هافل–حكيمي: لماذا نعيد ترتيب الدرجات بعد كل خطوة؟

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

لأن الدرجات تتغير بعد الطرح؛ ترتيبها السابق لا يضمن أن المواقع الأولى تحمل أكبر القيم الجديدة. في مثال(3,3,2,2,2)، تصبح البقية(2,1,1,2)، ويجب ترتيبها إلى(2,2,1,1) قبل الخطوة التالية. توجد حواف تحقق المدخل، رغم فشل التنفيذ دون إعادة الفرز.

• نقصد رسمًا غير موجه، بلا حلقة ذاتية أو حواف مكررة. اختبر أعدادًا صحيحة غير سالبة، ورتبها تنازليًا؛ احذف أكبر درجة d واطرح1 من أكبر d درجات باقية، ثم أعد الترتيب. هذه خطوة هافل–حكيمي. [1]
• نثبت A وB وC وD وE بدرجات3 و3 و2 و2 و2. بعد وصل A بـB وC وD، تبقى B:2 وC:1 وD:1 وE:2. لا نقرأ مواقع القائمة القديمة على أنها ترتيب جديد.
• نرتب البقية إلى B:2 وE:2 وC:1 وD:1. نصل B بـE وC، ثم E بـD. الحواف AB وAC وAD وBE وBC وDE تعطي الدرجات المطلوبة، وعددها6.
• إذا وصلنا B بـC وD بحسب المواقع القديمة، اكتملت درجات A وB وC وD، لكن بقيت درجتان عند E وحده. هذا فشل ذلك الاختيار، وليس برهانًا على استحالة المدخل؛ الرسم الصحيح يعرض حلًا.
• لكل حافة طرفان، لذا مجموع الدرجات زوجي. لكن المثال(3,3,1,1) مجموعه8 ولا يمكن بناؤه: في أربعة رؤوس يتصل كل رأس درجته3 بالثلاثة الآخرين، فيجبر الرأسين الأخيرين على درجة لا تقل عن2.
• احتفظ بالصفر، وارفض الدرجة السالبة أو أكبر درجة تتجاوز عدد الرؤوس الأخرى. إذا وصلت البقية إلى أصفار، فلا تحتاج حواف إضافية. الاختبار يجيب عن وجود رسم، ولا يختار شكلًا هندسيًا وحيدًا أو يثبت اتصال أي رسم آخر.

حدد الدرجة ونوع الرسم

درجة الرأس هنا عدد حوافه؛ والمتتالية القابلة للتحقيق هي درجات رسم موجود. في خطوة هافل–حكيمي نحذف رأسًا ونخفض درجات أصحاب أكبر القيم الباقية. إمكان تحقيق القائمة قبل الخطوة وبعدها متكافئ، مع إعادة الفرز. [1]

نعمل على خمسة رؤوس مختلفة A وB وC وD وE. الحافة AB هي نفسها BA؛ لا أسهم، ولا اتصال من الرأس بنفسه، ولا نسختان من الحافة. الأعداد ليست أطوال الخطوط أو ترتيب زيارة الرؤوس.

حددنا درجات الرؤوس بالترتيب A:3 وB:3 وC:2 وD:2 وE:2. عند تساوي الدرجات نستخدم ترتيب الحروف في مثالنا لتثبيت اختيار يمكن تتبعه، ولا ندعي أن التعادل يحتاج هذا الترتيب بعينه.

بعد حذف A يتغير ترتيب البقية

لأن درجة A المطلوبة3، نختار أكبر ثلاثة رؤوس أخرى في ترتيب البداية: B وC وD. نضيف الحواف AB وAC وAD. صار عند A ثلاث حواف فعلية؛ نخرجه من العمل الجاري، ونطرح1 من حاجة كل جار.

نكتب الدرجات الباقية، لا الدرجات الأصلية: B يحتاج2، وC يحتاج1، وD يحتاج1، وE يحتاج2. بقي E دون حافة، لذلك لم تنخفض درجته. في المواقع القديمة نحصل على(2,1,1,2).

هذه القائمة غير مرتبة تنازليًا؛ آخرها2 أكبر من الوسط1. قبل الاختيار التالي ننقل E مع اسمه إلى جانب B، فتصير(2,2,1,1). تغيير مكان العدد دون اسم صاحبه يفسد بناء الرسم، حتى لو صح اختبار الأعداد المجردة.

أكمل البناء مع الأسماء والدرجات الباقية

نختار B، وحاجته الباقية2. أكبر حاجتين بين الآخرين هما E:2 وC:1، مع تقديم C على D عند التعادل. نضيف BE وBC. صار B متصلًا بـA وE وC، فيحقق درجته3 ونخرجه من العمل الجاري.

تبقى E:1 وC:0 وD:1. نعيد الترتيب إلى E:1 وD:1 وC:0، ثم نضيف ED ونخرج E. لا نضيف اتصالًا إلى C لمجرد أن اسمه كان في الموقع التالي؛ حاجته صفر.

صارت الدرجات الباقية عند D وC صفرًا. الحواف الست النهائية هي AB وAC وAD وBE وBC وDE. افحصها رأسًا رأسًا: A له B وC وD؛ وB له A وE وC؛ وC له A وB؛ وD له A وE؛ وE له B وD.

تعطي هذه الجيران الدرجات(3,3,2,2,2). المجموع12 يساوي2×6، ولا حافة مكررة أو حلقة ذاتية. الرسم الرئيسي يعرض الاتصالات نفسها، لا قياسات هندسية؛ تقاطع خطين على الصفحة لا يضيف رأسًا بلا دائرة واسم.

فشل الاختيار القديم لا يعني فشل المدخل

نعود إلى البقية بعد إخراج A: B:2 وC:1 وD:1 وE:2. إذا لم نعد ترتيبها، فقد نختار B ثم نطرح من C وD، لأنهما يليانه في المواقع القديمة. نضيف BC وBD؛ هذا اختيار مختلف عن BE وBC.

عندئذ تكون الحواف الجزئية AB وAC وAD وBC وBD. درجات A وB وC وD الفعلية هي3 و3 و2 و2، بينما E درجته0 ويحتاج2. لم يبق رأس ذو حاجة موجبة يمكن وصله بـE دون تجاوز الدرجة المطلوبة.

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

لكن لدينا بالفعل الرسم الصحيح بالحواف الست. فشل التنفيذ الذي فقد ترتيب القيم لا يثبت استحالة وجود رسم. أصلح القاعدة أولًا، ولا تنسب رفضًا خاطئًا إلى نظرية هافل–حكيمي.

المجموع الزوجي فحص أولي لا شهادة إمكان

كل حافة في نموذجنا تصل رأسين مختلفين، فتضيف1 إلى درجة كل طرف. بجمع درجات الرؤوس نعد كل حافة مرتين. لذلك لا يمكن أن يكون المجموع فرديًا، كما في(2,1,0) التي مجموعها3.

أما(3,3,1,1) فمجموعها8، وكل درجة لا تتجاوز3، لكنها مستحيلة على أربعة رؤوس. سم الرأسين الأولين U وV؛ درجة كل منهما3 تجبره على الاتصال بجميع الآخرين.

إذن الرأس الثالث متصل بكل من U وV، وكذلك الرابع. لا تقل درجة أي منهما عن2، بينما المدخل يطلب1. هذا تناقض مباشر، دون الاحتياج إلى رسم تقريبي أو تجريب ترتيب مواضع.

يتوافق الاختبار الصحيح مع هذا الرفض: بعد حذف3 والطرح من الثلاثة الآخرين تصبح(2,0,0). حذف2 يفرض الطرح من الصفرين، فتظهر درجتان سالبتان. لا نحذف القيم السالبة ونواصل كأن شيئًا لم يحدث.

راجع شروط التوقف قبل إعلان النتيجة

الأصفار تعني رؤوسًا لا تحتاج حواف أخرى. مثلًا(0,0,0) تمثل ثلاثة رؤوس منفصلة بلا حواف، لا مدخلًا ناقصًا. في مثالنا لم نحذف الصفر مبكرًا من الشرح حتى يبقى اسم الرأس وسبب استبعاده واضحين.

إذا حذفت درجة d ولم يبق d رؤوس أخرى، فالخطوة مستحيلة. مثال(4,1,1,0) يطلب من رأس الاتصال بأربعة آخرين، لكن المتاح ثلاثة فقط. الكسور والقيم السالبة لا تمثل درجات هذا النموذج أصلًا.

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

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