תורת הגרפים

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

[עריכה] סוגים שונים של גרפים

גרף בעל 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 קיימות שתיהן, או חסרות שתיהן.

גרף מעורב (mixed graph) הוא קבוצה של צמתים, קבוצה של קשתות מכוונות וקבוצה של קשתות לא מכוונות. כל קשת, מכוונת או לא מכוונת, מקשרת בין שני צמתים.

לולאה (שמכונה גם חוג עצמי) היא קשת (או קשת מכוונת) שמקשרת צומת עם עצמו. גרף ללא לולאות נקרא גרף פשוט.

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

גרף ממושקל (weighted graph) הוא גרף (מכוון או בלתי מכוון) שבו לכל קשת יש משקל, כלומר מספר או ערך שמייצג עלות, אורך או כל מדד אחר. באופן פורמלי, גרף ממושקל (בלתי) מכוון הוא שלשה $\ (V,E,w)$ , כאשר $\ V$ ו- $\ E$ מוגדרים כמקודם, ו- $\ w$ היא פונקציית המשקל מ- $\ E$ ל- $\ \mathbb{N}$ , ל- $\ \mathbb{R}$ , או לקבוצת משקולות אחרת.

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

[עריכה] שימושים של גרפים

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

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

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

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

[עריכה] משפחות גרפים

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

דוגמאות:

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

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

[עריכה] הכללות של גרף

מולטיגרף (multigraph) הוא הכללה של גרף, שבה כל זוג צמתים יכולים להיות מחוברים על ידי יותר מקשת אחת. באופן פורמלי, מולטיגרף (מכוון או בלתי מכוון) מוגדר בדומה לגרף (מכוון או בלתי מכוון), כאשר $\ E$ היא קבוצה שבה האיברים אינם יחודיים (bag).

היפרגרף (hypergraph) הוא הכללה של גרף, שבה כל קשת יכולה לחבר יותר משני צמתים. באופן פורמלי, היפרגרף בלתי מכוון מוגדר בדומה לגרף בלתי מכוון, כאשר כל קשת $\ e \in E$ היא קבוצה של שני צמתים או יותר מ- $\ V$ . היפרגרף מכוון מוגדר בדומה לגרף מכוון, כאשר כאשר כל קשת $\ e \in E$ מורכבת משתי קבוצות כל אחת בעלת צומת אחד או יותר מ- $\ V$ , קבוצה של צמתים מהם הקשת יוצאת וקבוצה של צמתים אליהם הקשת נכנסת.

[עריכה] יצוג גרפים

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

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

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

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

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

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

[עריכה] רקע היסטורי

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

[עריכה] משפטים חשובים בתורת הגרפים

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

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

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

[עריכה] אלגוריתמים חשובים

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

[עריכה] ראו גם

מרחק (תורת הגרפים)

[עריכה] קישורים חיצוניים

במשיכת קולמוס אחת, על בעיית הגשרים של קניגסברג, באתר אלף אפס
תורת הגרפים בeitan.ac.il, בעיקר על אלגוריתמים בתורת הגרפים

מקור: http://he.wikipedia.org../../../%D7%AA/%D7%95/%D7%A8/%D7%AA%D7%95%D7%A8%D7%AA_%D7%94%D7%92%D7%A8%D7%A4%D7%99%D7%9D.html

קטגוריה: תורת הגרפים