imported>Idoiz: הכפלת ו' לאחר אותיות שימוש

2026-01-21T18:31:14Z

הכפלת ו' לאחר אותיות שימוש

דף חדש

ב[[תורת הגרפים]], '''גרף <math>n</math>-צביע''' הוא [[גרף (תורת הגרפים)|גרף]] שאפשר לצבוע את ה[[קודקוד]]ים שלו ב-n צבעים, כך ששני קודקודים סמוכים אינם צבועים באותו צבע.

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

עבור <math>k>2</math>, ההכרעה האם <math>\chi(G)=k</math> היא בעיה [[NP_(סיבוכיות)|NP שלמה]]. לגרף יש מספר כרומטי 2 [[אם ורק אם]] אין בו מעגל באורך אי זוגי.

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

השערה מפורסמת אחרת בהקשר לצביעת גרפים הועלתה ב-1960 על ידי המתמטיקאי הצרפתי קלוד ברגה (Berge) השערת ה[[גרף מושלם|גרף המושלם]], אשר העלה אותה בהקשר לרעיון מ[[תורת האינפורמציה]] של קיבול אפס שגיאה (zero-error capacity) בגרף. השערת המשפט הייתה פתוחה במשך שנים רבות עד שהוכחה על ידי [[מריה צ'ודנובסקי|צ'ודנובסקי]], רוברטסון, סימור ותומאס ב-2006.{{הערה|Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006). "The strong perfect graph theorem". Annals of Mathematics 164 (1): 51–229.|כיוון=שמאל}}

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

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

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

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

נסמן ב-<math>\alpha(G)</math> את גודל תת-הקבוצה ה[[קבוצה בלתי תלויה (תורת הגרפים)|בלתי תלויה]] הגדולה ביותר, אז <math>\chi(G)\geq \frac{n}{\alpha(G)}</math>.

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

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

== יישומים ==
בעיית צביעת גרפים מופיעה בבעיות מגוונות כשאלגוריתמים בתחום זה שימושים בהקשר של בעיות של תזמון משימות, הקצאת [[אוגר (מחשבים)|אוגרים]], זיהוי תבניות ופתרון תשבצי [[סודוקו]].{{הערה|שם=Lewis2015|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|עמ=98, 98–105, 101|שנת הוצאה=1982-06-23|doi=10.1145/800230.806984, 10.1145/872726.806984|קישור=http://dl.acm.org/citation.cfm?id=800230.806984,%20http://dl.acm.org/citation.cfm?id=872726.806984}}}} כאשר המהדר בונה גרף תלויות, כאשר משתנים מיוצגים על ידי קודקודים וקשתות מחברות בין זוגות קודקודים אם המשתנים שלהם נדרשים באותו הזמן. מספר הצביעה של הגרף מגדיר את מספר האוגרים הנדרש לשמירת המשתנים בזמן נתון.

==ראו גם==
* [[משפט ארבעת הצבעים]]
* [[משפט לובאס-קנזר]]

{{תורת הגרפים}}
==קישורים חיצוניים==
{{ויקישיתוף בשורה}}
* {{MathWorld}}

== הערות שוליים ==
{{הערות שוליים}}
{{בקרת זהויות}}

[[קטגוריה:תורת הגרפים]]
[[קטגוריה:בעיות NP-קשות]]

גרף n-צביע - היסטוריית גרסאות

imported>Idoiz: הכפלת ו' לאחר אותיות שימוש