גרף n-צביע

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

עבור גרף $G$ , מסמנים ב- $\chi (G)$ את המספר הקטן ביותר של צבעים הדרוש לצביעת הקודקודים שלו. מספר זה נקרא מספר הצביעה (או המספר הכרומטי) של הגרף.

עבור $k>2$ , ההכרעה האם $\chi (G)=k$ היא בעיה NP שלמה. לגרף יש מספר כרומטי 2 אם ורק אם אין בו מעגל באורך אי זוגי.

היסטוריה

הקשר נפוץ שבו הופיעה בעיית צביעת גרף היא בעיית צביעה של גרפים מישוריים בדמות של צביעת מפות. בשנת 1852 בעת שניסה לצבוע מפה של מחוזות אנגליה, העלה פרנסיס גאת'רי את השערת ארבעת הצבעים, על פיה די בארבעה צבעים לצביעת מפה כך שאף אזור שגובל באזור אחר לא יחלוק עימו את אותו הצבע. אחיו של גאת'רי נועץ עם מורו למתמטיקה אוגוסטוס דה-מורגן בקולג' האוניברסיטאי של לונדון שהזכיר את הבעיה במכתב לויליאם המילטון. ב-1878 הובאה הבעיה לתשומת לבו של ארתור קיילי, שהציג אותה בפני החברה המלכותית הבריטית. אלפרד קמפ (Kempe) פרסם הוכחה למשפט, שהתקבלה על המתמטיקאים בני זמנו, אך התבררה כשגויה 11 שנה מאוחר יותר כשפרסי ג'ון היווד (Heawood) הצביע על טעות בהוכחה, אך הצליח להוכיח כי די בחמישה צבעים. ההוכחה לכך שאפשר להסתפק בארבעה נמצאה רק ב-1976 על ידי קנת' אפל (Appel) ווולפגנג האקן (Haken), והיא כרוכה בחיפוש ממוחשב על-פני אלפי מקרים.

השערה מפורסמת אחרת בהקשר לצביעת גרפים הועלתה ב-1960 על ידי המתמטיקאי הצרפתי קלוד ברגה (Berge) השערת הגרף המושלם, אשר העלה אותה בהקשר לרעיון מתורת האינפורמציה של קיבול אפס שגיאה (zero-error capacity) בגרף. השערת המשפט הייתה פתוחה במשך שנים רבות עד שהוכחה על ידי צ'ודנובסקי, רוברטסון, סימור ותומאס ב-2006.^[1]

חסמים על מספר הצביעה

עבור גרף $G$ עם $n$ צמתים מקבלים טריוויאלית ש- $1\leq \chi (G)\leq n$ .

אם מסמנים ב $\triangle (G)$ את הדרגה המקסימלית של צומת ב- $G$ אז $\chi (G)\leq \triangle (G)+1$ . תוצאה זאת ניתן לשפר בצורה הבאה: אם עבור $k\in \mathbb {N}$ בכל תת-גרף מושרה $H$ של $G$ קיים צומת $v\in H$ כך ש- $d_{H}(v)\leq k$ אז $\chi (G)\leq k+1$ . עבור $k=\triangle (G)$ תנאי זה נכון ולכן האי-שוויון גורר את החסם הקודם. עבור גרף שלם על n צמתים $\triangle (G)=n-1$ ו- $\chi (G)=n$ ועבור מעגל אי-זוגי $\triangle (G)=2$ ו $\chi (G)=3$ ומכאן שאי אפשר לשפר את המשפט באופן כללי. אולם משפט ברוקס קובע כי לכל שאר הגרפים הקשירים $\chi (G)\leq \triangle (G)$ .

נסמן ב- $\omega (G)$ את גודל הקליקה המקסימלית ב- $G$ אז $\chi (G)\geq \omega (G)$ . אם אי-שוויון זה הדוק עבור הגרף ועבור כל אחד מתתי הגרפים המושרים שלו, אז הגרף נקרא גרף מושלם.

נסמן ב- $\alpha (G)$ את גודל תת-הקבוצה הבלתי תלויה הגדולה ביותר, אז $\chi (G)\geq {\frac {n}{\alpha (G)}}$ .

הפולינום הכרומטי

מספר הדרכים לצבוע גרף נתון G ב- $\lambda$ צבעים נתון על ידי הצבה של $\lambda$ בפולינום $\chi (G,\lambda )$ , הקרוי הפולינום הכרומטי של הגרף. פולינום זה, שאותו גילה ג'ורג' בירקהוף ב-1912, מקיים את נוסחת הרקורסיה $\chi (G,\lambda )=\chi (G-e,\lambda )-\chi (G/e,\lambda )$ , לכל קשת e בגרף, כאשר G-e הוא הגרף ללא הקשת האמורה, ו-G/e הוא הגרף המתקבל מכיווץ הקשת לנקודה.

יישומים

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

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

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

ראו גם

קישורים חיצוניים

מדיה וקבצים בנושא גרף n-צביע בוויקישיתוף

גרף n-צביע, באתר MathWorld (באנגלית)

הערות שוליים

^ Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006). "The strong perfect graph theorem". Annals of Mathematics 164 (1): 51–229.
^ Lewis, R. A Guide to Graph Colouring: Algorithms and Applications. Springer International Publishers, 2015.
^ G. J. Chaitin, G. J. Chaitin, Register allocation & spilling via graph coloring, Register allocation & spilling via graph coloring, ACM SIGPLAN Notices 17, 1982-06-23, עמ' 98, 98–105, 101 doi: 10.1145/800230.806984, 10.1145/872726.806984

[1] Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006). "The strong perfect graph theorem". Annals of Mathematics 164 (1): 51–229.

[Lewis2015-2] Lewis, R. A Guide to Graph Colouring: Algorithms and Applications. Springer International Publishers, 2015.

[3] G. J. Chaitin, G. J. Chaitin, Register allocation & spilling via graph coloring, Register allocation & spilling via graph coloring, ACM SIGPLAN Notices 17, 1982-06-23, עמ' 98, 98–105, 101 doi: 10.1145/800230.806984, 10.1145/872726.806984

[1]

[2]

[3]