محدد المسارات: لماذا يمكن أن تكون النتيجة سالبة؟

الخلاصة السريعة

لأن المحدد يطرح أسر ترتيب النهايتين المعكوس من أسر ترتيبهما الأصلي، ولا يجمع العددين. في الرسم الأول لا توجد أسرة منفصلة للوصل A→C وB→D، وتوجد ثلاث للوصل A→D وB→C؛ لذلك det M=0−3=−3، مع أن العدد الكلي ثلاث.

• في الرسم الموجه الخالي من الدورات، يفسر مبدأ ليندستروم–جيسل–فيينو المحدد كمجموع بإشارات لأسر مسارات لا تشترك في رؤوس. [1] لا نجعله عددًا موجبًا دون فحص ترتيب النهايات.
• نثبت A وB بدايتين، وC وD نهايتين؛ الحواف A→X وB→X وX→C وX→D وA→D وB→C. صفا عدد المسارات هما (1,2) و(2,1)، فيكون 1×1−2×2=−3.
• بالترتيب الأصلي، المساران A→X→C وB→X→D يشتركان في X. بالترتيب المعكوس، ثلاث أسر منفصلة: A→X→D مع B→C، أو A→D مع B→X→C، أو A→D مع B→C.
• تبديل ذيلي المسارين عند X يربط الأسرة المشتركة ذات الإشارة الموجبة بأسرة مشتركة سالبة، فيلغيهما الطرح. لا نعد تقاطع خطين بلا رأس مسمى مشاركةً في رأس.
• إضافة A→C تعطي أسرة موجبة واحدة وثلاثًا سالبة: المحدد −2 والعدد الكلي 4، لا 2. وإضافة B→D أيضًا تجعل المحدد صفرًا مع ست أسر منفصلة؛ الصفر لا ينفي وجودها.
• عرّف P عدد الأسر المنفصلة بالترتيب الأصلي وQ بالمعكوس: المحدد P−Q، والكل N=P+Q؛ إذا Q=0 يطابق الفرق العدد P. راجعنا 256 رسمًا من حواف الطبقات الثماني الممكنة؛ المثال محدود ولا يحول إشارات المحدد إلى أوزان مرور سالبة.

ثبّت اتجاه الحواف وترتيب النهايات

الأسماء الخمسة A وB وX وC وD رؤوس مختلفة. الحواف الست موجهة: A→X وB→X وX→C وX→D وA→D وB→C. لا نستعمل X→A مثلًا لأن عكس السهم ليس حافة معلنة.

يمر كل سهم من طبقة A وB إلى X أو مباشرة إلى طبقة C وD، ثم تقف المسارات عند النهاية. الترتيب A B X C D يسمح بقراءة الحواف إلى الأمام فقط؛ لا مسار يعود إلى بداية ليشكل دورة موجهة.

نختار مسارًا يبدأ من A وآخر يبدأ من B، ويجب أن يستعملا C وD نهايتين مختلفتين. هناك ترتيب أصلي A→C مع B→D، وترتيب معكوس A→D مع B→C. ترتيب البدايات والنهايات جزء من تعريف المصفوفة.

نسمي الزوج أسرة منفصلة إذا لم تتكرر بين مساريه أي هوية رأس. هنا الأطراف الأربعة مختلفة، فلا استثناء لطرف مشترك كما في مسألة مسارين بين بداية واحدة ونهاية واحدة. X وحده يمكن أن يكون رأسًا مشتركًا في الداخل.

سنكتب P لعدد الأسر المنفصلة بالترتيب الأصلي، وQ لعددها بالمعكوس، وN لمجموعهما. الأعداد P وQ وN غير سالبة. الذي قد يكون سالبًا هو الفرق P−Q، وليس عدد المسارات الفردية أو وزن حافة.

ابن المصفوفة من قوائم المسارات الفردية

من A إلى C يوجد A→X→C فقط. ومن A إلى D يوجد A→X→D والحافة المباشرة A→D. لذلك صف A، بترتيب العمودين C ثم D، هو (1,2). لا نعطي حافة إضافية من موضع تقاطع خطين في الصورة.

من B إلى C يوجد B→X→C والحافة B→C، ومن B إلى D يوجد B→X→D فقط. صف B هو (2,1). كل مسار قائمة اتجاهات موجودة؛ اختلاف المرور بـX عن الحافة المباشرة يجعل الخيارين مختلفين.

محدد المصفوفة ذات الصفين (1,2) و(2,1) هو حاصل ضرب القطر الأول ناقص حاصل ضرب القطر الآخر: 1×1−2×2=−3. مدخلات المصفوفة موجبة، لكن الطرح بين حاصلَي الضرب قد يعطي عددًا سالبًا.

الحاصل 1×1 يجمع اختيارات المسارين بالنهايات الأصلية دون اشتراط انفصالهما؛ والحاصل 2×2 يجمع اختياراتهما بالنهايات المعكوسة دون هذا الشرط أيضًا. لا تعني كتابة حاصل ضرب أننا تحققنا بعد من أسماء الرؤوس المشتركة.

احصر الأسر الخمس قبل منع الرأس المشترك

للترتيب الأصلي اختيار واحد: A→X→C مع B→X→D. رؤوس الأول A وX وC، ورؤوس الثاني B وX وD؛ التقاطع X، فيفشل شرط الانفصال. لذلك P=0 في هذا الرسم، رغم وجود مسار فردي لكل طلب.

للترتيب المعكوس أربع اختيارات. إذا استعملنا A→X→D مع B→X→C، اشترك المساران في X وفشلا. أما إذا أخذنا A→X→D مع B→C، فمجموعتا الرؤوس {A,X,D} و{B,C} لا تتقاطعان؛ هذه أسرة صالحة.

والأسرة A→D مع B→X→C صالحة أيضًا، لأن {A,D} لا تشارك {B,X,C} أي اسم. والأسرة الثالثة A→D مع B→C صالحة: أربعة أطراف مختلفة وحافتان مباشرتان. إذن Q=3، لا أربعة.

لدينا خمس أسر عند السماح بالمشاركة: واحدة أصلية وأربع معكوسة. بعد منع الرأس المشترك تبقى ثلاث فقط، وكلها معكوسة. العدد الكلي N=3، والفرق P−Q=0−3=−3؛ هذان حسابان يجيبان عن سؤالين مختلفين.

قد تتقاطع الحافتان المباشرتان A→D وB→C في الرسم على الصفحة، لكن لا يوجد رأس مسمى عند التقاطع. يبقى هذا الزوج منفصلًا في الرؤوس المحددة. نحن نقارن قوائم الأسماء، لا نحول كل التقاء بصري بين خطين إلى اتصال جديد.

بدّل الذيول عند X لتفهم الإلغاء

تفسر صيغة ليندستروم–جيسل–فيينو في الرسم الموجه الخالي من الدورات المحدد كمجموع بإشارات لأسر منفصلة الرؤوس، بحسب تبديل نهاياتها. [1] سنراجع الإلغاء في مثال الرأس الوسيط الواحد بدل ادعاء برهان المبدأ لكل رسم.

خذ الأسرة A→X→C مع B→X→D. بعد الوصول إلى X، بدّل الجزء المتبقي من المسارين: يصير الأول A→X→D، والثاني B→X→C. الحواف الأربع إلى X ومنه موجودة، ولذلك الزوج الناتج صالح كمسارين، لكنه يظل مشتركًا في X.

الزوج الأول من ترتيب النهايات الأصلي، فيدخل بإشارة +1؛ والثاني من المعكوس، فيدخل بإشارة −1. تبديل الذيول مرة أخرى يعيد الزوج الأول. لهذا يتقابل الاختياران المشتركان ويسهمان بالمجموع صفر في الفرق.

بقيت الأسر الثلاث المنفصلة المعكوسة، وكل منها يسهم −1، فكان المحدد −3. الإلغاء يحذف الأسر المشتركة من المجموع ذي الإشارات، لكنه لا يحول مساهمات الأسر المنفصلة السالبة إلى موجبة.

الصورة الداخلية تبرز X بلون مختلف، وتعرض الزوجين المتقابلين قبل التبديل وبعده. الأزرق مسار A والأحمر مسار B؛ الحواف الرمادية متاحة لكنها غير مختارة في الأسرة المعروضة. لا نزعم أن الزوجين المصورين منفصلان.

القيمة المطلقة تفقد الفرق بين العددين

أضف A→C مباشرة، وأبق الحواف الست الأخرى. يصبح صف A هو (2,2)، ويبقى صف B هو (2,1). المحدد 2×1−2×2=−2. الحافة الجديدة موجودة فعلًا في الصورة الرئيسية اليمنى، وليست تغييرًا في ترتيب أسماء المصفوفة.

يوجد الآن زوج منفصل أصلي جديد: A→C مباشرة مع B→X→D؛ مجموعتا الرؤوس {A,C} و{B,X,D} منفصلتان. الزوج الأصلي عبر X في المسارين ما زال يفشل. إذن P=1، بينما تبقى الأسر المعكوسة الثلاث نفسها ويكون Q=3.

العدد الكلي 1+3=4، والفرق 1−3=−2. القيمة المطلقة للمحدد 2 لا تساوي العدد الكلي 4؛ لذلك لا تصلح وصفة «احذف إشارة السالب» لعد الأسر كلها. في الرسم الأول وافقت القيمة المطلقة العدد 3 لأن P كان صفرًا، لا لأن الوصفة عامة.

أضف B→D أيضًا، فيصبح الصفان (2,2) و(2,2)، والمحدد صفرًا. في كل ترتيب أربع اختيارات؛ واحدة تمر بـX في المسارين وتفشل، والثلاث الأخرى منفصلة. لدينا P=3 وQ=3، فيكون N=6 رغم أن P−Q=0.

ميز العدد الكلي عن المجموع ذي الإشارات

للمقارنة، احذف الحافتين المباشرتين A→D وB→C من الرسم الأول. تبقى أربع حواف عبر X فقط، وصفان (1,1) و(1,1). كل أسرة تشترك في X، فيكون P=0 وQ=0 وN=0، والمحدد صفرًا أيضًا. الصفر هنا يوافق غياب الأسر المنفصلة؛ وفي رسم الحواف الثماني لا يوافقه.

إذا لم يسمح اتصال الرسم بأية أسرة منفصلة للنهايات المعكوسة، يكون Q=0 ويصير الفرق P−Q مساويًا P. [1] هذا هو الشرط الذي يجب فحصه قبل استعمال المحدد عدًّا موجبًا للترتيب الأصلي، وليس افتراضًا تمنحه الأعداد الموجبة في المصفوفة.

راجعنا جميع الرسوم الـ256 الناتجة من اختيار أي مجموعة من الحواف الثماني الممكنة في الطبقات المحددة. حصرنا المسارات والأسر لكلا ترتيبَي النهايات، وفحصنا مجموعات الأسماء، وتحققنا من إلغاء الزوجين المشتركين بتبديل الذيول عند X كلما وجدا.

هذه مراجعة منتهية لخمسة رؤوس بطبقات ثابتة وحواف بلا أوزان. لا ندعي خوارزمية عامة لكل رسم أو برهانًا عامًا لاختيار أول رأس مشترك إذا تعددت الرؤوس المشتركة. لا توجد حواف سالبة ولا سعات أو أزمنة حقيقية في المسألة.

ابدأ بترتيب الصفوف والأعمدة وقوائم الحواف الموجهة. عد المسارات الفردية، ثم افحص انفصال كل زوج ومعنى إشارة ترتيب نهايتيه. إذا أردت جميع الأسر، اجمع P+Q؛ وإذا أردت تفسير المحدد، احتفظ بالطرح P−Q وبشروطه.