הגשרים של קוניסברג (Königsberg bridge) הציבו בעיה מעניינת שהעסיקה אנשים רבים במשך שנים רבות; כאשר הבעיה נפתרה היא בישרה על לידתו של ענף חדש וחשוב במתמטיקה - תורת הגרפים.

קוניגסברג היא עיר ברוסיה (בסמוך לפטרבורג); העיר קרויה היום בשם קלנינגרד. בתקופה המדוברת (ראשית המאה ה 18), העיר קוניגסברג הייתה עיר משגשגת על גדול נהר פרגל (Pregel). העיר הייתה עמוסת פעילות מסחרית ובעקבות כך במצב כלכלי טוב ולכן בנתה 7 גשרים מעל הנהר כדי לעזור במסחר. כפי שניתן לראות באיור למטה הגשרים חיברו בין האי (ISLA) לחלקי העיר A, B, C:


גשרי קניגסברג ממבט על


מיקום הגשרים על מפת העיר

במהלך השנים עלתה השאלה הבאה: האם אפשר לעבור על כל 7 הגשרים ברצף בלי לחצות אף אחד מהם פעמיים? אף אחד לא הצליח לענות על השאלה עד שבשנת 1736 מתמטיקאי שוויצרי גאון בשם אווילר (Leonhard Euler), שגר באותה תקופה בעיר פטרסבורג הסמוכה, הצליח לפתור את הבעיה והראה שלא ניתן לבצע את המטלה כפי שהוצגה. הגאונות של אווילר הייתה שהוא פתר לא רק את הבעיה הספציפית אלא מצא דרך פשוטה וגראפית לפתור את כל הבעיות מסוג זה:

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


גרף הגשרים. שימו לב בלכל נקודה ישנם מספר אי-זוגי של גשרים/קישורים

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


הגשר הנוסף. כל התמונות במאמר זה הן באדיבות ויקיפדיה.

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

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


ד"ר מאיר ברק
המחלקה לביולוגיה מבנית
מכון ויצמן למדע



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

0 תגובות