מהי תורת הגרפים וכיצד מוגדר גרף ככזה?

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

ציטוט (APA)

אלכסנדר ברזה | יולי 2022
תואר בפיזיקה

אנו מצידו מגדירים גרף כזוג מסודר (הולך) איפה v מציין את הקבוצה (הלא ריקה) של כל הקודקודים או הצמתים של הגרף, while א מציין את הקבוצה (היא יכולה להיות ריקה) של כל הקצוות או הקווים המצטרפים לקודקודים של גרף. האלמנטים של הסט א יכול להיות מוגדר כזוג לא מסודר {v, w} כאשר v ו-w הם אלמנטים (צמתים או קודקודים) של v, באופן זה נאמר אז ש-v ו-w הם קודקודים סמוכים (הם מחוברים בקצה).

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

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

אוילר עיצב את קניגסברג כגרף שבו כל נקודה (קודקוד או צומת) מייצגת גשר וכל קו (קצה) נתיב ביבשה:

מה הפתרון לבעיה זו?

אין אחד פִּתָרוֹן שעומד בתנאים שהוטלו, שכן, כפי שהראה אוילר, הקודקודים אינם בדרגה זוגית, כלומר, מספר זוגי של קווים אינו משפיע על כל נקודה _[3]. עם זאת, לא נראה שאנחנו יכולים לעשות הרבה עם מבנה המוגדר כל כך פשוט כמו זה, כפי שקורה לעתים קרובות ב מתמטיקה, לפעמים הדברים אינם מה שהם נראים. לפיכך, אחד התחומים הפוריים, הרוחביים והבינתחומיים ביותר _[4] של ידע אנושי, תורת הגרפים.

גרפים אולריאניים או עם מסלול אוילריאנית?

לכל הגרפים הבאים יש נתיבים אולריאניים _[5]. האם לכולם יש מחזורים אולריאנים?

ניקח את הגרף השלישי:

בואו נמנה את הקודקודים:

אנו רואים אם כן שהנתיב המוגדר על ידי הרצף {3,4,6,2,1,3,7,6,5,4,2} הוא נתיב אולריאנית, שכן הוא עובר על כל הגרף מבלי לחזור על קצוות, אבל זה לא מחזור אולריאן, מכיוון שהוא לא מגיע לנקודת ההתחלה. מה היה קורה אם היינו מספרים את הקודקודים אחרת? לא הרבה, אלא שעכשיו הדרך תוגדר על ידי רצף אחר. מה היה קורה אילו היינו הולכים בדרכים שונות מאלה שהוצעו בפתרון הראשוני שלנו? שאלה זו קצת יותר מורכבת לתשובה, והיא כרוכה באלגוריתמים שמהנדסי תוכנה בדרך כלל מרוצים מהם. תִכנוּת.

להוכחה קפדנית יותר למה שנחשף כאן עלינו להתייחס לתוצאה הבאה:

"לִהיוֹת ג גרף מחובר _[6]. אז כן ג שיהיה לך מעגל חשמלי אוילר, מידת כל קודקוד היא זוגית, ואילו אם ג יש נתיב אוילר, ל-G יש בדיוק שני קודקודים בדרגה אי-זוגית _[7] (בדיוק הקודקודים שבהם הנתיב מתחיל ונגמר)".

לאחר מכן נוכל לוודא שלמעשה, בגרף שאנו לוקחים, רק לקודקודים 3 ו-6 יש מידה אי-זוגית (זו היה מתרחש גם אם מספור הקודקודים היה שונה), לכן לגרף האמור יש נתיב אולריאן _[8]. עבור הגרפים הנותרים נוכל להמשיך בצורה אנלוגית ולוודא אם אכן יש להם נתיבים ו מחזורים אולריאנים, או במילים אחרות, האם נוכל לצייר גרפים כאלה מבלי להרים את העיפרון ולחזור שורות? ניתן להסיק את התשובה לשאלה זו ממה שכבר הוסבר עד כה, אולם היא מהווה תרגיל מעניין מבחינת מוטוריקה עדינה, כושר המצאה וסבלנות, אני מזמין את הקורא למצוא ולצייר גרפים של 6 או יותר קודקודים עם מַסלוּל אוילריאן.

האם יש עוד סוגים של גרפים? האם לתורת הגרפים יש יישומים בעולם ה'אמיתי'?

הגרפים הללו שסקרנו בקצרה מאוד, הם רק אחד מסוגי הגרפים הרבים שאנו מוצאים בתורת הגרפים. אנו יכולים למצוא גם גרפים כגון עצים, מייצגים מאוד בקבוצות שבהן ניתן לסווג את האלמנטים שלהם בהיררכיות ובחישובי ספירה. הִסתַבְּרוּת_[9], דיגרפים, גרפים המילטון _[10], וכו.

תמונה של מודלים גרפיים ורשתות בפסיכו., מאת Ruiz, Ana María.

לחידות אלה, אם נרצה לקרוא להן כך, יש יישום עצום בעולם של היום, במצבים מגוונים כמו: ביולוגיה מולקולרית _[11], מחשוב_[12], תקשורת _[13] וניתוח רשת _[14]. כדאי לשאול אם כך: האין זה לפחות מוזר שיש בעיה של כמעט בָּנָאלִי האם בסופו של דבר תהיה אחת התוצאות המעניינות והבולטות של המתמטיקה? אולי לשם כך הייתה נחוצה תרומתו של אחד המוחות המהוללים ביותר של האנושות.