הגשרים של קניגסברג (Königsberg bridge) הציבו בעיה מעניינת שהעסיקה אנשים רבים במשך שנים רבות; כאשר הבעיה נפתרה היא בישרה על לידתו של ענף חדש וחשוב במתמטיקה - תורת הגרפים.
השם קניגסברג הוא שם גרמני היסטורי לעיר קלינינגרד שברוסיה של היום, אך במאה ה-18 היא הייתה חלק מממלכת פרוסיה. קניגסברג הייתה עיר משגשגת על גדות נהר פרגל (Pregel), עמוסת פעילות מסחרית ובעלת מעמד כלכלי יציב שאיפשר לתושביה לבנות שבעה גשרים שחצו את הנהר וחיברו בין חלקי העיר השונים. כפי שניתן לראות באיור, הגשרים חיברו בין האי המרכזי (ISLA) לבין חלקי העיר A, B, C.
הגשרים חיברו בין האי לבין חלקי העיר A,B,C. תרשים הגשרים של קניגסברג | מקור: Bogdan Giuşcă & Moriel, Wikipedia
החידה של קניגסברג
במהלך השנים עלתה השאלה הבאה: האם אפשר לעבור על כל שבעת הגשרים ברצף, בלי לחצות אף אחד מהם פעמיים? אף אחד לא הצליח לענות על השאלה עד שבשנת 1736, מתמטיקאי שוויצרי גאון בשם לאונרד אווילר (Leonhard Euler), שגר באותה תקופה בעיר סנט פטרסבורג, הצליח לפתור את הבעיה והוכיח שלא ניתן לבצע את המטלה כפי שהוצגה. הגאונות של אווילר הייתה בכך שהוא לא רק פתר את הבעיה הספציפית הזו, אלא גם פיתח עקרונות גראפיים פשוטים לפתרון בעיות דומות.
אווילר התייחס לכל פיסת אדמה בציור כצומת, ואת הגשרים כקישורים בין הצמתים. הוא הראה במאמר שלו שבשביל שבעיה מהסוג הזה תהיה פתירה, צריכים להיות לכל היותר שני צמתים עם מספר אי-זוגי של קישורים: הצומת שממנה מתחילים והצומת שבה מסיימים. מבט בתמונה מראה שכל ארבעת הצמתים בקניגסברג הם בעלי מספר אי-זוגי של קישורים, ולכן הבעיה אינה פתירה.
בכל נקודה ישנם מספר אי-זוגי של גשרים או קישורים | מקור: Bogdan Giusca, Xiong, Mark Foskey, Wikipedia
רק בשנת 1875 (כמעט 150 שנה לאחר פתרון הבעיה) נבנה גשר שמיני שחיבר, לדוגמה, בין נקודות A ו-C. אז הבעיה הפכה לפתירה, כי היו רק שני צמתים עם מספר אי-זוגי של קישורים. עם זאת, במלחמת העולם השנייה נהרסו שניים מהגשרים בעקבות הפצצות בעלות הברית, ובהמשך נהרסו שני גשרים נוספים במסגרת בניית אוטוסטרדה.
החשיבות של תורת הגרפים, המכונה גם תורת הרשתות, היא ההבנה שלרשתות וגרפים יש מאפיינים פנימיים הנובעים מהמבנה שלהם. מאפיינים אלה קובעים תרחישים ואפשרויות שונות במערכות רבות סביבנו, כגון המוח, מערכות כבישים, קשרים חברתיים ועוד.
הבנת המאפיינים הללו חשובה במיוחד גם לבעיה נפוצה בישראל – פקקי תנועה. בערים רבות יש עומסי תנועה כבדים. אם נצליח לייצג את בעיות התנועה באמצעות תורת הגרפים, ייתכן שנוכל לחסוך אלפי שעות עבודה ומיליוני שקלים על ידי בניית כביש רוחב אחד או שניים במקומות הנכונים. כמובן, רשתות הכבישים בערים השונות הן מורכבות מאוד, והפתרון שהוצג כאן הוא פשטני, אך תורת הגרפים יכולה לסייע בפישוט בעיות מורכבות ולמציאת פתרונות יעילים לבעיות שללא שיטה זו היו בלתי פתירות.מעט פשטני; אך תורת הגרפים יכולה לפשט בעיות מורכבות שכאלה ולסייע בפתרון בעיות שללא שיטה זו היו בלתי פתירות
