הגשרים של קניגסברג
בעיית הגשרים של קניגסברג היא חידה מפורסמת עם השפעה מכרעת על ההיסטוריה של המתמטיקה.
העיר קניגסברג שבפרוסיה המזרחית (כיום קלינינגרד שברוסיה) הייתה מחולקת לארבעה חלקים על ידי נהר הפרגל (כיום פרגוליה). שבעה גשרים חיברו בין ארבעת חלקי העיר. בין תושבי העיר התפתחה מסורת לפיה לא ניתן להלך בעיר ולחצות את כל שבעת הגשרים מבלי לעבור על גשר אחד לפחות יותר מפעם אחת. תושבי העיר ניסו להוכיח או להפריך השערה זו, אך ללא הצלחה.
המתמטיקאי לאונרד אוילר פתר את הבעיה ב-1735, כשהראה שמסלול שכזה אינו אפשרי. אוילר הציג את הפתרון בפני האקדמיה של סנקט פטרבורג ב-26 באוגוסט במה שנחשב למאמר הראשון בתורת הגרפים ולנקודת ציון בהיסטוריה של הטופולוגיה.
הפתרון של אוילר
[עריכת קוד מקור | עריכה]ראשית אוילר הבחין שפתרון הבעיה כלל אינו תלוי בצורה הגאוגרפית המדויקת של העיר. למתווה העירוני, לאורכי הרחובות והגשרים ולמיקומם המדויק אין השפעה על המסלולים האפשריים. המידע היחיד הנחוץ לצורך פתרון הבעיה הוא אילו חלקים מחוברים לאילו חלקים ובכמה גשרים.
בשביל לפתור את החידה מספיק לייצג את העיר באמצעות גרף. כל אחד מארבעת חלקי העיר נייצג באמצעות צומת, וכל אחד מבין שבעת הגשרים ייוצג על ידי קשת, כמתואר בציור.
→
→
בעיית הגשרים של קניגסברג היא למעשה השאלה האם ניתן למצוא מסלול רציף המתחיל מצומת כלשהו ועובר דרך כל שבע הקשתות פעם אחת בדיוק. כדי להיווכח בכך שהתשובה היא 'לא', נשים לב להבחנה הבאה:
- נבחר את אחד הצמתים ונניח שצומת זה אינו ההתחלה או הסיום של המסלול.
- בכל פעם שמגיעים לצומת הזה חייבים להיכנס לצומת דרך קשת אחת ולצאת מהצומת דרך קשת אחרת. כלומר, בכל ביקור בצומת שתי קשתות נפסלות לשימוש עתידי (כי אסור לעבור על אותה קשת פעמיים).
- מכיוון שהמסלול לא מתחיל או נגמר בצומת הנתון, מובטח שלכל כניסה לצומת אכן תתאים יציאה מהצומת, ובסך הכל לצומת חייב להיות מספר זוגי של קשתות המחוברות אליו.
- לכן אם לצומת יש מספר אי-זוגי של קשתות המחוברות אליו, הוא חייב להיות נקודת ההתחלה או הסיום של המסלול, וחייב להיות צומת אחד נוסף שבו יסתיים או יתחיל המסלול בהתאמה.
המסקנה היא שכדי שיהיה מסלול העובר דרך כל הקשתות פעם אחת בלבד, נדרש שכל הצמתים, או כולם פרט לשניים, יהיו מחוברים למספר זוגי של קשתות. אבל בבעיית הגשרים של קניגסברג לכל ארבעת הצמתים יש מספר אי-זוגי של קשתות מחוברות. לכן לא קיים מסלול שכזה.
הכללה
[עריכת קוד מקור | עריכה]למעשה הפתרון של אוילר רחב יותר מפתרון נקודתי לבעיית הגשרים של קניגסברג. הניתוח של אוילר עובד בכל גרף קשיר (בלתי מכוון) אפשרי. מסלול שמבקר בכל הקשתות של גרף נתון פעם אחת בדיוק נקרא מסלול אוילר. הדרגה של צומת בגרף היא מספר הקשתות המחוברות אליו. הטיעון של אוילר מוכיח שבגרף קשיר יהיה מסלול אוילר אם ורק אם כל הצמתים הם בעלי דרגה זוגית, או שיש בדיוק שני צמתים עם דרגה אי-זוגית (צומת ההתחלה וצומת הסיום). אם רוצים שמסלול אוילר יתחיל ויסתיים באותו הצומת (מסלול שכזה נקרא מעגל אוילר) אז הגרף חייב להיות כזה בו כל הצמתים הם בעלי דרגה זוגית.
חידה נפוצה הקשורה לבעיה זו היא, עבור ציור נתון, האם ניתן לצייר אותו במשיכת קולמוס אחת, כלומר בלי להרים את העיפרון מהנייר. חידה זו שקולה לשאלה האם הגרף שאותו מתאר הציור מכיל מסלול אוילר.
חשיבות היסטורית
[עריכת קוד מקור | עריכה]פתרונו של אוילר לבעיית הגשרים של קניגסברג, שהוצג בשנת 1735, נחשב לתוצאה הראשונה בתורת הגרפים. תרומה נוספת של אוילר לתחום היא נוסחת אוילר.
בנוסף מקובל לציין פתרון זה כנקודת ציון בהיסטוריה של הטופולוגיה. ההבחנה של אוילר שניתן לזנוח את המאפיינים הגאומטריים של העיר לטובת תיאור סכמטי של העיר כגרף, קרובה לרעיון העומד בבסיס ענף הטופולוגיה, החוקר את המרחב תוך התעלמות מהתכונות המטריות שלו.
ראו גם
[עריכת קוד מקור | עריכה]קישורים חיצוניים
[עריכת קוד מקור | עריכה]
- במשיכת קולמוס אחת, באתר "אלף אפס"
- הגשרים של קניגסברג, בארכיון אוילר
- הגשרים של קניגסברג, באתר אנציקלופדיה בריטניקה (באנגלית)
- הגשרים של קניגסברג, באתר MathWorld (באנגלית)