הגשרים של קניגסברג

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

בעיית הגשרים של קניגסברג היא חידה מפורסמת עם השפעה מכרעת על ההיסטוריה של המתמטיקה.

מפת קנינסברג, הנהר והגשרים מודגשים בצבע

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

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

הפתרון של אוילר[עריכת קוד מקור | עריכה]

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

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

Konigsburg graph.svg7 bridges.svgKonigsberg bridges.png

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

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

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

הכללה[עריכת קוד מקור | עריכה]

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

חשיבות היסטורית[עריכת קוד מקור | עריכה]

פתרונו של אוילר לבעיית הגשרים של קניגסברג, שהוצג בשנת 1735, נחשב לתוצאה הראשונה בתורת הגרפים. תרומה נוספת של אוילר לתחום היא נוסחת אוילר.

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

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]