תורת הגרפים

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

מושגים יסודיים בתורת הגרפים

ערך מורחב – גרף (תורת הגרפים)

גרף בעל 6 צמתים ו-7 קשתות

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

שתי הבחנות בולטות בתורת הגרפים הן ההבחנה בין גרף מכוון לגרף בלתי מכוון, ובין גרף סופי לגרף אינסופי.

גרף מכוון (directed graph, digraph) הוא קבוצה של צמתים (נקראים גם נקודות, קודקודים, nodes, vertices) וקבוצה של קשתות מכוונות (directed edges, arcs). כאשר ישנה משמעות לכיוונה של קשת מכוונת – היא יוצאת מצומת אחד ונכנסת לצומת אחר. באופן פורמלי, גרף מכוון $\ D$ מוגדר על ידי $\ (V,E)$ כאשר $\ V$ היא קבוצת הצמתים ו-$\ E\subseteq V\times V$ היא קבוצת הקשתות. קשת $\ e=(u,v)\in E$ יוצאת מ-$\ u$ ונכנסת ל-$\ v$.

גרף בלתי מכוון (undirected graph), ולעיתים בפשטות גרף הוא קבוצה של צמתים וקבוצה של קשתות (edges). כל קשת מקשרת בין שני צמתים. באופן פורמלי, גרף בלתי מכוון $\ G$ מוגדר על ידי $\ (V,E)$ כאשר $\ V$ היא קבוצת הצמתים ו-$\ E\subseteq \{uv\mid u,v\in V\}$ היא קבוצת הקשתות. ניתן לראות בגרפים בלתי מכוונים מקרה פרטי של גרפים מכוונים, בהם עבור כל זוג צמתים u ו-v, הקשתות מ-u ל-v ומ-v ל-u קיימות שתיהן, או חסרות שתיהן.

גרף תשתית של גרף מכוון הוא גרף לא מכוון, אשר מכיל אותה קבוצת צמתים כמו הגרף המכוון, ומכיל את הקשתות בין זוגות הצמתים אשר היו ביניהם קשתות בגרף המקורי. אם $G=(V,E)$‎ הוא גרף מכוון אז $G'=(V,\{\{u,v\}|(u,v)\in E\})$ הוא גרף התשתית של $G$.

גרף סופי (finite graph) הוא גרף שקבוצת הצמתים שלו סופית. גרף אינסופי (infinite graph) הוא גרף שקבוצת הצמתים שלו היא אינסופית.

שימושים של גרפים

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

דוגמה לשימוש בגרף בלתי מכוון ממושקל היא רשת כבישים. כל עיר מיוצגת על ידי צומת, כל כביש בין-עירוני על ידי קשת, ואורכו של כל כביש הוא משקל הקשת המתאימה.

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

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

משפחות גרפים

משפחת גרפים (graph class) היא קבוצת כל הגרפים שלהם תכונה משותפת מסוימת.

דוגמאות:

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

ניתן להגדיר משפחת גרפים בעבור כל תכונה, ואפילו לפי רשימה פרטנית של גרפים שבמשפחה או של גרפים שאינם במשפחה.

הכללות של גרף

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

ייצוג גרפים

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

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

מטריצת סמיכויות (adjacency matrix) היא שיטת יצוג מקובלת לגרף כללי. בשיטה זו, הגרף מיוצג כמטריצה בגודל $\ |V|\times |V|$ כאשר כל צומת מיוצג על ידי שורה ועל ידי עמודה. תא $\ (i,j)$ במטריצה מכיל "1" אם ישנה בגרף קשת מהצומת של $i$ לצומת של $j$, ו-"0" אחרת. היתרון של מטריצת סמיכויות הוא שניתן לענות על שאלות מסוג "האם u הוא שכן של v?" בזמן קבוע. במטריצת סמיכויות, כל זוג צמתים מיוצג על ידי סיבית בודדות במטריצה, בין אם קיימת קשת ביניהם ובין אם הקשת אינה קיימת. לכן, המקום שנדרש לייצוג כזה הוא כריבוע מספר הצמתים, כלומר $\ \Theta (|V|^{2})$ סיביות. גודל מקום זה הוא אופטימלי עבור גרף כללי וגרף אקראי, אבל עלול להיות גבוה עבור גרף דליל.

רשימת סמיכויות (adjacency list) גם היא שיטת יצוג מקובלת לגרף כללי. בשיטה זו, הגרף מיוצג כקבוצה של רשימות מקושרות של השכנים של כל צומת. היתרון של רשימות סמיכויות הוא תשובה בזמן קבוע על פעולות מסוג "הבא את רשימת השכנים של v", "הבא שכן כלשהו של v" ו"הבא את השכן הבא של v". לצורך כך דרושים $\ |V|$ ראשי רשימות ו-$\ |E|$ צמתים, כלומר סה"כ $\ \Theta (|V|+|E|)$ מקום, פחות מזה של מטריצת סמיכויות עבור גרף שאינו צפוף.

את שתי השיטות הנ"ל ניתן להכליל גם עבור גרפים בלתי מכוונים וגרפים ממושקלים.

פרט לשתי השיטות שהוזכרו, המקובלת לגרף כללי, קיימות שיטות יצוג שונות עבור גרפים מסוימים. כאשר ידוע לנו שהגרפים עליהם האלגוריתם פועל שייכים למשפחת גרפים מסוימת, כלומר מקיימים תכונה מסוימת, ניתן למצוא יצוג שיינצל את התכונה כדי לקבל זמן ריצה יעיל עבור פעולות הקשורות בה, או נפח אחסון נמוך. למשל, עץ ניתן לייצוג על ידי קביעת צומת כלשהו לשורש, ואחסון מצביע לאב (הצומת השכן שהמסלול היחיד לשורש עובר דרכו) עבור כל צומת אחר. יצוג כזה של עץ דורש $\ \Theta (|V|\log |V|)$ מקום.

רקע היסטורי

מאמרו של לאונרד אוילר על הגשרים של קניגסברג, שהוצג בשנת 1735, נחשב לתוצאה המשמעותית הראשונה בתורת הגרפים. הוא גם נחשב לאחת מהתוצאות הטופולוגיות הראשונות בגאומטריה; כלומר, הוא לא תלוי במדידות כלשהן.

משפטים חשובים בתורת הגרפים

• משפט החתונה של הול
• משפט רמזי
• נוסחת קיילי – נוסחה לחישוב מספר העצים הפורשים בגרף השלם על n קודקודים מסומנים

בעיות מרכזיות בתורת הגרפים

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

אלגוריתמים חשובים

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

קישורים חיצוניים

• במשיכת קולמוס אחת, על בעיית הגשרים של קניגסברג, באתר אלף אפס
• תורת הגרפים ב־eitan.ac.il, בעיקר על אלגוריתמים בתורת הגרפים
• תורת הגרפים, באתר אנציקלופדיה למתמטיקה (באנגלית)
• תורת הגרפים, באתר MathWorld (באנגלית)
• תורת הגרפים, באתר אנציקלופדיה בריטניקה (באנגלית)
• עקומות, תיאוריה, דף שער בספרייה הלאומית