תורת הגרפים

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

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

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

ייצוג גרפים

לצורך ביצוע פעולות על גרפים, שהם גופים מופשטים, יש צורך להשתמש בייצוג כלשהו שלהם. נהוג להציג גרף באופן ויזואלי, כפי שהוצג בראש ערך זה, כך שכל צומת מוצג באמצעות נקודה, וכל קשת מוצגת באמצעות קו. קשת מכוונת מוצגת באמצעות ראש חץ לכיוון הצומת אליו הקשת נכנסת. ההצגה הוויזואלית היא מאוד נוחה וטבעית לעין אנושית. צורת הצגה זו אינה פורמלית ולכן קשה להגדיר אלגוריתמים שמשתמשים בה.
גרף, כפי שהוגדר לעיל, הוא קבוצה של צמתים וקבוצה של קשתות ביניהם. שתי הקבוצות הללו יחדיו מייצגות את הגרף. הייצוג הטריוויאלי הזה אינו מקובל, מכיוון שהוא אינו מקל על ביצוע פעולות על הגרף. סיבוכיות זמן הריצה ומקום האחסון של אלגוריתם הפועל על גרפים תלויה ביעילות יצוג הגרפים והפעולות עליהם. לכן, יש חשיבות לבחירת יצוג גרפים לפי אופי האלגוריתם, כלומר לפי סוג הגרפים עליהם הוא פועל ולפי הפעולות על הגרפים אותם הוא מבצע.
מטריצת סמיכויות (adjacency matrix) היא שיטת יצוג מקובלת לגרף כללי. בשיטה זו, הגרף מיוצג כמטריצה בגודל  כאשר כל צומת מיוצג על ידי שורה ועל ידי עמודה. תא  במטריצה מכיל "1" אם ישנה בגרף קשת מהצומת של  לצומת של , ו-"0" אחרת. היתרון של מטריצת סמיכויות הוא שניתן לענות על שאלות מסוג "האם u הוא שכן של v?" בזמן קבוע. במטריצת סמיכויות, כל זוג צמתים מיוצג על ידי סיבית בודדות במטריצה, בין אם קיימת קשת ביניהם ובין אם הקשת אינה קיימת. לכן, המקום שנדרש לייצוג כזה הוא כריבוע מספר הצמתים, כלומר  סיביות. גודל מקום זה הוא אופטימלי עבור גרף כללי וגרף אקראי, אבל עלול להיות גבוה עבור גרף דליל.
רשימת סמיכויות (adjacency list) גם היא שיטת יצוג מקובלת לגרף כללי. בשיטה זו, הגרף מיוצג כקבוצה של רשימות מקושרות של השכנים של כל צומת. היתרון של רשימות סמיכויות הוא תשובה בזמן קבוע על פעולות מסוג "הבא את רשימת השכנים של v", "הבא שכן כלשהו של v" ו-"הבא את השכן הבא של v". לצורך כך דרושים  ראשי רשימות ו צמתים, כלומר סה"כ  מקום, פחות מזה של מטריצת סמיכויות עבור גרף שאינו צפוף.
את שתי השיטות הנ"ל ניתן להכליל גם עבור גרפים בלתי מכוונים וגרפים ממושקלים.
פרט לשתי השיטות שהוזכרו, המקובלת לגרף כללי, קיימות שיטות יצוג שונות עבור גרפים מסוימים. כאשר ידוע לנו שהגרפים עליהם האלגוריתם פועל שייכים למשפחת גרפים מסוימת, כלומר מקיימים תכונה מסוימת, ניתן למצוא יצוג שיינצל את התכונה כדי לקבל זמן ריצה יעיל עבור פעולות הקשורות בה, או נפח אחסון נמוך. למשל, עץ ניתן לייצוג על ידי קביעת צומת כלשהו לשורש, ואחסון מצביע לאב (הצומת השכן שהמסלול היחיד לשורש עובר דרכו) עבור כל צומת אחר. יצוג כזה של עץ דורש  מקום.

רקע היסטורי

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