מתמטיקה בדידה: תורת הקבוצות, קומבינטוריקה ותורת הגרפים

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

תכונות יסוד של עצים

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

עץ (Tree): גרף קשיר וחסר מעגלים (acyclic).

יער (Forest): גרף חסר מעגלים. כל רכיב קשירות ביער הוא עץ.

תכונות מרכזיות של עצים:

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

עצים פורשים ומינימליים

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

עץ פורש (Spanning Tree): עבור גרף קשיר G=(V,E), עץ פורש הוא תת-גרף T=(V,E') של G שהוא עץ ומכיל את כל קודקודי G.

עץ פורש מינימלי (Minimum Spanning Tree - MST): עבור גרף קשיר ממושקל G=(V,E), עץ פורש מינימלי הוא עץ פורש שסכום משקלי הקשתות שלו הוא מינימלי מבין כל העצים הפורשים האפשריים.

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

גרפים דו-צדדיים

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

גרף דו-צדדי (Bipartite Graph): גרף G=(V,E) הוא דו-צדדי אם ניתן לחלק את קבוצת הקודקודים V לשתי קבוצות זרות V1 ו-V2 כך שכל קשת ב-E מחברת קודקוד מ-V1 לקודקוד מ-V2 (כלומר, אין קשתות בתוך V1 או בתוך V2).

תכונות מרכזיות של גרפים דו-צדדיים:

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

השוואת מושגים וקשרים

הבנת הקשרים וההבדלים בין סוגי הגרפים השונים חיונית להבנה עמוקה של החומר.

עץ

גרף קשיר וחסר מעגלים. תמיד דו-צדדי (ניתן לצבוע בשני צבעים).

גרף קשיר

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

גרף דו-צדדי

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

חשוב לזכור: כל עץ הוא גרף קשיר, וכל עץ הוא גם גרף דו-צדדי. לעומת זאת, לא כל גרף קשיר הוא עץ (כי הוא יכול להכיל מעגלים), ולא כל גרף קשיר הוא דו-צדדי.

שאלות לדיון

הוכח: גרף קשיר עם n קודקודים ו-n-1 קשתות הוא עץ.
הסבר מדוע כל עץ הוא גרף דו-צדדי. תאר אלגוריתם לצביעת עץ בשני צבעים.
נתון גרף G. כיצד ניתן לקבוע האם G הוא דו-צדדי? נמק את תשובתך והדגם על גרף המכיל מעגל באורך 5.
האם עץ פורש מינימלי (MST) הוא תמיד יחיד? אם כן, הוכח. אם לא, תן דוגמה נגדית.

נקודות לתשובת מודל

לשאלה 1: ניתן להוכיח באינדוקציה על מספר הקודקודים, או על ידי שימוש בתכונה שגרף קשיר עם n קודקודים מכיל לפחות n-1 קשתות, וגרף עם n קודקודים ו-n-1 קשתות שאינו עץ חייב להיות לא קשיר (סתירה).
לשאלה 2: עץ אינו מכיל מעגלים כלל, ולכן בפרט אינו מכיל מעגלים באורך אי-זוגי. אלגוריתם: בחר קודקוד שרירותי, צבע אותו בצבע 1. צבע את כל שכניו בצבע 2. צבע את שכני השכנים בצבע 1, וכן הלאה (BFS או DFS). מכיוון שאין מעגלים, לא תהיה סתירה בצביעה.
לשאלה 3: גרף הוא דו-צדדי אם ורק אם אין בו מעגלים באורך אי-זוגי. ניתן להשתמש באלגוריתם צביעה בשני צבעים (למשל, BFS): מתחילים מקודקוד שרירותי, צובעים אותו בצבע 1, את שכניו בצבע 2, את שכני השכנים בצבע 1 וכן הלאה. אם במהלך הצביעה נתקלים בקשת המחברת שני קודקודים מאותו צבע, הגרף אינו דו-צדדי (כי נמצא מעגל אי-זוגי). אחרת, הוא דו-צדדי. דוגמה לגרף עם מעגל באורך 5: C5 (מעגל עם 5 קודקודים) אינו דו-צדדי.
לשאלה 4: לא בהכרח. אם כל משקלי הקשתות שונים, אז ה-MST יחיד. אם קיימות קשתות בעלות משקל זהה, ייתכנו מספר MSTs שונים בעלי אותו משקל כולל. דוגמה נגדית: גרף עם 3 קודקודים A, B, C וקשתות (A,B) במשקל 1, (B,C) במשקל 1, (A,C) במשקל 2. שני MSTs אפשריים: {(A,B), (B,C)} ו-{(A,B), (A,C)} (אם נניח ש-(A,C) היה במשקל 1 גם כן). דוגמה טובה יותר: ריבוע (מעגל C4) עם כל הקשתות במשקל 1. ישנם 4 עצים פורשים מינימליים שונים, כל אחד מסיר קשת אחת מהמעגל.

מצאתם טעות או שחסר משהו?