מסלול המילטוני – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף
דיוק קישור פנימי
תגיות: עריכה ממכשיר נייד עריכה דרך האתר הנייד
Rnaveh (שיחה | תרומות)
מ המליטוני -> המילטוני
שורה 3:
ב[[תורת הגרפים]], '''מסלול המילטוני''' הוא [[מסלול (תורת הגרפים)|מסלול]] בגרף [[גרף מכוון|מכוון]] או [[גרף לא מכוון|בלתי מכוון]] העובר בכל צומת בדיוק פעם אחת. '''מעגל המילטוני''' הוא מסלול בגרף העובר בכל צומת פעם אחת פרט לצומת שממנו יצא (ואז הוא עובר בו בדיוק פעמיים - בהתחלה ובסוף).
 
המונחים קרויים על שמו של [[ויליאם רואן המילטון]], מתמטיקאי ואסטרונום [[אירלנד|אירי]], אשר המציא ב-1857 משחק המבוסס על מציאת מעגל המילטוני בגרף ה[[דודקהדרון]]{{הערה|1=ראו צילומים של המשחק {{קישור כללי|כתובת=https://www.puzzlemuseum.com/month/picm02/200207icosian.htm|כותרת=Sir William Hamilton's Icosian Game and Traveller's Dodecahedron Puzzle.|תאריך_וידוא=2019-03-31|אתר=www.puzzlemuseum.com}}}}. [[שעשוע מתמטי]] אחר הקשור במסלולים ומעגלים המילטוניים היא [[חידת מסע הפרש]] ב[[שחמט]], בה יש למצוא מסלול המליטוניהמילטוני ב[[גרף פרש]]. על בעיה זאת כתבו [[לאונרד אוילר]] ו[[ונדרמונדה]] כבר ב[[המאה השמונה עשרה|מאה ה-18]]{{הערה|1=לסקירה היסטורית ראו Norman Biggs, E. Keith Lloyd, Robin J. Wilson '''Graph theory, 1736-1936''' Oxford University Press 1976 }}.
 
==התנאים לקיום מסלול==