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