צילום: Александр Сигачёв, Wikimedia Commons (CC0)
בעיר קניגסברג של המאה השמונה עשרה - היום קלינינגרד - זרם נהר הפרגולה ובתוכו שני איים. שבעה גשרים חיברו בין ארבעת חלקי היבשה: האי המרכזי, האי השני, הגדה הצפונית והגדה הדרומית. חמישה גשרים חיברו את האי המרכזי לשאר החלקים, שניים נוספים חיברו את האי השני לשתי הגדות, וגשר אחד חיבר בין שני האיים.
תושבי העיר נהגו לצאת לטיולי שבת, ובין הפונדקים נולדה שאלה שהתגלגלה שנים: האם אפשר לצאת לטיול שעובר על כל שבעת הגשרים בדיוק פעם אחת כל אחד - בלי לחצות אף גשר פעמיים ובלי לדלג על אף אחד? מותר להתחיל בכל מקום ולסיים בכל מקום.
אנשים ניסו וניסו ולא הצליחו. אבל אי הצלחה אינה הוכחה. בשנת 1736 קיבל את השאלה מתמטיקאי שווייצרי בן עשרים ותשע בשם לאונרד אוילר, והתשובה שלו לא רק סגרה את הסיפור - היא פתחה ענף מתמטי חדש לגמרי.
השאלה: האם קיים מסלול כזה - ואיך אפשר להכריע את זה בוודאות מוחלטת בלי לנסות אפילו מסלול אחד?
שכחו לרגע מהמרחקים, מהצורה של האיים ומאורך הגשרים. כל מה שחשוב הוא מי מחובר למי. צמצמו כל חלק יבשה לנקודה אחת וכל גשר לקו שמחבר שתי נקודות. מה נשאר מהעיר?
חשבו על נקודה שאינה נקודת ההתחלה ואינה נקודת הסיום של הטיול. בכל פעם שנכנסים אליה חייבים גם לצאת ממנה, ובכל כניסה ויציאה נשרפים שני גשרים. מה זה מחייב לגבי מספר הגשרים שנוגעים בנקודה כזאת - וכמה נקודות חריגות מותר שיהיו?
המסלול אינו קיים - ואי אפשר לבנות אותו בשום דרך.
אוילר צמצם את המפה לארבע נקודות ושבעה קווים, ובכך המציא למעשה את מה שקרוי היום גרף. לאחר מכן ספר כמה קווים נוגעים בכל נקודה. באי המרכזי נוגעים חמישה גשרים, ובכל אחת משלוש הנקודות האחרות נוגעים שלושה גשרים. כלומר כל ארבע הנקודות הן בעלות "דרגה אי-זוגית".
וכאן הטיעון: נקודה שאינה ההתחלה ואינה הסיום נדרשת תמיד לזוגות של גשרים - אחד לכניסה ואחד ליציאה - ולכן מספר הגשרים בה חייב להיות זוגי. רק נקודת ההתחלה ונקודת הסיום יכולות להיות אי-זוגיות. מכיוון שיש בטיול לכל היותר התחלה אחת וסיום אחד, מספר הנקודות האי-זוגיות המותר הוא אפס או שתיים בלבד. בקניגסברג יש ארבע - ולכן שום מסלול כזה לא ייתכן, ולא משנה כמה זמן ננסה.
הכלל הזה הפוך גם לכיוון השני: בגרף מחובר שבו יש אפס נקודות אי-זוגיות תמיד קיים מסלול סגור שעובר על כל הקשתות בדיוק פעם אחת (מעגל אוילר), ואם יש בדיוק שתיים - קיים מסלול פתוח שמתחיל באחת ומסתיים בשנייה. זאת הסיבה שאפשר לצייר מעטפה סגורה בקו אחד, אבל לא כל צורה שרירותית.
המאמר שאוילר פרסם ב-1736 נחשב למאמר הראשון בתורת הגרפים, ומהותו הייתה תובנה עקרונית: לפעמים הפתרון מתחיל בזריקה מכוונת של כל המידע המיותר. אגב, מבין שבעת הגשרים המקוריים שרדו את מלחמת העולם השנייה חמישה בלבד, ואחד מהם - גשר הדבש - עדיין עומד על מקומו וניתן לחצות אותו גם היום.
תגובות
- לא נמצאו תגובות
Post comment as a guest