شرح مسارات هاملتون ودوراته

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

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

كل رأس مرة واحدة

المخطط مجموعة من النقاط تسمى الرؤوس، تصل بينها خطوط تسمى الأضلاع. ويسير مسار هاملتون على الأضلاع فيمر بكل رأس مرة واحدة بالضبط؛ أما دورة هاملتون فتعود كذلك إلى حيث بدأت، فعدد أضلاعها يساوي عدد رؤوسها. ويسمى المخطط الذي له دورة هاملتون مخططًا هاملتونيًا. والتحقق من مسار مقترح سهل: عُدّ الرؤوس وانظر في كل خطوة. أما الصعب فهو إيجاد مسار أو إثبات عدم وجود أي مسار، لأن عدد الترتيبات التي يمكن أن تُزار بها الرؤوس ينمو مثل ⁦n!⁩، وهو عند 20 رأسًا ⁦2٫4 × 10¹⁸⁩ بالفعل.

لعبة الإيكوسيان لهاملتون

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

جولات الحصان

تحرّك جولة الحصان حصان الشطرنج بحيث يحط على كل مربع مرة واحدة بالضبط: وهي مسار هاملتون في المخطط الذي رؤوسه المربعات وأضلاعه نقلات الحصان. والجولة المغلقة تنتهي على بعد نقلة حصان من نقطة بدايتها، أي إنها دورة هاملتون. وكان لاعبو الشطرنج يطرحون مثل هذه الأحاجي قبل أكثر من ألف عام، ودرسها أويلر في بحث عام 1759. وفي عام 1823 اقترح ه. ك. فون فارنسدورف الانتقال دائمًا إلى المربع الأقل نقلات تالية؛ وهذه القاعدة البسيطة تكمل عادة جولة على رقعة ⁦8 × 8⁩ دون رجوع. والحصان يبدّل لون المربع دائمًا، فالجولة المغلقة تحتاج إلى عدد متساوٍ من المربعات الفاتحة والداكنة، وهو ما يستبعد الرقع ذات العدد الفردي من المربعات. وبيّن ألن شوينك عام 1991 بالضبط أي الرقع المستطيلة لها جولة مغلقة؛ ومن بين المربعة، كل رقعة طول ضلعها زوجي ⁦6⁩ فأكثر. ولرقعة الشطرنج المعتادة 13٬267٬364٬410٬532 جولة مغلقة، عدّها بريندان مكاي عام 1997.

مخططات بلا دورة هاملتون

أسرع البراهين على عدم وجود دورة هي حجج العدّ. فإذا أمكن تلوين الرؤوس بلونين بحيث يصل كل ضلع لونين مختلفين، فالدورة تتناوب وتحتاج إلى عدد متساوٍ من رؤوس كل لون؛ وفي الشبكة ⁦5 × 5⁩ ثلاثة عشر من لون واثنا عشر من الآخر، فليست لها دورة هاملتون. والرأس القاطع، الذي تؤدي إزالته إلى تقسيم المخطط، سيلزم المرور به مرتين، والرأس من الدرجة 1 لا يمكن المرور به أصلًا. على أن بعض المخططات يفلت من كل هذه الحجج. فمخطط بيترسن، الذي نشره يوليوس بيترسن عام 1898، له 10 رؤوس من الدرجة 3 وليست له دورة هاملتون، ومع ذلك فحذف أي رأس منه يترك مخططًا له دورة؛ وهو أصغر مخطط شبه هاملتوني من هذا النوع. ومخطط هيرشل، المسمى باسم ألكسندر ستيوارت هيرشل الذي كتب عن لعبة الإيكوسيان عام 1862، له 11 رأسًا و18 ضلعًا، وهو مخطط متعدد سطوح ذي تسعة أوجه رباعية. ولا يخلو أي متعدد سطوح أقل زوايا من دورة هاملتون. وفي عام 1884 حدس بيتر غوثري تيت أن كل متعدد سطوح تلتقي في كل زاوية منه ثلاثة أضلاع له دورة هاملتون؛ فوجد و. ت. توت عام 1946 مثالًا مضادًا بستة وأربعين رأسًا.

شروط تضمن وجود دورة

إذا كان للمخطط أضلاع كثيرة فوجود دورة هاملتون مؤكد. أثبت غابرييل ديراك عام 1952 أن المخطط الذي له ⁦n ≥ 3⁩ من الرؤوس ودرجة كل رأس فيه ⁦n/2⁩ على الأقل له دورة هاملتون، وأضعف أويستاين أوري الشرط عام 1960: يكفي أن يكون مجموع درجتي أي رأسين غير موصولين ⁦n⁩ على الأقل. والشرطان لا يعملان إلا في اتجاه واحد. فحلقة بسيطة من 100 رأس درجتها 2 في كل موضع، أي أقل بكثير من 50، ومع ذلك فهي نفسها دورة هاملتون. وهذه هي الصورة العامة: هناك شروط كافية وهناك أسباب للفشل، وبينهما يمتد إقليم واسع من المخططات لا يحسمه إلا البحث.

لماذا لا يُعرف اختبار سريع

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

رموز غراي والمكعب الفائق

اكتب الأعداد من 0 إلى 7 رموزًا من ثلاث بتات، وصِل رمزين حين يختلفان ببت واحد بالضبط: الناتج مخطط مكعب. ودورة هاملتون فيه، مثل ⁦000, 001, 011, 010, 110, 111, 101, 100⁩، تسرد الرموز الثمانية بحيث يختلف كل رمز عن سابقه ببت واحد فقط. وهذه القائمة هي رمز غراي، المسمى باسم فرانك غراي من مختبرات بل، الذي وصفه في براءة اختراع قُدّمت عام 1947. ولكل مكعب فائق رمز كهذا: اكتب الرموز ببت أقل، ثم اكتب القائمة نفسها بالمقلوب، وضع 0 قبل النصف الأول و1 قبل النصف الثاني. وتستعمل أجهزة الترميز الدوّارة رموز غراي حتى لا تخطئ قراءة تؤخذ بين وضعين بأكثر من خطوة واحدة. وللمكعب 6 دورات هاملتون، وللمكعب الفائق ذي الأربع بتات 1٬344.

جرّبه بنفسك

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

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

هل المخطط الذي له دارة أويلر هاملتوني أيضًا، أم العكس؟

لا يلزم أحدهما من الآخر. فربطة الفراشة، وهي مثلثان يشتركان في رأس، لها دارة أويلر لأن كل درجة فيها زوجية، لكن ليست لها دورة هاملتون لأن الرأس المشترك سيلزم المرور به مرتين. والمخطط التام ⁦K₄⁩ له دورات هاملتون، لكن رؤوسه الأربعة كلها من الدرجة 3، فليست له دارة أويلر.

ألا يستطيع الحاسوب تجربة كل الترتيبات ببساطة؟

في المخططات الصغيرة فقط. فعدد ترتيبات ⁦n⁩ من الرؤوس هو ⁦n!⁩، أي نحو ⁦2٫4 × 10¹⁸⁩ عند 20 رأسًا. والتراجع أفضل من ذلك بكثير، لأنه يسير على الأضلاع فقط ويتخلى عن المسار الجزئي فور أن يعلق: فهو يجد الدورات الثلاثين كلها في المجسم الاثني عشري ذي العشرين رأسًا في نحو 1٬400 خطوة. ومع ذلك ينمو عدد المسارات الجزئية أسّيًا في بعض المخططات، ولا تُعرف طريقة تتفادى ذلك في كل مخطط.

هل مسألة مسار هاملتون أسهل من مسألة الدورة؟

لا، كلتاهما تامة في NP. وكل منهما تتحول إلى الأخرى: أضف رأسًا جديدًا موصولًا بكل رأس قديم، فيكون للمخطط القديم مسار هاملتون تمامًا حين تكون للمخطط الجديد دورة هاملتون. وفي الاتجاه الآخر تصير مسألة الدورة مسألة مسار بإضافة نسخة من أحد الرؤوس لها الجيران أنفسهم، ثم تعليق رأس طرفي جديد بالرأس وآخر بنسخته.

لماذا يجب أن تبدأ جولة الحصان على رقعة ⁦5 × 5⁩ من لون الزوايا؟

من المربعات الخمسة والعشرين، 13 بلون الزوايا و12 باللون الآخر، والحصان يبدّل اللون في كل نقلة. والجولة على 25 مربعًا تتناوب الألوان، فتبدأ وتنتهي على اللون الأكثر مربعات. ويجد التطبيق كل الجولات المفتوحة على رقعة ⁦5 × 5⁩ وعددها 1٬728، أي 864 إذا عُدّت الجولة وعكسها واحدة، وكل جولة منها تبدأ وتنتهي على مربع بلون الزوايا.

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

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

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