المسار
العقد المستكشفة
دورة هاملتون
مسار هاملتون

الوضع

    الهدف

    المزيد عن مسارات هاملتون ودوراته

    مستكشف مسارات هاملتون

    في عام 1857 ابتكر ويليام روان هاملتون أحجية: سر على أضلاع مجسم اثني عشري بحيث تمر بكل زاوية من زواياه العشرين مرة واحدة بالضبط وتنتهي حيث بدأت. يسمى هذا المسار اليوم دورة هاملتون. التحقق منه سهل، وإيجاده صعب في العموم. تتبع واحدة بنفسك على مجسم هاملتون أو على رقعة شطرنج أو على مخطط ترسمه، أو راقب بحثًا بالتراجع وهو يطاردها، وعُدّ الطرق المسدودة التي يقع فيها، وانظر كم تختصر بضعة فحوص بسيطة من البحث. اختر مخططًا وهدفًا: دورة تعود إلى نقطة البداية، أو مسارًا. التتبع: انقر رأسًا للبدء، ثم انقر جارًا في كل مرة؛ الحلقات المتقطعة تبيّن إلى أين يمكنك المتابعة. النقر على الرأس الأخير أو زر رجوع أو تراجع يعود خطوة واحدة، وزر تلميح يذكر خطوة تالية ما زال يمكن إكمالها. البحث: زر تشغيل أو خطوة يشغّل بحثًا بالتراجع، يضيف رؤوسًا حتى يعلق ثم يرجع؛ الخطوط الحمراء المتقطعة تبيّن مواضع الرجوع، والأعمدة تعدّ العقد حسب طول المسار. قبل البدء، النقر على رأس يختار من أين ينطلق البحث. تبدّل مربعات الاختيار تشغيل التقليم وإيقافه، وزر مقارنة يشغّل البحث نفسه مع التقليم وبدونه، وزر عدّ الكل يعدّ كل دورة أو مسار في مخطط صغير. التحرير: انقر لإضافة رأس، وانقر رأسين لوصلهما أو فصلهما، واسحب لتحريك رأس، وزر حذف يزيل الرأس المحدد.

    كيف يعمل

    1. اختر مخططًا، مثل مجسم هاملتون الاثني عشري أو مخطط بيترسن أو جولة حصان، أو ارسم مخططك في وضع التحرير، ثم اختر دورة أو مسارًا هدفًا.
    2. في وضع التتبع، انقر رأسًا للبدء ثم انقر الجيران واحدًا بعد آخر. يعيدك زرّا رجوع وتراجع خطوة واحدة، ويبيّن زر تلميح خطوة تالية ما زال يمكن إكمالها.
    3. في وضع البحث، اضغط تشغيل أو خطوة لمتابعة التراجع وهو يبحث عن مسار، وبدّل تشغيل التقليم وإيقافه، ثم اضغط مقارنة لترى كم عقدة تحتاج كل نسخة.

    هاملتون مقابل أويلر

    يستعمل مسار أويلر كل ضلع مرة واحدة؛ ويمر مسار هاملتون بكل رأس مرة واحدة. يبدوان متشابهين لكن سلوكهما مختلف تمامًا. يُحسم وجود مسار أويلر في مخطط مترابط بعدّ الرؤوس ذات الدرجة الفردية، كما بيّن أويلر عام 1736: يوجد المسار حين لا توجد رؤوس كهذه أو حين يكون عددها اثنين. أما مسارات هاملتون فلا يُعرف لها قاعدة مماثلة. تحديد ما إذا كان لمخطط دورة هاملتون مسألة تامة في NP، وهي إحدى المسائل الإحدى والعشرين في قائمة ريتشارد كارب لعام 1972، فلو وُجدت طريقة سريعة لها لأعطت طرقًا سريعة لآلاف المسائل الصعبة الأخرى. والموجود شروط تحسم بعض المخططات. تضمن مبرهنة ديراك لعام 1952 وجود دورة هاملتون إذا كانت درجة كل رأس ⁦n/2⁩ على الأقل، وتضمنها مبرهنة أوري لعام 1960 إذا كان مجموع درجتي أي رأسين غير موصولين ⁦n⁩ على الأقل؛ أما رأس من الدرجة 1 أو رأس قاطع أو صنفا لون مختلفا الحجم فينفونها.

    كيف يعمل البحث

    يبني التراجع المسار رأسًا رأسًا، وحين يعلق يسحب الخطوة الأخيرة ويجرّب الجار التالي. وهو يجد دورة هاملتون دائمًا إن وُجدت، لكن عدد المسارات الجزئية قد ينمو أسّيًا. في الشبكة ⁦5 × 5⁩، التي ليست لها دورة هاملتون، يستكشف التراجع البسيط 153٬745 عقدة قبل أن يتيقن. وهناك فحصان يوقفان المسارات اليائسة مبكرًا: الرأس غير المزار الذي له أقل من جارين حرّين لم يعد ممكنًا إدراجه في دورة، وحين تتفكك الرؤوس غير المزارة إلى أجزاء منفصلة فلا مسار واحد يغطيها. وبالفحصين معًا يستغرق البرهان نفسه 1٬761 عقدة. أما قاعدة فارنسدورف لعام 1823، التي تجرّب أولًا الجار الأقل نقلات تالية، فتجد جولة حصان على رقعة ⁦8 × 8⁩ انطلاقًا من زاوية في 64 نقلة دون طريق مسدود واحد.

    الأسئلة المتداولة

    ما الفرق بين مسار هاملتون ودورة هاملتون؟

    يمر مسار هاملتون بكل رأس في المخطط مرة واحدة بالضبط. وتفعل دورة هاملتون الشيء نفسه ثم تعود عبر ضلع إضافي إلى حيث بدأت، فيمكنها أن تبدأ من أي من رؤوسها. كل مخطط له دورة هاملتون له مسار هاملتون أيضًا (احذف ضلعًا واحدًا من الدورة)، لكن العكس غير صحيح: لمخطط بيترسن مسارات هاملتون وليست له دورة هاملتون.

    هل للمجسم الاثني عشري دورة هاملتون؟

    نعم، 30 دورة، إذا عُدّت كل دورة مرة واحدة أيًا كانت نقطة بدايتها واتجاهها. حوّل هاملتون هذا السؤال عام 1857 إلى لعبة الإيكوسيان، وهي رقعة عليها زوايا مجسم اثني عشري مفرود، معلَّمة بحروف ساكنة، وباع حقوقها بخمسة وعشرين جنيهًا لصانع الألعاب اللندني John Jaques and Son. ويجد زر عدّ الكل في التطبيق هذه الدورات الثلاثين في نحو 1٬400 عقدة.

    لماذا لا توجد دورة هاملتون في شبكة ⁦5 × 5⁩؟

    لوّن النقاط الخمس والعشرين كرقعة شطرنج: 13 منها بلون و12 باللون الآخر، وكل خطوة تنتقل إلى اللون الآخر. والدورة تتناوب الألوان طوال الدوران، فتحتاج إلى عدد متساوٍ من اللونين، وهو ما لا يوفره العددان 13 و12. وينطبق المنطق نفسه على كل شبكة عدد نقاطها فردي، وعلى الحصان في رقعة ⁦5 × 5⁩ أو ⁦7 × 7⁩ (فالحصان يبدّل لون المربع دائمًا)، وعلى مخطط هيرشل الذي يضم صنفاه 6 و5 رؤوس. ويبقى مسار هاملتون ممكنًا: يبدأ وينتهي على اللون الأكثر عددًا.

    كيف تجد قاعدة فارنسدورف جولة حصان؟

    اقترح ه. ك. فون فارنسدورف عام 1823 أن يُنقل الحصان دائمًا إلى المربع الذي ستكون منه أقل نقلات تالية. وبذلك تُزار المربعات القريبة من الحواف والزوايا، وهي التي يسهل قطعها، في وقت مبكر ما دام الحصان يستطيع الوصول إليها. والقاعدة تجريبية لا ضمان فيها، ولا بد من فض التعادل بطريقة ما، لكنها على رقعة ⁦8 × 8⁩ تكمل الجولة عادة دون رجوع. وبدمجها مع التراجع، كما في هذا التطبيق، تجد جولات مفتوحة من ⁦5 × 5⁩ فما فوق وجولات مغلقة على رقعتي ⁦6 × 6⁩ و⁦8 × 8⁩.

    كم دورة هاملتون في المخطط التام؟

    ⁦(n − 1)!/2⁩ عندما ⁦n ≥ 3⁩. ثبّت رأس البداية؛ فالرؤوس ⁦n − 1⁩ الباقية يمكن أن تأتي بأي ترتيب، وكل دورة تُعدّ مرتين، مرة لكل اتجاه. في ⁦K₆⁩ توجد ⁦5!/2 = 60⁩ دورة، وفي ⁦K₁₀⁩ توجد 181٬440. وهذه هي الجولات التي على البائع المتجول أن يختار منها، ولهذا يصير تجريبها كلها مستحيلًا بهذه السرعة.

    هل أنت مستعد لتجربتها؟

    افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.

    الانتقال إلى المحرر