Loading AI tools
מוויקיפדיה, האנציקלופדיה החופשית
צביעת קשתות של גרף היא השמה של צבעים לקשתות הגרף כך שלשום קודקוד אין זוג קשתות הנוגעות בו וצבועות באותו הצבע. בעיית הצביעה ב-K צבעים היא השאלה האם ניתן לעשות זאת עם קבוצה של K צבעים. דרך אחרת לנסח זאת היא לשאול האם ניתן לחלק את קשתות הגרף ל-K קבוצות כך שכל קבוצה מהווה שידוך. האינדקס הכרומטי של גרף הוא המספר הקטן ביותר של צבעים בו ניתן לצבוע את קשתות הגרף. בגרף שדרגתו המקסימלית היא d חייבים להשתמש בלפחות d צבעים (על פי עקרון שובך היונים). גרפים מסוימים ניתנים לצביעה ב-d צבעים: מעגל זוגי ניתן לצביעה בשני צבעים, הגרף השלם על 2n קודקודים ניתן לצביעה ב d=2n-1 צבעים (ראו דוגמה בציור) וכל גרף דו-צדדי ניתן לצביעה ב- d צבעים (הדבר נובע ממשפט קניג (König)). לעומת זאת מעגל אי-זוגי ניתן לצביעה רק בשלושה צבעים.
משפט ויזינג (נקרא על שמו של ואדים ויזינג שפרסם אותו ב-1964) קובע כי כל גרף פשוט (ללא קשתות מקבילות) ניתן לצביעה ב d+1 צבעים. כלומר האינדקס הכרומטי שלו הוא d או d+1. לגבי גרפים שאינם פשוטים (מולטיגרפים), קלוד שנון הראה כי האינדקס הכרומטי חסום על ידי וביטוי זה הדוק במובן שיש גרפים לגביהם זה האינדקס הכרומטי. למרות האפיון ההדוק יחסית של משפט ויזינג, ההכרעה האם האינדקס הכרומטי של גרף נתון הוא d או d+1 היא בעיה NP-שלמה והדבר נכון גם לגרפים שדרגתם 3, כפי שהראה הולייר[1].
גרפים d רגולריים (כאלה שהדרגה של כל הקודקודים היא d) ניתנים לצביעה ב-d או d+1 צבעים. גרף פיטרסן (ראו תמונה) הוא דוגמה לגרף שלוש רגולרי שהאינדקס הכרומטי שלו הוא ארבע.
לגרפים דו-צדדיים יש אלגוריתמים מאוד יעילים למציאת צביעה ב-d צבעים, כאלה שזמן הריצה שלהם הוא [2].
תחום נוסף בתורת הגרפים הקשור בצביעה הוא צביעה של קודקודים. ניתן לנסח את בעיית הצביעה בקשתות של גרף כבעיית הצביעה בקודקודים של גרף הקשתות (line graph) של הגרף.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
