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

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

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

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

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

מתי קיים מסלול?

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

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

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

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

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

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

ראו גם

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

לקריאה נוספת

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

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

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