מסלול המילטוני

בתורת הגרפים, מסלול המילטוני הוא מסלול בגרף מכוון או בלתי מכוון העובר בכל צומת בדיוק פעם אחת. מעגל המילטוני הוא מסלול בגרף העובר בכל צומת פעם אחת פרט לצומת שממנו יצא (ואז הוא עובר בו בדיוק פעמיים - בהתחלה ובסוף).

מעגל המילטוני על הקשתות של תריסרון

מסע הפרש במסלול סגור

שלוש דוגמאות בגרף רשת 8 על 8

המונחים קרויים על שמו של ויליאם רואן המילטון, מתמטיקאי ואסטרונום אירי, אשר המציא ב-1857 משחק המבוסס על מציאת מעגל המילטוני בגרף התריסרון^[1]. שעשוע מתמטי אחר הקשור במסלולים ומעגלים המילטוניים היא חידת מסע הפרש בשחמט, בה יש למצוא מסלול המילטוני בגרף פרש. על בעיה זאת כתבו לאונרד אוילר ואלכסנדר ונדרמונד כבר במאה ה-18^[2].

התנאים לקיום מסלול

ידועים מספר תנאים המבטיחים קיום מסלול או מעגל המילטוניים, אולם הם רחוקים מאפיון מלא (ראו הפסקה על סיבוכיות). כך, ידוע שבגרף תחרות (שהוא גרף מכוון), תמיד יש מסלול המילטוני ויש מעגל המילטוני אם ורק אם הגרף קשיר היטב. בגרפים צפופים מאוד מובטח כי יהיה מסלול המילטוני. כך, למשל, משפט אור הקובע כי לגרף עם ${\displaystyle n\geq 3}$ קודקודים אם לכל שני קודקודים x,y שאינם שכנים n ≤ deg(x) + deg(y) אזי הגרף מכיל מעגל המילטוני. ונובע ממנו משפט דירק שקובע כי גרף עם ${\displaystyle n\geq 3}$ צמתים בו הדרגה המינימלית היא לפחות ${\displaystyle \displaystyle n/2}$ הוא בהכרח המילטוני. בהיפרקוביה מכל מימד יש מעגל המילטוני והמעגלים הללו מתאימים לקוד גריי.

בגרף מקרי ידועים ערכים מדויקים של הסף ממנו ניתן לצפות כי יהיה מסלול המילטוני בגרף בהסתברות גבוהה. בגרף מקרי עם ${\displaystyle \displaystyle n}$ צמתים ו-${\displaystyle {\frac {1}{2}}n\log n+{\frac {1}{2}}n\log \log n+c\cdot n}$ קשתות הנבחרות באקראי, ההסתברות כי יהיה המילטוני שואפת ל-${\displaystyle \,e^{e^{-2c}}}$^[3]. אם מוסיפים את הקשתות בזו אחר זו עד שהדרגה המינימלית מגיעה ל-2 (זהו תנאי הכרחי לקיומו של מעגל המילטוני), אז הסיכוי לכך שהגרף אינו המילטוני שואף לאפס כאשר n גדל.

סיבוכיות ואלגוריתמים

מספר בעיות הנוגעות למסלולים המילטוניים הן בעיות NP - שלמות, ומכאן שלא ידוע אלגוריתם יעיל לפתרונן. כאלו הן, למשל, מציאת מסלול המילטוני בגרף שבו קיים מסלול כזה; הקביעה האם קיים מסלול המילטוני בגרף נתון. הבעיות נכללות ב-רשימה המקורית של 21 הבעיות של ריצ'רד קארפ. הבעיה היא שלמה ל-NP אף בגרפים מישוריים שדרגתם שלוש^[4]. בעיית ספירת המסלולים ההמילטוניים בגרף היא שלמה ל-#P. בעיית מציאת מסלול המילטוני בגרף קשורה בקשר הדוק לבעיית מציאת מעגל המילטוני בגרף - גרף בעל מעגל המילטוני יכול להתקבל מגרף בעל מסלול המילטוני על ידי הוספת צומת חדש לגרף שמחובר לכל שאר הצמתים (זה יהיה צומת המוצא והסיום). בעיית מציאת מעגל המילטוני היא מקרה פרטי של בעיית הסוכן הנוסע, כאשר משקלי כל הקשתות הם 1.

לבעיית מציאת מסלול המילטוני יש אלגוריתם שסיבוכיותו מעריכית בלבד, (ולא ${\displaystyle \displaystyle O(n!)}$ כפי שיהיה לאלגוריתם שיעבור על כל המסלולים האפשריים), באמצעות תכנות דינמי^[5]. בגרפים מקריים ידועים אלגוריתמים יעילים המוצאים את המעגל ההמילטוני בהסתברות הצלחה הדומה להסתברות שהמעגל קיים.

בעיית מציאת מסלול המילטוני הייתה הדוגמה הראשונה עבורה הודגם חישוב מולקולרי (מחשוב DNA) העושה שימוש ב-DNA ובביולוגיה מולקולרית, במקום באמצעים האלקטרוניים הרגילים. ב-1994 הדגים לאונרד אדלמן מאוניברסיטת דרום קליפורניה שימוש ב-DNA לצורך פתרון הבעיה על גרף עם שבעה צמתים.

ראו גם

• מסלול אוילרי
• בעיית הסוכן הנוסע
• גרף תחרות

לקריאה נוספת

• הפרק Basic Graph Theory: Paths and Circuits ב-Ronald L. Graham,, Handbook of Combinatorics, MIT Press, 1995.

קישורים חיצוניים

מדיה וקבצים בנושא מסלול המילטוני בוויקישיתוף

• מסלול המילטוני, באתר MathWorld (באנגלית)
• מסלול המילטוני, באתר אנציקלופדיה בריטניקה (באנגלית)

הערות שוליים

1. ראו צילומים של המשחק Sir William Hamilton's Icosian Game and Traveller's Dodecahedron Puzzle., www.puzzlemuseum.com
2. לסקירה היסטורית ראו Norman Biggs, E. Keith Lloyd, Robin J. Wilson Graph theory, 1736-1936 Oxford University Press 1976
3. János Komlós and Endre Szemerédi, Limit distribution for the existence of hamiltonian cycles in a random graph, Discrete Mathematics Volume 43, Issue 1, 1983, Pages 55-63
4. Michael R. Garey, David S. Johnson, Larry J. Stockmeyer, Some Simplified NP-Complete Graph Problems, Theor. Comput. Sci. 1(3), 237-267, 1976.
5. Michael Held, Richard M. Karp, A Dynamic Programming Approach to Sequencing Problems A Dynamic Programming Approach to Sequencing Problems, Journal of the Society for Industrial and Applied Mathematics, Vol. 10, No. 1 (Mar., 1962), pp. 196-210