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

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

תמונה 1 - תיאור הגשרים (קרדיט וויקיפדיה)

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

תמונה 2. בעית הגשרים כגרף

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

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

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

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

 מקורות:

[1] בעית הגשרים

[2] בעית הסוכן הנוסע