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

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

עצים: המבנה היסודי ביותר

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

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

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

תכונות מפתח של עצים:

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

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

גרפים מיוחדים נוספים ויישומיהם

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

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

גרף מישורי (Planar Graph): גרף שניתן לצייר אותו במישור כך שאף שתי קשתות לא יחתכו זו את זו (למעט בקודקודים).

גרף מכוון חסר מעגלים (DAG - Directed Acyclic Graph): גרף מכוון שאינו מכיל אף מעגל מכוון.

משפטים ותכונות חשובות:

גרפים דו-צדדיים: גרף הוא דו-צדדי אם ורק אם אין בו מעגלים באורך אי-זוגי. יישומים: שידוכים (matching), תזמון.
גרפים מישוריים:
- נוסחת אוילר: עבור גרף מישורי קשיר עם v קודקודים, e קשתות ו-f פאות (אזורים), מתקיים v - e + f = 2.
- משפט קורטובסקי (Kuratowski's Theorem): גרף הוא מישורי אם ורק אם אין לו תת-גרף שהוא חלוקה של K5 או K3,3. זהו משפט מהותי לאפיון גרפים מישוריים.
גרפים מכוונים חסרי מעגלים (DAGs):
- ניתן לבצע מיון טופולוגי (Topological Sort) לקודקודיו. זהו סדר ליניארי של הקודקודים כך שלכל קשת (u,v), u מופיע לפני v בסדר.
- יישומים: תזמון משימות, ניתוח תלות.

גרף דו-צדדי

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

גרף מישורי

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

גרף מכוון חסר מעגלים (DAG)

מאפשר מיון טופולוגי. מהותי בייצוג תלויות בין משימות או אירועים.

שאלות לדיון

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

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

הוכחת תכונת עץ: התחילו מההנחה שהגרף קשיר ועם n-1 קשתות. השתמשו בהוכחה בדרך השלילה או באינדוקציה, תוך התייחסות לעובדה שהוספת קשת לעץ יוצרת מעגל, והסרת קשת מעץ מנתקת אותו.
אלגוריתם קרוסקל: תארו את השלבים (מיון קשתות, הוספה לפי סדר עולה תוך הימנעות ממעגלים). הסבירו את תכונת ה"חתך": קשת במשקל מינימלי החוצה חתך כלשהו חייבת להיות חלק מ-MST.
גרף דו-צדדי ומישורי: התשובה היא לא. דוגמה נגדית: K3,3 הוא גרף דו-צדדי אך אינו מישורי (לפי קורטובסקי).
בדיקת דו-צדדיות: השתמשו באלגוריתם BFS (חיפוש לרוחב) או DFS (חיפוש לעומק) לצביעת הקודקודים בשני צבעים לסירוגין. אם נתקלים בקשת המחברת שני קודקודים מאותו צבע, הגרף אינו דו-צדדי. הסיבוכיות היא O(V+E).
חשיבות משפט קורטובסקי: המשפט מספק אפיון מלא של גרפים מישוריים, כלומר קריטריון הכרחי ומספיק. הוא הופך את שאלת המישוריות לבעיה של מציאת תת-גרף מסוים (חלוקה של K5 או K3,3), ובכך מאפשר הוכחות וניתוחים פורמליים.

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