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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
מעגל המילטוני על הקשתות של דודקהדרון
מסע הפרש במסלול סגור

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

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

מתי קיים מסלול?[עריכת קוד מקור | עריכה]

ידועים מספר תנאים המבטיחים קיום מסלול או מעגל המילטוניים, אולם הם רחוקים מאפיון מלא (ראו הפסקה על סיבוכיות). כך, ידוע שבגרף תחרות (שהוא גרף מכוון), תמיד יש מסלול המילטוני ויש מעגל המילטוני אם ורק אם הגרף קשיר היטב. בגרפים צפופים מאוד מובטח כי יהיה מסלול המילטוני. כך, למשל, משפט דיראק קובע כי גרף עם n \ge 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}} [3]. אם מוסיפים את הקשתות בזו אחר זו עד שהדרגה המינימלית מגיעה ל-2 (זהו תנאי הכרחי לקיומו של מעגל המילטוני), אז הסיכוי לכך שהגרף אינו המילטוני שואף לאפס כאשר n גדל.

סיבוכיות ואלגוריתמים[עריכת קוד מקור | עריכה]

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

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

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

ראו גם[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ ראו צילומים של המשחק [1]
  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

לקריאה נוספת[עריכת קוד מקור | עריכה]

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