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

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

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

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

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

תמונה:Konigsburg_graph.png

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

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

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

[עריכה] קישורים חיצוניים