ברוכים הבאים ליחידת המבוא לתורת הגרפים! יחידה זו מהווה את אבן היסוד להבנת אחד התחומים המרתקים והשימושיים ביותר במדעי המחשב ובמתמטיקה בדידה. נלמד את ההגדרות הבסיסיות, נכיר סוגי גרפים נפוצים ואת שיטות הייצוג שלהם, תוך שימת דגש על ההיבטים החשובים לבחינה.
היסודות: מהו גרף?
גרפים הם מודל מתמטי רב עוצמה לייצוג יחסים בין אובייקטים. הם מורכבים מקבוצת קודקודים ומקבוצת קשתות המחברות ביניהם.
סוגי גרפים בסיסיים
הקשרים בין הקודקודים יכולים להיות מכוונים או לא מכוונים, וכן יכולים להיות קשתות מרובות או לולאות.
גרף לא מכוון (Undirected Graph)
קשתות הן זוגות לא סדורים של קודקודים {u,v}. הקשר הוא הדדי (אם u מחובר ל-v, אז v מחובר ל-u). רוב הדיון בתורת הגרפים מתייחס לגרפים לא מכוונים אלא אם צוין אחרת.
גרף מכוון (Directed Graph / Digraph)
קשתות הן זוגות סדורים של קודקודים (u,v), כאשר u הוא קודקוד המוצא ו-v הוא קודקוד היעד. הקשר הוא חד-כיווני (u מחובר ל-v, אך לא בהכרח v מחובר ל-u).
גרף פשוט (Simple Graph)
גרף שאינו מכיל קשתות מקבילות (מרובות) ואינו מכיל לולאות. אלו הגרפים הנפוצים ביותר במרבית היישומים.
גרף עם קשתות מרובות ולולאות (Multigraph/Pseudograph)
גרף שיכול להכיל קשתות מקבילות (שתי קשתות או יותר המחברות את אותם שני קודקודים) ו/או לולאות (קשת המחברת קודקוד לעצמו).
סוגי גרפים נפוצים
ישנם מספר סוגי גרפים "קלאסיים" שחשוב להכיר היטב, שכן הם משמשים כדוגמאות בסיסיות וכבסיס לגרפים מורכבים יותר.
גרף שלם (Complete Graph, K_n)
גרף לא מכוון שבו כל זוג קודקודים שונים מחובר על ידי קשת יחידה. לגרף K_n יש n קודקודים ו-n(n-1)/2 קשתות.
גרף מעגל (Cycle Graph, C_n)
גרף לא מכוון עם n קודקודים (n ≥ 3) ו-n קשתות, היוצרות מעגל יחיד. כל קודקוד מחובר בדיוק לשני קודקודים אחרים.
גרף מסלול (Path Graph, P_n)
גרף לא מכוון עם n קודקודים ו-n-1 קשתות, היוצרות מסלול יחיד. שני קודקודים בדרגה 1, והשאר בדרגה 2.
ייצוג גרפים
כדי לעבוד עם גרפים באלגוריתמים, אנו זקוקים לשיטות לייצוגם במחשב. לכל שיטה יתרונות וחסרונות משלה.
מטריצת שכנויות (Adjacency Matrix)
מטריצה בגודל |V|x|V| שבה A[i][j] = 1 אם קיימת קשת מ-i ל-j, ו-0 אחרת. בגרף לא מכוון, המטריצה סימטרית. קלה לבדיקת קיום קשת, אך דורשת מקום רב לגרפים דלילים (sparse).
מטריצת סמיכויות (Incidence Matrix)
מטריצה בגודל |V|x|E| שבה M[i][j] = 1 אם קודקוד i סמוך לקשת j, ו-0 אחרת. פחות נפוצה בשימוש מאשר מטריצת שכנויות או רשימת שכנויות.
רשימת שכנויות (Adjacency List)
מערך של רשימות, כאשר האיבר ה-i במערך מכיל רשימה של כל הקודקודים השכנים לקודקוד i. יעילה במקום ובזמן עבור גרפים דלילים, אך בדיקת קיום קשת דורשת זמן רב יותר.
למת לחיצות הידיים: אבן יסוד
למה זה חשוב? היא מדגישה את הקשר הבסיסי בין קודקודים לקשתות ומאפשרת להסיק מסקנות חשובות, כמו למשל שבכל גרף לא מכוון חייב להיות מספר זוגי של קודקודים בעלי דרגה אי-זוגית. הבנה והוכחה של למה זו הן קריטיות.
שאלות לדיון
- הגדירו גרף פשוט, גרף דו-צדדי וגרף דו-צדדי שלם. תנו דוגמה לכל אחד.
- כיצד משתנה מטריצת השכנויות בין גרף לא מכוון לגרף מכוון? מה לגבי רשימת השכנויות?
- האם גרף K_n יכול להיות גרף דו-צדדי? אם כן, מתי? אם לא, מדוע?
- הוכיחו את למת לחיצות הידיים עבור גרף לא מכוון.
נקודות לתשובת מודל
עבור השאלה: "האם גרף K_n יכול להיות גרף דו-צדדי? אם כן, מתי? אם לא, מדוע?"
- הגדרה נכונה של גרף דו-צדדי (חלוקת V ל-V1, V2 ללא קשתות פנימיות).
- הגדרה נכונה של K_n (כל זוג קודקודים מחובר).
- הבנה ש-K_n יכול להיות דו-צדדי רק אם n קטן מאוד.
- עבור n=1: K_1 הוא קודקוד בודד, ניתן לחלק אותו ל-V1={v}, V2={}. הוא דו-צדדי.
- עבור n=2: K_2 הוא שני קודקודים המחוברים בקשת. ניתן לחלק ל-V1={v1}, V2={v2}. הוא דו-צדדי.
- עבור n ≥ 3: K_n אינו יכול להיות דו-צדדי. כל שלושה קודקודים ב-K_n יוצרים מעגל באורך 3. בגרף דו-צדדי, כל המעגלים חייבים להיות באורך זוגי. מכיוון שמעגל באורך 3 אינו זוגי, K_n עבור n ≥ 3 אינו דו-צדדי.