חידה על טיול
העיר הפרוסית קניגסברג, כיום קלינינגרד שברוסיה, נבנתה במקום שבו נהר הפרגל מתפצל סביב אי בשם קנייפהוף ואחר כך ממשיך לזרום כנהר אחד. בתחילת המאה השמונה־עשרה חיברו שבעה גשרים בין האי, שתי גדות הנהר והיבשה שבין שתי הזרועות המזרחיות של הנהר. בעיר נפוצה חידה: האם אפשר לצאת לטיול שחוצה כל גשר בדיוק פעם אחת?
איש לא מצא טיול כזה. ב־1736 הראה המתמטיקאי השווייצרי לאונרד אוילר שאיש גם לא ימצא, והוא עשה זאת בלי לנסות אף מסלול.
רק החיבורים חשובים
אוילר שם לב שכמעט כל מה שיש בעיר לא משנה דבר. לצורת האי, לאורך הרחובות ולמקום שבו עומדים על הגדה אין שום השפעה. כל מה שחשוב הוא אילו פיסות יבשה כל גשר מחבר.
אז כווצו כל פיסת יבשה לנקודה, וציירו כל גשר כקו בין שתי נקודות. מה שנשאר הוא גרף: קבוצה של נקודות, שנקראות צמתים או קודקודים, המחוברות בקווים, שנקראים קשתות. בחרו הגרף תחת הפיכת העיר לגרף, והעיר שבמודל תהפוך בדיוק לציור הזה, עם האי A באמצע, הגדות B ו־C והיבשה המזרחית D.
סופרים את הגשרים בכל פיסת יבשה
עכשיו חשבו על טיול שעובר דרך פיסת יבשה. בכל פעם שהוא מגיע אליה בגשר אחד, הוא חייב לצאת ממנה בגשר אחר. לכן הגשרים של פיסת יבשה שהטיול רק עובר דרכה מנוצלים בזוגות, ומספרם חייב להיות זוגי. מספר הקשתות שיוצאות מצומת נקרא הדרגה שלו.
המקומות היחידים שמותר שתהיה להם דרגה אי־זוגית הם המקום שבו הטיול מתחיל והמקום שבו הוא נגמר. כלומר:
- אם כל הדרגות זוגיות, אפשר לעבור בכל קשת פעם אחת ולסיים במקום שבו התחלתם: מעגל.
- אם בדיוק שתי דרגות הן אי־זוגיות, אפשר לעבור בכל קשת פעם אחת, אבל צריך להתחיל בצומת אי־זוגי אחד ולסיים בשני.
- אם יותר משתיים הן אי־זוגיות, אין טיול כזה.
בקניגסברג יש לאי חמישה גשרים, ולכל אחת משלוש פיסות היבשה האחרות יש שלושה. כל ארבע הדרגות אי־זוגיות, ולכן הטיול בלתי אפשרי. בסצנה המטייל חוצה כמה שיותר גשרים, והגשר שאליו הוא לא מצליח להגיע ממשיך לזהור באדום.
נסו: קבעו את גשרים על 7, כמו ב־1736, ובחרו הגרף תחת הפיכת העיר לגרף: כל הנקודות זוהרות בכתום. אחר כך קבעו את גשרים על 6 ועל 9, וצפו איך הנקודות הכתומות נעלמות.
אף פעם לא יכול להיות צומת אי־זוגי אחד בדיוק. לכל קשת יש שני קצוות, ולכן סכום הדרגות הוא תמיד פעמיים מספר הקשתות, כלומר מספר זוגי, והצמתים האי־זוגיים חייבים לבוא בזוגות.
מוצאים את המסלול
הספירה של אוילר אומרת מתי טיול כזה קיים. כדי למצוא אותו בפועל צריך מתכון, ומתכון אלגנטי פרסם ב־1873 המתמטיקאי הגרמני קרל היירהולצר, שהוכיח שהתנאי של אוילר לא רק הכרחי אלא גם מספיק. התחילו בצומת אי־זוגי, אם יש כזה, והמשיכו ללכת לאורך קשת כלשהי שעוד לא השתמשתם בה, עד שתיתקעו. אם נשארו קשתות, חזרו לצומת במסלול שלכם שעדיין יוצאות ממנו קשתות שלא השתמשתם בהן, לכו משם בלולאה עד שתחזרו אליו, ושלבו את הלולאה במסלול. חזרו על כך עד שתשתמשו בכל הקשתות. המטייל בסצנה הולך במסלול שנמצא בדיוק בדרך הזאת.
מסלולים שעוברים בכל קשת פעם אחת נקראים היום מסלולי אוילר ומעגלי אוילר. אותו היגיון משמש לתכנון מסלולים למטאטאי כבישים, למפלסות שלג ולסבבי משלוחים שצריכים לכסות כל רחוב, וגרפים באופן כללי מתארים כל דבר שעשוי מחיבורים: מפות דרכים, מעגלים חשמליים, מולקולות, חברויות והקישורים בין דפי אינטרנט.
מה המודל הזה משאיר בחוץ
העיר היא מודל מפושט. הנהר, היבשה ומיקומי הגשרים מצוירים כדי להראות אילו פיסות יבשה כל גשר מחבר, ולא כדי להתאים למפות ישנות, והגשרים השמיני והתשיעי הומצאו כדי להראות מה משתנה. מטייל אמיתי יכול היה גם לחצות בסירה; החידה אוסרת זאת, וכך גם המודל. ולבסוף, אוילר עבד עם אותיות לפיסות היבשה ועם מספרי הגשרים, ולא עם ציור של נקודות וקווים; תמונת הגרף היא הדרך המודרנית להציג את הרעיון שלו.