צילום: Alexander Grebenkov, Wikimedia Commons (CC BY 3.0)
בתחילת המאה השמונה עשרה שכנה העיר קניגסברג - היום קלינינגרד - על שני עברי נהר הפרגל.
הנהר חוצה את העיר ויוצר בה ארבעה חלקי יבשה: הגדה הצפונית, הגדה הדרומית, האי קנייפהוף שבמרכז, ורצועת יבשה נוספת במזרח, במקום שבו שני זרועות הנהר מתאחדות.
ארבעת החלקים חוברו זה לזה בשבעה גשרים. האי המרכזי היה מחובר בחמישה גשרים: שניים אל הגדה הצפונית, שניים אל הגדה הדרומית ואחד אל החלק המזרחי. החלק המזרחי היה מחובר גם הוא בשני גשרים נוספים, אחד לכל גדה.
תושבי העיר נהגו לטייל בשבתות ושאלו את עצמם שאלה שנראתה כמו משחק:
השאלה: האם אפשר לצאת לטיול בעיר, לעבור על כל אחד משבעת הגשרים בדיוק פעם אחת, ולא לעבור על אף גשר פעמיים? (מותר לסיים במקום אחר מזה שממנו יצאתם.)
אל תנסו למפות רחובות. לחידה אין שום קשר למרחקים, לצורת האי או לאורכי הגשרים - אלא רק לשאלה מה מחובר למה. ציירו ארבע נקודות, וקו לכל גשר.
ספרו כמה גשרים נוגעים בכל חלק יבשה. עכשיו חשבו על חלק יבשה שאינו נקודת ההתחלה ואינו נקודת הסיום: בכל פעם שנכנסים אליו חייבים גם לצאת ממנו, כלומר הגשרים שלו מתחלקים לזוגות. מה זה אומר על מספר הגשרים שלו?
לא, טיול כזה אינו אפשרי - וזו אינה שאלה של מזל או של חוסר כישרון, אלא הוכחה מלאה.
בשנת 1736 ניגש לבעיה לאונרד אוילר, והצעד המכריע שלו היה לזרוק את המפה. הוא החליף כל חלק יבשה בנקודה וכל גשר בקו המחבר שתי נקודות. המרחקים, הצורות והגדלים אינם רלוונטיים - רק החיבורים.
עכשיו נספור כמה גשרים נוגעים בכל חלק יבשה: האי המרכזי - 5 גשרים; הגדה הצפונית - 3; הגדה הדרומית - 3; החלק המזרחי - 3.
הטיעון של אוילר פשוט להפליא: אם חלק יבשה אינו ההתחלה ואינו הסיום של הטיול, אז בכל פעם שנכנסים אליו דרך גשר אחד חייבים לצאת ממנו דרך גשר אחר. הגשרים שלו מתחלקים אפוא לזוגות של "כניסה ויציאה", ולכן מספרם חייב להיות זוגי. מספר אי זוגי של גשרים מותר רק בנקודת ההתחלה או בנקודת הסיום.
אבל בטיול אחד יש נקודת התחלה אחת ונקודת סיום אחת - כלומר לכל היותר שני חלקי יבשה רשאים להיות בעלי מספר גשרים אי זוגי. בקניגסברג כל ארבעת החלקים אי זוגיים (5, 3, 3, 3). ארבעה גדולים משניים, ולכן המסלול אינו קיים. אין צורך לבדוק אפילו מסלול אחד.
המאמר שאוילר כתב על בעיית הטיול הזאת נחשב היום למאמר הראשון בתורת הגרפים, ואחד המוקדמים בטופולוגיה. מסלול שעובר על כל הקשתות בדיוק פעם אחת נקרא מאז "מסלול אוילר", והתנאי שגילה - אפס או שתי נקודות אי זוגיות - הוא הקריטריון המדויק לקיומו.
הערה היסטורית: מבין שבעת הגשרים המקוריים שרדו עד היום חמישה בלבד, וחלקם נבנו מחדש לאחר מלחמת העולם השנייה.
תגובות
- לא נמצאו תגובות
Post comment as a guest