יחידה 9: צביעת גרפים ומישוריות

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

צביעת גרפים: עקרונות ויישומים

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

משפטים מרכזיים בצביעת גרפים:

• משפט ברוקס (Brooks' Theorem): עבור גרף קשיר G שאינו גרף שלם ואינו מעגל אי-זוגי, מתקיים χ(G) ≤ Δ(G), כאשר Δ(G) הוא הדרגה המקסימלית של קודקוד ב-G.
• משפט ויזינג (Vizing's Theorem): עבור כל גרף פשוט G, מתקיים Δ(G) ≤ χ'(G) ≤ Δ(G) + 1. משפט זה מחלק גרפים לשתי מחלקות: מחלקה 1 (χ'(G) = Δ(G)) ומחלקה 2 (χ'(G) = Δ(G) + 1).

מישוריות גרפים: ייצוג גיאומטרי ומאפיינים

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

נוסחת אוילר לגרפים מישוריים:

עבור כל גרף מישורי קשיר G עם V קודקודים, E קשתות ו-F פאות בשיכון מישורי כלשהו, מתקיים: V - E + F = 2.

מנוסחת אוילר נובעות מספר תכונות חשובות לגרפים מישוריים פשוטים:

• אם G גרף מישורי פשוט וקשיר עם V ≥ 3 קודקודים, אז E ≤ 3V - 6.
• אם G גרף מישורי פשוט וקשיר ללא מעגלים באורך 3 (כלומר, ללא משולשים), ועם V ≥ 3 קודקודים, אז E ≤ 2V - 4.

משפטים מרכזיים וקריטריונים למישוריות

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

משפט קורטובסקי (Kuratowski's Theorem):

גרף G הוא מישורי אם ורק אם הוא אינו מכיל תת-גרף שהוא חלוקה של K₅ (הגרף השלם עם 5 קודקודים) או חלוקה של K_3,3 (הגרף הדו-צדדי השלם עם 3 קודקודים בכל צד) כמינור.

משפט ארבעת הצבעים (Four Color Theorem):

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

שאלות לדיון

• הסבירו את הקשר בין המספר הכרומטי של גרף לבין בעיות תזמון במשאבים מוגבלים. תנו דוגמה קונקרטית.
• כיצד ניתן להשתמש בנוסחת אוילר כדי להוכיח שגרף נתון אינו מישורי? תנו דוגמה לגרף והראו את ההוכחה.
• השוו בין משפט קורטובסקי למשפט ארבעת הצבעים בהקשר של גרפים מישוריים. מה חשיבותו של כל אחד מהם?
• תארו מצב בו צביעה חמדנית (Greedy Coloring) אינה נותנת את המספר הכרומטי המינימלי. כיצד ניתן להתמודד עם אתגר זה?

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

• קשר צביעה-תזמון: קודקודים מייצגים משימות/אירועים, קשתות מייצגות קונפליקטים (לא יכולים להתרחש בו-זמנית), וצבעים מייצגים משאבים/יחידות זמן. המספר הכרומטי הוא מספר המשאבים/זמנים המינימלי הנדרש. דוגמה: תזמון בחינות, הקצאת תדרים.
• הוכחת אי-מישוריות עם אוילר: אם גרף G קשיר ופשוט עם V קודקודים ו-E קשתות מקיים E > 3V-6 (או E > 2V-4 אם הוא ללא משולשים), אז G אינו מישורי. דוגמה: K₅ (V=5, E=10). 3V-6 = 3*5-6 = 9. מכיוון ש-10 > 9, K₅ אינו מישורי.
• השוואת קורטובסקי וארבעת הצבעים:
  • קורטובסקי: נותן קריטריון מבני הכרחי ומספיק למישוריות – גרף מישורי אם ורק אם אינו מכיל חלוקה של K₅ או K_3,3 כמינור. זהו כלי להבנת המבנה הפנימי של גרפים מישוריים ואי-מישוריים.
  • ארבעת הצבעים: קובע תכונה של גרפים מישוריים – כל גרף מישורי ניתן לצבוע ב-4 צבעים לכל היותר. זהו משפט קיום, ללא קריטריון מבני ישיר. חשיבותו ביישומים כמו צביעת מפות.
• צביעה חמדנית לא אופטימלית: צביעה חמדנית תלויה בסדר הקודקודים. דוגמה: גרף מעגל C₃ (משולש). אם נצבע קודקודים v1, v2, v3, נקבל 3 צבעים (אופטימלי). אם ניקח גרף P₃ (שלושה קודקודים בטור v1-v2-v3), נצבע v1 (צבע 1), v3 (צבע 1), v2 (צבע 2). סדר זה נותן 2 צבעים, וזה אופטימלי. אבל אם נצבע v1 (צבע 1), v2 (צבע 2), v3 (צבע 1), זה גם אופטימלי. אם נשנה את הסדר ל-v1,v2,v3 בגרף שהוא מעגל C5, צביעה חמדנית יכולה להשתמש ב-3 צבעים, בעוד המספר הכרומטי הוא 3. דוגמה טובה יותר: גרף כוכב K_1,n. אם נצבע את המרכז ראשון, ואז את העלים, נקבל 2 צבעים. אם נצבע עלה, ואז את המרכז, ואז את העלים האחרים, עדיין 2 צבעים. דוגמה קלאסית לכישלון צביעה חמדנית היא גרף בעל 3 קודקודים v1, v2, v3 וקשתות (v1,v2), (v2,v3). המספר הכרומטי הוא 2. אם סדר הצביעה הוא v1, v3, v2: v1 מקבל צבע 1. v3 מקבל צבע 1. v2 סמוך לשניהם, ולכן מקבל צבע 2. סה"כ 2 צבעים. אבל אם ניקח גרף עם 4 קודקודים v1, v2, v3, v4 וקשתות (v1,v2), (v2,v3), (v3,v4), (v4,v1) (מעגל C4). המספר הכרומטי הוא 2. אם נצבע בסדר v1, v2, v3, v4: v1 (צבע 1), v2 (צבע 2), v3 (צבע 1), v4 (צבע 2). סה"כ 2 צבעים. צביעה חמדנית יכולה להיות לא אופטימלית עבור גרפים מורכבים יותר. למשל, גרף עם קודקודים v1, v2, v3, v4, v5 וקשתות (v1,v2), (v2,v3), (v3,v4), (v4,v5), (v5,v1) (מעגל C5). המספר הכרומטי הוא 3. אם נצבע בסדר v1, v2, v3, v4, v5: v1 (צבע 1), v2 (צבע 2), v3 (צבע 1), v4 (צבע 2), v5 (צבע 3, כי סמוך ל-v1 ו-v4). סה"כ 3 צבעים. האתגר הוא למצוא סדר קודקודים אופטימלי. דרכים להתמודד: שימוש בהיוריסטיקות לסדר קודקודים (למשל, צביעה לפי דרגה יורדת), אלגוריתמי צביעה מורכבים יותר (כמו backtracking), או שימוש בחסמים תחתונים ועליונים למספר הכרומטי.