הגשרים של קניגסברג – הבדלי גרסאות

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

בשביל לפתור את החידה מספיק לייצג את העיר באמצעות [[גרף (תורת הגרפים)|גרף]]. כל אחד מארבעת חלקי העיר נייצג באמצעות [[צומת (תורת הגרפים)|צומת]] כחול, וכל אחד מבין שבעת הגשרים ייוצג על ידי [[קשת (תורת הגרפים)|קשת]], כמתואר שחורהבציור.

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

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