ברוכים הבאים ליחידת הלימוד בנושא צביעת גרפים ומישוריות בקורס "מתמטיקה בדידה". יחידה זו היא אבן יסוד בתורת הגרפים, המשלבת עקרונות תיאורטיים עם יישומים מעשיים רחבים במדעי המחשב ובתחומים אחרים. נלמד כיצד להקצות "צבעים" לאלמנטים בגרף תחת אילוצים שונים, וכיצד לזהות גרפים שניתן לציירם במישור ללא חיתוך קשתות. הבנה מעמיקה של נושאים אלו חיונית לא רק להצלחה בבחינה, אלא גם לפיתוח חשיבה אלגוריתמית ופתרון בעיות מורכבות.
צביעת גרפים: יסודות ומושגים
צביעת גרפים עוסקת בהקצאת צבעים לקודקודים, קשתות או פאות של גרף, כך שאלמנטים סמוכים יקבלו צבעים שונים. המטרה העיקרית היא למצוא את המספר המינימלי של צבעים הנדרשים לצביעה חוקית.
תכונות ומשפטים חשובים:
- גרפים דו-צדדיים: גרף $G$ הוא דו-צדדי אם ורק אם הוא ניתן לצביעה בשני צבעים, כלומר $\chi(G) = 2$. תכונה שקולה היא שאין בו מעגלים באורך אי-זוגי.
- משפט ברוקס (Brooks' Theorem): לכל גרף קשיר $G$ שאינו גרף שלם ואינו מעגל אי-זוגי, מתקיים $\chi(G) \le \Delta(G)$, כאשר $\Delta(G)$ היא הדרגה המקסימלית של קודקודי הגרף.
- משפט ארבעת הצבעים (Four Color Theorem): כל גרף מישורי ניתן לצביעה בארבעה צבעים לכל היותר. זהו אחד המשפטים המפורסמים והמורכבים בתורת הגרפים, שהוכח בעזרת מחשב.
גרפים מישוריים: הגדרות ותכונות
גרף מישורי הוא גרף שניתן לצייר אותו במישור כך שאף שתי קשתות לא יחתכו זו את זו (למעט בקודקודים משותפים). למושג זה חשיבות רבה בתכנון מעגלים מודפסים, מפות ועוד.
גרף מישורי (Planar Graph)
הגרף עצמו, ללא קשר לאופן שרטוטו. הוא קיים אם קיימת לו לפחות דרך אחת לשרטוט ללא חיתוך קשתות.
גרף מישורי משורטט (Plane Graph)
שרטוט ספציפי של גרף מישורי במישור, שבו אף קשת אינה חותכת קשת אחרת. זהו המימוש הגרפי של גרף מישורי.
נוסחת אוילר לגרפים מישוריים:
עבור כל גרף מישורי קשיר $G=(V,E)$ המשורטט במישור, מתקיים הקשר הבא בין מספר הקודקודים ($v$), מספר הקשתות ($e$) ומספר הפאות ($f$):
מנוסחת אוילר ניתן להסיק חסמים חשובים: לכל גרף מישורי פשוט קשיר עם $v \ge 3$ קודקודים, מתקיים $e \le 3v - 6$. אם הגרף אינו מכיל מעגלים באורך 3 (כלומר, אינו מכיל $K_3$), אז $e \le 2v - 4$.
משפט קורטובסקי: המפתח למישוריות
משפט קורטובסקי מספק אפיון מלא לגרפים מישוריים, ומאפשר לקבוע האם גרף נתון הוא מישורי או לא באמצעות זיהוי תתי-גרפים מסוימים.
משפט קורטובסקי (Kuratowski's Theorem): גרף הוא מישורי אם ורק אם הוא אינו מכיל תת-גרף שהוא חלוקה של $K_5$ (הגרף השלם עם 5 קודקודים) או חלוקה של $K_{3,3}$ (הגרף הדו-צדדי השלם עם 3 קודקודים בכל צד).
יישומים וקשרים בין צביעה למישוריות
צביעת גרפים ומישוריות הם נושאים בעלי יישומים מעשיים רבים:
- צביעת גרפים: תזמון משימות (קודקודים הם משימות, קשתות מייצגות התנגשות במשאבים), הקצאת תדרים, הקצאת אוגרים במעבד, לוחות זמנים.
- גרפים מישוריים: תכנון מעגלים מודפסים (PCB), שרטוט מפות, עיצוב רשתות תקשורת.
הקשר הבולט ביותר בין שני התחומים הוא משפט ארבעת הצבעים, הקובע חסם עליון למספר הצבעים הנדרש עבור כל גרף מישורי. למרות שהוכח, מציאת אלגוריתם יעיל לצביעה במספר הצבעים המינימלי (המספר הכרומטי) נותרה בעיה קשה (NP-קשה) באופן כללי.
שאלות לדיון
- כיצד ניתן להשתמש בנוסחת אוילר כדי להוכיח שגרף מסוים אינו מישורי? תן דוגמה.
- האם גרף דו-צדדי יכול להכיל חלוקה של $K_5$? נמק.
- הסבר את ההבדל בין המספר הכרומטי של גרף לבין הדרגה המקסימלית שלו. מתי הם זהים ומתי שונים?
- כיצד ניתן להשתמש במשפט קורטובסקי כדי להוכיח שגרף פיטרסן אינו מישורי?
נקודות לתשובת מודל
- נוסחת אוילר: יש לבדוק האם הגרף מקיים את החסמים $e \le 3v-6$ או $e \le 2v-4$ (אם אין $K_3$). אם לא, הוא אינו מישורי. יש לציין שהיא תקפה רק לגרפים קשירים.
- גרף דו-צדדי ו-$K_5$: $K_5$ אינו דו-צדדי (מכיל מעגלים אי-זוגיים). חלוקה של $K_5$ גם היא אינה דו-צדדית. לכן, גרף דו-צדדי אינו יכול להכיל חלוקה של $K_5$.
- מספר כרומטי מול דרגה מקסימלית: המספר הכרומטי הוא המספר המינימלי, בעוד שהדרגה המקסימלית היא חסם עליון (לפי משפט ברוקס). הם זהים בגרפים שלמים או מעגלים אי-זוגיים. בגרפים אחרים, המספר הכרומטי יכול להיות קטן יותר.
- גרף פיטרסן וקורטובסקי: יש להראות כי גרף פיטרסן מכיל חלוקה של $K_{3,3}$. ניתן לעשות זאת על ידי בחירת 6 קודקודים מתאימים ו-9 קשתות המקשרות ביניהם, תוך התעלמות מקודקודים בדרגה 2 שנוצרים בתהליך החלוקה.