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