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