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