الدورة السالبة: قد تتأثر وجهة ويبقى أقل وزن لأخرى محددًا

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

في مثالنا يمكن الوصول من A إلى الدورة B→C→B ذات الوزن 1 − 3 = −2. بعد تكرارها k مرة ثم الخروج إلى D يصبح وزن الرحلة 4 − 2k، ويمكن خفضه بلا حد. أما E فلا يصله إلا A→E بوزن 4، ولا يوجد طريق من الدورة إليه؛ لذلك أقل وزن إلى E يظل 4. نفترض السماح بتكرار الرؤوس والحواف أثناء الرحلة.

• تؤثر الدورة السالبة في الوجهة عندما يمكن بلوغ الدورة من البداية، ثم بلوغ الوجهة منها. مع السماح بالتكرار لا يبقى حد أدنى منتهٍ لوزن الرحلات إلى الرؤوس على الدورة أو التي تصل إليها. الدورة غير المتاحة من البداية لا تؤثر في هذه الرحلات. [1]
• الحواف الأصلية A→B بوزن 1، و B→C بوزن 1، و C→B بوزن −3، و C→D بوزن 2، و A→E بوزن 4 فقط. البداية A، والدورة B→C→B مجموعها −2.
• ليكن k عددًا صحيحًا غير سالب. رحلة A→B ثم k دورات B→C→B ثم B→C→D تستخدم 3 + 2k حافة ووزنها 4 − 2k. عند k يساوي 0 أو 1 أو 2 أو 3، الأوزان 4 و 2 و 0 و −2؛ لا تتوقف المقارنة عند أقل صف مكتوب.
• في الرسم الأصلي A له أقل وزن 0، و E له أقل وزن 4. أما B و C و D فأوزان الرحلات إليها تنخفض بلا حد، ونشير إلى ذلك بـ −∞؛ لا نعني رحلة منتهية وزنها اللانهاية السالبة.
• إضافة C→E بوزن 1 تجعل E متأثرًا أيضًا: يمكن الدوران ثم الخروج إليه بوزن 3 − 2k. وفي تعديل منفصل، حذف A→B يجعل الدورة غير متاحة من A، ولا يصل A إلى B أو C أو D؛ ويبقى E متاحًا بوزن 4.
• إضافة F معزولًا تجعل حالته ∞ لعدم وجود رحلة إليه، بخلاف −∞ الذي يعني إمكان خفض الوزن بلا حد. وإذا منعنا تكرار الرؤوس، لم تعد الرحلات الدورية مسموحة؛ في رسمنا يصبح A→B→C→D الطريق الوحيد إلى D ووزنه 4.

حدد هل تسمح بتكرار الرؤوس والحواف

عندما تكون دورة سالبة متاحة من البداية، تنخفض أوزان الرحلات إلى رؤوسها وإلى الرؤوس التي يمكن الوصول إليها منها بلا حد؛ ولا تؤثر دورة لا يمكن الوصول إليها من البداية. [1]

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

رؤوس الرسم A و B و C و D و E، والبداية A. الحواف الوحيدة A→B بوزن 1، و B→C بوزن 1، و C→B بوزن −3، و C→D بوزن 2، و A→E بوزن 4. السهمان بين B و C متعاكسان، ولكل منهما وزنه المستقل؛ لا نحول أحدهما إلى نسخة من الآخر.

الأرقام أوزان حسابية مجردة، لا أزمنة سفر أو أطوالًا فعلية. وزن الرحلة مجموع أوزان كل عبور، حتى عند استخدام الحافة نفسها ثانية. يوضح الشكل الرئيسي اتجاه كل سهم ووزنه. لا توجد حافة خروج من D أو E، ولا حافة تدخل A.

دورة وزنها −2 تنتج رحلات إلى D بأوزان أقل باستمرار

الدورة B→C→B تجمع وزن B→C الذي يساوي 1 ووزن C→B الذي يساوي −3، فيكون مجموعها 1 − 3 = −2. من A نصل إلى B عبر A→B بوزن 1، لذلك نستطيع بدء الدورة فعلًا من البداية المحددة.

بعد الوصول إلى B، نكرر B→C→B عدد k من المرات، ثم نخرج عبر B→C→D. هنا k عدد صحيح غير سالب. الوصول إلى B يضيف 1، وكل دورة تضيف −2، والخروج عبر B→C→D يضيف 1 + 2 = 3؛ فيصبح المجموع 4 − 2k.

عدد الحواف المستخدمة في هذه الرحلة 3 + 2k: حافة A→B، وحافتان لكل تكرار، وحافتا الخروج B→C و C→D. يظهر الجدول أمثلة مختارة لقيمة k وعدد الحواف والوزن. عند k يساوي 10 يصبح الوزن −16 مع 23 عبورًا.

هذه الأرقام ليست خمس تجارب تنهي المسألة. لأي k نستطيع اختيار k + 1، فنحصل على رحلة مسموحة إلى D أقل وزنًا بمقدار 2. بذلك لا توجد رحلة منتهية هي الأقل بين جميع الرحلات المسموحة، ولا أصغر قيمة منتهية لوزنها.

D متأثر، لكن أقل وزن إلى E يبقى 4

الرأس D ليس جزءًا من الدورة B→C→B، لكنه متاح منها عبر C→D. يمكن تأخير الخروج حتى نكرر الدورة أكثر، فينتقل إليه أثر التخفيض. وبالنسبة إلى B، الرحلات A→B مع k دورات وزنها 1 − 2k؛ وإلى C نضيف B→C فتصير 2 − 2k.

أما E فالحافة الداخلة الوحيدة إليه A→E بوزن 4. ولا تدخل A أي حافة، فلا يمكن الانطلاق من A إلى الدورة ثم الرجوع إلى A لأخذ A→E. كذلك لا يوجد سهم من B أو C أو D إلى E. لذا الرحلة الوحيدة إلى E هي A→E، وأقل وزنها 4.

يبقى أقل وزن إلى A مساويًا 0، باستعمال رحلة لا تعبر أي حافة. لا توجد رحلة أخرى تعود إلى A لأن كل حواف الرسم لا تدخل إليه. يسجل الجدول وضع الرؤوس الخمسة؛ ولا نعلن أن كل وجهة فقدت قيمتها الدنيا لمجرد وجود الدورة.

نكتب −∞ اختصارًا لعدم وجود حد أدنى منتهٍ للأوزان إلى B و C و D في هذا المثال. كل رحلة كتبناها بعدد محدد من الدورات لها وزن منتهٍ؛ الرمز لا يصف رحلة واحدة تنتهي بوزن اللانهاية السالبة. الصورة الداخلية تميز الرؤوس المتأثرة عن A و E.

سهم جديد إلى E ينقل الأثر، وحذف مدخل الدورة يمنعه

نضيف C→E بوزن 1 فقط إلى الرسم الأصلي. الآن نستطيع الوصول إلى B، وتكرار الدورة k مرة، ثم اتباع B→C→E. يكون الوزن 1 − 2k + 1 + 1، أي 3 − 2k؛ لذلك يمكن خفض الوزن إلى E بلا حد أيضًا.

الطريق المباشر A→E بوزن 4 لم يحذف في هذا التعديل. وجوده لا يحمي القيمة الدنيا: الطرق الأخرى المتاحة أصبحت تنخفض أكثر منه باستمرار. يحكمنا كل ما تسمح به الحواف المعدلة، لا اختيار طريق واحد مريح.

في تعديل منفصل نعود إلى الرسم الأصلي ونحذف A→B وحدها، دون إضافة C→E. ما زالت الدورة B→C→B موجودة ووزنها −2، لكن A لا يملك الآن سوى A→E، ولا تخرج من E أي حافة. فلا نستطيع الوصول إلى الدورة من A.

بعد الحذف لا توجد رحلة من A إلى B أو C أو D. يبقى A عند 0 و E عند 4، وتصبح الرؤوس الثلاثة الأخرى غير متاحة. إذن وجود دورة سالبة في مكان من الرسم يختلف عن إمكان استعمالها من البداية المحددة.

ميز غياب الرحلة من غياب الحد الأدنى

في تعديل ثالث نضيف F بلا أي حافة إلى الرسم الأصلي. لا توجد رحلة من A إلى F، فنكتب ∞ لحالة عدم الوصول. أما D فيمكن الوصول إليه، لكن أوزان رحلاته تنخفض بلا حد؛ حالته −∞. لا يجوز استبدال الحالتين أو إعطاء F وزن 0.

إذا غيرنا قاعدة السؤال ومنعنا تكرار أي رأس، فلن نستطيع استعمال B→C→B ضمن طريق إلى D، لأنه يكرر B. في رسمنا يصبح A→B→C→D الطريق البسيط الوحيد إلى D، ومجموعه 1 + 1 + 2 = 4. هذا جواب للسؤال المقيد الجديد، لا تصحيح لنتيجة الرحلات التي تسمح بالتكرار.

لذلك اكتب نقطة البداية والوجهة وقاعدة التكرار قبل الحكم. افحص هل تصل البداية إلى الدورة، وهل تصل الدورة إلى الوجهة. والحد −∞ لا يدل على قياس فيزيائي أو على تنفيذ رحلة لا نهائية؛ إنه يختصر مقارنة عائلة من الرحلات المنتهية التي لا يحد انخفاض وزنها.