المسار الهاميلتوني

في مجال نظرية المخططات الرياضية ، يُعرف المسار الهاميلتوني (أو المسار القابل للتتبع ) بأنه مسار في مخطط غير موجه أو موجه يمر بكل رأس مرة واحدة فقط. أما الدورة الهاميلتونية (أو الدائرة الهاميلتونية ) فهي دورة تمر بكل رأس مرة واحدة فقط. يمكن إكمال المسار الهاميلتوني الذي يبدأ وينتهي عند رأسين متجاورين بإضافة حافة واحدة لتشكيل دورة هاميلتونية، كما أن إزالة أي حافة من دورة هاميلتونية ينتج عنه مسار هاميلتوني. تُصنف المسائل الحسابية المتعلقة بتحديد وجود هذه المسارات والدورات في المخططات ضمن فئة المسائل NP-complete ؛ راجع مسألة المسار الهاميلتوني لمزيد من التفاصيل.

سُميت المسارات والدورات الهاميلتونية نسبةً إلى ويليام روان هاميلتون ، مخترع لعبة الإيكوسيان ، المعروفة أيضًا باسم لغز هاميلتون ، والتي تتضمن إيجاد دورة هاميلتونية في الرسم البياني لحواف المجسم ذي الاثني عشر وجهًا . حلّ هاميلتون هذه المسألة باستخدام حساب الإيكوسيان ، وهو بنية جبرية تعتمد على جذور الوحدة وتتشابه في كثير من جوانبها مع الكواترنيونات (التي اخترعها هاميلتون أيضًا). لا يُمكن تعميم هذا الحل على الرسوم البيانية العشوائية.

على الرغم من تسميتها نسبةً إلى هاميلتون، فقد دُرست دورات هاميلتون في المجسمات متعددة الأوجه قبل عام من ذلك على يد توماس كيركمان ، الذي قدم على وجه الخصوص مثالًا لمجسم متعدد الأوجه خالٍ من دورات هاميلتون. ^{[ 1 ]} وحتى قبل ذلك، دُرست دورات هاميلتون ومساراتها في رسم بياني لحصان رقعة الشطرنج ، أو ما يُعرف بجولة الحصان ، في القرن التاسع في الرياضيات الهندية على يد رودراتا ، وفي نفس الفترة تقريبًا في الرياضيات الإسلامية على يد العدلي الرومي . وفي أوروبا في القرن الثامن عشر، نُشرت جولات الحصان على يد أبراهام دي مويفر وليونهارد أويلر . ^{[ 2 ]}

التعريفات

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

الدورة الهاميلتونية ، أو الدائرة الهاميلتونية ، أو جولة الرؤوس ، أو دورة الرسم البياني، هي دورة تزور كل رأس مرة واحدة فقط. ويُطلق على الرسم البياني الذي يحتوي على دورة هاميلتونية اسم الرسم البياني الهاميلتوني .

يمكن تعريف مفاهيم مماثلة للرسوم البيانية الموجهة ، حيث لا يمكن تتبع كل حافة (قوس) من مسار أو دورة إلا في اتجاه واحد (أي أن الرؤوس متصلة بالأسهم ويتم تتبع الحواف "من الذيل إلى الرأس").

التفكيك الهاميلتوني هو تفكيك حواف الرسم البياني إلى دوائر هاميلتونية.

متاهة هاميلتون هي نوع من الألغاز المنطقية التي يكون الهدف منها إيجاد دورة هاميلتونية فريدة في رسم بياني مُعطى. ^{[ 3 ]}^{[ 4 ]}

أمثلة

الرسم البياني الكامل الذي يحتوي على أكثر من رأسين هو رسم بياني هاميلتوني
كل رسم بياني دوري هو هاميلتوني
كل بطولة لها عدد فردي من المسارات الهاميلتونية ( ريدي 1934)
كل جسم أفلاطوني ، إذا اعتبرنا رسمًا بيانيًا، هو هاميلتوني ^{[ 5 ]}
إن الرسم البياني لكايلي لمجموعة كوكسيتر المحدودة هو هاميلتوني (انظر تخمين لوفاس للحصول على ادعاء أكثر عمومية)
تُعتبر مخططات كايلي على المجموعات العديمة القوة ذات المجموعة الفرعية التبادلية الدورية هاميلتونية. ^{[ 6 ]}
الرسم البياني العكسي لمضلع محدب، أو ما يعادله، الرسم البياني الدوراني للأشجار الثنائية ، هو رسم بياني هاميلتوني. ^{[ 7 ]}^{[ 8 ]}

ملكيات

يمكن تحويل أي دورة هاميلتونية إلى مسار هاميلتوني عن طريق إزالة أحد حوافها، ولكن لا يمكن تمديد المسار الهاميلتوني إلى دورة هاميلتونية إلا إذا كانت نقاط نهايته متجاورة.

جميع الرسوم البيانية الهاميلتونية ثنائية الاتصال ، ولكن الرسم البياني ثنائي الاتصال ليس بالضرورة أن يكون هاميلتونيًا (انظر، على سبيل المثال، الرسم البياني لبيترسن ). ^{[ 9 ]}

يحتوي الرسم البياني الأويلري G $($ وهو رسم بياني متصل تكون فيه درجة كل رأس زوجية) بالضرورة على مسار أويلري، وهو مسار مغلق يمر عبر كل حافة من حواف $G$ مرة واحدة فقط. يتوافق هذا المسار مع دورة هاميلتونية في الرسم البياني الخطي $L (G)$ ، لذا فإن الرسم البياني الخطي لكل رسم بياني أويلري هو رسم بياني هاميلتوني. قد تحتوي الرسوم البيانية الخطية على دورات هاميلتونية أخرى لا تتوافق مع مسارات أويلرية، وعلى وجه الخصوص، فإن الرسم البياني الخطي $L (G)$ لكل رسم بياني هاميلتوني $G$ هو نفسه رسم بياني هاميلتوني، بغض النظر عما إذا كان الرسم البياني $G$ أويلريًا أم لا. ^{[ 10 ]}

تكون البطولة ( التي تحتوي على أكثر من رأسين) هاميلتونية إذا وفقط إذا كانت متصلة بقوة .

عدد دورات هاميلتون المختلفة في رسم بياني كامل غير موجه ذي $n$ رأسًا هو $(n - 1)! / 2 ،$ وفي رسم بياني كامل موجه ذي $n$ $رأسًا$ هو $($ $n - 1)!.$ وتفترض هذه الحسابات عدم احتساب الدورات المتشابهة باستثناء نقطة بدايتها بشكل منفصل.

نظرية بوندي-شفاتال

تم تقديم أفضل توصيف لدرجة رؤوس الرسوم البيانية الهاميلتونية في عام 1972 من خلال نظرية بوندي - شفاتال ، التي تعمم نتائج سابقة لـ جي إيه ديراك (1952) وأويستين أور . ويمكن اشتقاق كلتا النظريتين، ديراك وأور، من نظرية بوسا (1962). وقد دُرست خاصية الهاميلتونية على نطاق واسع فيما يتعلق بمعايير مختلفة مثل كثافة الرسم البياني ، والمتانة ، والرسوم البيانية الفرعية المحظورة ، والمسافة ، وغيرها من المعايير. ^{[ 11 ]} تنص نظريتا ديراك وأور بشكل أساسي على أن الرسم البياني يكون هاميلتونيًا إذا كان يحتوي على عدد كافٍ من الحواف .

تعمل نظرية بوندي-تشفاتال على إغلاق $cl(G)$ للرسم البياني $G$ الذي يحتوي على $n$ رأسًا، والذي يتم الحصول عليه عن طريق إضافة حافة جديدة $uv$ بشكل متكرر تربط زوجًا غير متجاور من الرؤوس $u$ و $v$ مع $deg(v) + deg(u) \geq n$ حتى لا يتم العثور على المزيد من الأزواج بهذه الخاصية.

نظرية بوندي-تشفاتال (1976) - يكون الرسم البياني هاميلتونيًا إذا وفقط إذا كان إغلاقه هاميلتونيًا.

بما أن الرسوم البيانية الكاملة هي رسوم بيانية هاميلتونية، فإن جميع الرسوم البيانية التي يكون إغلاقها كاملاً هي رسوم بيانية هاميلتونية، وهو محتوى النظريات السابقة التالية لديراك وأور.

نظرية ديراك (1952) - رسم بياني بسيط ذو $n$ رأسًا ( $n\geq 3$ تكون دالة هاميلتونية إذا كان لكل رأس درجة ${\tfrac {n}{2}}$ أو أكبر.

نظرية أور (1960) - رسم بياني بسيط ذو $n$ رأسًا ( $n\geq 3$ تكون دالة هاميلتونية إذا كان مجموع درجات كل زوج من الرؤوس غير المتجاورة يساوي $n$ أو أكبر.

يمكن اعتبار النظريات التالية بمثابة نسخ موجهة:

غويلا-حوري (1960) - الرسم البياني الموجه البسيط المتصل بقوة والذي يحتوي على $n$ رأسًا يكون هاميلتونيًا إذا كان لكل رأس درجة كاملة أكبر من أو تساوي $n$ .

مينيل (1973) - الرسم البياني البسيط الموجه ذو الاتصال القوي والذي يحتوي على $n$ رأسًا يكون هاميلتونيًا إذا كان مجموع الدرجات الكاملة لكل زوج من الرؤوس المختلفة غير المتجاورة أكبر من أو يساوي $2n-1$

يجب مضاعفة عدد الرؤوس لأن كل حافة غير موجهة تتوافق مع قوسين موجهين، وبالتالي فإن درجة الرأس في الرسم البياني الموجه هي ضعف الدرجة في الرسم البياني غير الموجه.

رحمان – كايكوباد (2005) - يحتوي الرسم البياني البسيط ذو $n$ رأسًا على مسار هاميلتوني إذا كان مجموع درجات كل زوج من الرؤوس غير المتجاورة وطول أقصر مسار بينهما أكبر من $n$ . ^{[ 12 ]}

لا يمكن للنظرية المذكورة أعلاه إلا أن تعترف بوجود مسار هاميلتوني في الرسم البياني وليس دورة هاميلتونية.

العديد من هذه النتائج لها نظائر في الرسوم البيانية الثنائية المتوازنة ، حيث تتم مقارنة درجات الرؤوس بعدد الرؤوس على جانب واحد من التقسيم الثنائي بدلاً من عدد الرؤوس في الرسم البياني بأكمله. ^{[ 13 ]}

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

نظرية — يحتوي التثليث المستوي رباعي الاتصال على دورة هاميلتونية. ^{[ 14 ]}

نظرية — يحتوي الرسم البياني المستوي ذو الاتصال الرباعي على دورة هاميلتونية. ^{[ 15 ]}

متعددة حدود دورة هاميلتون

التمثيل الجبري لدورات هاميلتون لمخطط موجه مُثقَّل (حيث تُخصَّص أوزان لأقواسه من حقل أساسي مُحدَّد) هو متعدد حدود دورة هاميلتون لمصفوفة التجاور المُثقَّلة، والذي يُعرَّف بأنه مجموع حاصل ضرب أوزان أقواس دورات هاميلتون للمخطط الموجه. لا يساوي متعدد الحدود هذا الصفر كدالة في أوزان الأقواس إلا إذا كان المخطط الموجه هاميلتونيًا. وقد أوضح غريغوري كوجان العلاقة بين التعقيدات الحسابية لحسابه وحساب الثابت . ^{[ 16 ]}

انظر أيضاً

تخمين بارنيت ، مسألة مفتوحة حول خاصية الهاميلتونية للرسوم البيانية متعددة السطوح المكعبة ثنائية الأجزاء
المسار الأويلري ، هو مسار يمر عبر جميع الحواف في الرسم البياني
نظرية فليشنر ، حول المربعات الهاميلتونية للرسوم البيانية
قانون غراي
تُقدّم نظرية غرينبيرغ شرطًا ضروريًا لوجود دورة هاميلتونية في الرسوم البيانية المستوية
مشكلة المسار الهاميلتوني ، وهي مشكلة حسابية تتمثل في إيجاد المسارات الهاميلتونية
الرسم البياني شبه الهاميلتوني ، هو رسم بياني غير هاميلتوني يكون فيه كل رسم بياني فرعي محذوف منه رأس هاميلتونيًا.
جولة الفارس ، دورة هاميلتونية في رسم الفارس البياني
ترميز LCF للرسوم البيانية المكعبة الهاميلتونية .
يفترض لوفاس أن الرسوم البيانية المتعدية على الرؤوس هي رسوم بيانية هاميلتونية
الرسم البياني الدوري الشامل ، هو رسم بياني يحتوي على دورات بجميع الأطوال بما في ذلك دورة هاميلتونية
الترابط الشامل ، وهو تعزيز لكل من الترابط الدوري الشامل والترابط الهاميلتوني
جسور كونيغسبرغ السبعة
معامل التقصير ، وهو مقياس عددي لمدى بُعد الرسوم البيانية في عائلة ما عن الهاميلتوني
مسار الثعبان في الصندوق ، أطول مسار مستحث في مكعب فائق
خوارزمية شتاينهاوس-جونسون-تروتر لإيجاد مسار هاميلتوني في مجسم تبادلي
الرسم البياني شبه الهاميلتوني ، هو رسم بياني فرعي من رسم بياني هاميلتوني مستوٍ
تخمين تايت (الذي ثبت الآن خطأه) بأن الرسوم البيانية متعددة السطوح المنتظمة من الدرجة 3 هي رسوم بيانية هاميلتونية
مشكلة البائع المتجول
رسوم هاريس البيانية ، وهي عائلة من الرسوم البيانية التي تتميز بصعوبتها، وكونها رسوم أويلرية ، وغير هاميلتونية.

ملحوظات

↑ بيغز، إن إل (1981)، "تي بي كيركمان، عالم رياضيات"، نشرة جمعية لندن الرياضية ، 13 (2): 97-120 ، doi : 10.1112/blms/13.2.97 ، MR 0608093 .
↑ واتكينز، جون ج. (2004)، "الفصل 2: جولات الفارس"، عبر الرقعة: رياضيات مسائل رقعة الشطرنج ، مطبعة جامعة برينستون، ص 25-38 ، ISBN 978-0-691-15498-5.
^ دي رويتر، يوهان (2017). متاهات هاملتون – دليل المبتدئين .
↑ فريدمان، إريك. "متاهات هاميلتونية" . قصر ألغاز إريك . مؤرشف من الأصل في 16 أبريل 2016. تم الاطلاع عليه في 23 أكتوبر 2025 .
↑ غاردنر، م. "الألعاب الرياضية: حول التشابه الملحوظ بين لعبة إيكوسيان وأبراج هانوي." مجلة ساينتفك أمريكان 196، 150-156، مايو 1957
↑ غادربور، إي.؛ موريس، د. و. (2014). "مخططات كايلي على مجموعات نيلبوتنت ذات مجموعة فرعية مبدلة دورية هي هاميلتونية". آرس ماتيماتيكا كونتمبورانيا . 7 (1): 55-72 . arXiv : 1111.6216 . doi : 10.26493/1855-3974.280.8d3 . S2CID 57575227 .
↑ لوكاس، جوان م. (1987)، "مخطط دوران الأشجار الثنائية هو هاميلتوني"، مجلة الخوارزميات ، 8 (4): 503-535 ، doi : 10.1016/0196-6774(87)90048-4
↑ هورتادو، فيران ؛ نوي، مارك (1999)، "رسم بياني لتثليثات مضلع محدب وشجرة التثليثات"، الهندسة الحسابية ، 13 (3): 179-188 ، doi : 10.1016/S0925-7721(99)00016-4
↑ إريك دبليو. وايسشتاين . "الرسم البياني ثنائي الاتصال" . وولفرام ماث وورلد.
↑ بالاكريشنان، ر.؛ رانغاناثان، ك. (2012)، "النتيجة 6.5.5"، كتاب في نظرية الرسم البياني ، سبرينغر، ص 134، ISBN 9781461445296.
↑ غولد، رونالد ج. (8 يوليو 2002). "تطورات في مسألة هاميلتون - دراسة استقصائية" (ملف PDF) . جامعة إيموري. مؤرشف من الأصل (ملف PDF) بتاريخ 13 يوليو 2018. تم الاطلاع عليه بتاريخ 10 ديسمبر 2012 .
↑ رحمن، م.س.؛ كايكوباد، م. (أبريل 2005). "حول دورات هاميلتون ومسارات هاميلتون". رسائل معالجة المعلومات . 94 : 37-41 . doi : 10.1016/j.ipl.2004.12.002 .
↑ مون، ج.؛ موسر، ل. (1963)، "حول الرسوم البيانية الثنائية الهاميلتونية"، مجلة إسرائيل للرياضيات ، 1 (3): 163-165 ، doi : 10.1007/BF02759704 ، MR 0161332 ، S2CID 119358798
↑ ويتني، هاسلر (1931)، "نظرية حول الرسوم البيانية"، حوليات الرياضيات ، السلسلة الثانية، 32 (2): 378-390 ، doi : 10.2307/1968197 ، JSTOR 1968197 ، MR 1503003
↑ توت، دبليو تي (1956)، "نظرية حول الرسوم البيانية المستوية"، معاملات الجمعية الأمريكية للرياضيات ، 82 : 99-116 ، doi : 10.1090/s0002-9947-1956-0081471-8
↑ كوجان، غريغوري (1996). "حساب الثوابت على حقول ذات خاصية 3: أين ولماذا يصبح الأمر صعبًا". وقائع المؤتمر السابع والثلاثين حول أسس علوم الحاسوب . ص 108-114 . doi : 10.1109/SFCS.1996.548469 . ISBN 0-8186-7594-2. S2CID 39024286 .

مراجع

بيرج، كلود ؛ غويلا-حوري، أ. (1962)، البرمجة والألعاب وشبكات النقل ، نيويورك: أبناء، شركة.
دي ليون، ميليسا (2000)، "دراسة للشروط الكافية لدورات هاميلتون" (ملف PDF) ، مجلة روز-هولمان للرياضيات الجامعية ، 1 (1)، مؤرشفة من الأصل (ملف PDF) بتاريخ 22-12-2012 ، تم استرجاعها بتاريخ 28-11-2005.
ديراك، جي إيه (1952)، "بعض النظريات حول الرسوم البيانية المجردة"، وقائع الجمعية الرياضية في لندن ، السلسلة الثالثة، 2 : 69-81 ، doi : 10.1112/plms/s3-2.1.69 ، MR 0047308 .
هاميلتون، ويليام روان (1856)، "مذكرة بشأن نظام جديد لجذور الوحدة"، المجلة الفلسفية ، 12 : 446.
هاميلتون، ويليام روان ( 1858)، "شرح حساب التفاضل والتكامل الإيكوزي"، وقائع الأكاديمية الملكية الأيرلندية ، 6 : 415-416.
Meyniel، M. (1973)، “Une condition suffisante d’existence d’un Circuit hamiltonien dans un graphe orienté”، مجلة النظرية التوافقية ، السلسلة ب، 14 (2): 137–147 ، دوى : 10.1016 / 0095-8956(73)90057-9 ، MR 0317997 .
أور، أويستين (1960)، "ملاحظة حول دوائر هاميلتون"، المجلة الرياضية الأمريكية الشهرية ، 67 (1): 55، doi : 10.2307/2308928 ، JSTOR 2308928 ، MR 0118683 .
Pósa، L. (1962)، “نظرية تتعلق بخطوط هاملتون”، Magyar Tud. أكاد. حصيرة. كوتاتو إنت. كوزل. , 7 : 225 – 226 , م 0184876 .

روابط خارجية

وايسشتاين، إريك دبليو. "دورة هاميلتون" . عالم الرياضيات .
جولة أويلر ودراجات هاميلتون

[1] بيغز، إن إل (1981)، "تي بي كيركمان، عالم رياضيات"، نشرة جمعية لندن الرياضية ، 13 (2): 97-120 ، doi : 10.1112/blms/13.2.97 ، MR 0608093 .

[2] واتكينز، جون ج. (2004)، "الفصل 2: جولات الفارس"، عبر الرقعة: رياضيات مسائل رقعة الشطرنج ، مطبعة جامعة برينستون، ص 25-38 ، ISBN 978-0-691-15498-5.

[3] دي رويتر، يوهان (2017). متاهات هاملتون – دليل المبتدئين .

[4] فريدمان، إريك. "متاهات هاميلتونية" . قصر ألغاز إريك . مؤرشف من الأصل في 16 أبريل 2016. تم الاطلاع عليه في 23 أكتوبر 2025 .

[5] غاردنر، م. "الألعاب الرياضية: حول التشابه الملحوظ بين لعبة إيكوسيان وأبراج هانوي." مجلة ساينتفك أمريكان 196، 150-156، مايو 1957

[6] غادربور، إي.؛ موريس، د. و. (2014). "مخططات كايلي على مجموعات نيلبوتنت ذات مجموعة فرعية مبدلة دورية هي هاميلتونية". آرس ماتيماتيكا كونتمبورانيا . 7 (1): 55-72 . arXiv : 1111.6216 . doi : 10.26493/1855-3974.280.8d3 . S2CID 57575227 .

[7] لوكاس، جوان م. (1987)، "مخطط دوران الأشجار الثنائية هو هاميلتوني"، مجلة الخوارزميات ، 8 (4): 503-535 ، doi : 10.1016/0196-6774(87)90048-4

[8] هورتادو، فيران ؛ نوي، مارك (1999)، "رسم بياني لتثليثات مضلع محدب وشجرة التثليثات"، الهندسة الحسابية ، 13 (3): 179-188 ، doi : 10.1016/S0925-7721(99)00016-4

[9] إريك دبليو. وايسشتاين . "الرسم البياني ثنائي الاتصال" . وولفرام ماث وورلد.

[10] بالاكريشنان، ر.؛ رانغاناثان، ك. (2012)، "النتيجة 6.5.5"، كتاب في نظرية الرسم البياني ، سبرينغر، ص 134، ISBN 9781461445296.

[11] غولد، رونالد ج. (8 يوليو 2002). "تطورات في مسألة هاميلتون - دراسة استقصائية" (ملف PDF) . جامعة إيموري. مؤرشف من الأصل (ملف PDF) بتاريخ 13 يوليو 2018. تم الاطلاع عليه بتاريخ 10 ديسمبر 2012 .

[12] رحمن، م.س.؛ كايكوباد، م. (أبريل 2005). "حول دورات هاميلتون ومسارات هاميلتون". رسائل معالجة المعلومات . 94 : 37-41 . doi : 10.1016/j.ipl.2004.12.002 .

[13] مون، ج.؛ موسر، ل. (1963)، "حول الرسوم البيانية الثنائية الهاميلتونية"، مجلة إسرائيل للرياضيات ، 1 (3): 163-165 ، doi : 10.1007/BF02759704 ، MR 0161332 ، S2CID 119358798

[14] ويتني، هاسلر (1931)، "نظرية حول الرسوم البيانية"، حوليات الرياضيات ، السلسلة الثانية، 32 (2): 378-390 ، doi : 10.2307/1968197 ، JSTOR 1968197 ، MR 1503003

[15] توت، دبليو تي (1956)، "نظرية حول الرسوم البيانية المستوية"، معاملات الجمعية الأمريكية للرياضيات ، 82 : 99-116 ، doi : 10.1090/s0002-9947-1956-0081471-8

[16] كوجان، غريغوري (1996). "حساب الثوابت على حقول ذات خاصية 3: أين ولماذا يصبح الأمر صعبًا". وقائع المؤتمر السابع والثلاثين حول أسس علوم الحاسوب . ص 108-114 . doi : 10.1109/SFCS.1996.548469 . ISBN 0-8186-7594-2. S2CID 39024286 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗