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