מפת הסיבוכיות
EN
קודקוד חדש המחובר להכול

3COL ≤p 4COL

3COL≤p4COL\mathrm{3COL}\le_p\mathrm{4COL}, ולכן 4COL\mathrm{4COL} היא NP-שלמה. באופן כללי אותו רעיון נותן 3COL≤pkCOL\mathrm{3COL}\le_p k\mathrm{COL} לכל k≥3k\ge3 קבוע.

הבנייה

על קלט G=(V,E)G=(V,E):

  1. בנה G^\hat G על ידי הוספת קודקוד חדש v^\hat v, וחיבורו בקשת לכל הקודקודים ב-VV.
  2. החזר את G^\hat G.

בכלליות, עבור kCOLk\mathrm{COL}: מוסיפים k−3k-3 קודקודים חדשים, מחברים אותם זה לזה (קליקה) וכן כל אחד מהם לכל קודקודי VV.

הקודקוד v^\hat v "שורף" את הצבע הרביעי: הוא מחובר לכל קודקוד מקורי, ולכן אף קודקוד מקורי אינו יכול לקבל את צבעו.

המחשה

בנייה מודרכת

צביעה ב-3 → צביעה ב-4

שלב 1 מתוך 7
מצביעה ב-3 לצביעה ב-4: הוספת קודקוד אחד המחובר להכולבפאנל השמאלי גרף הקלט עם צביעה; בפאנל הימני אותו גרף בתוספת קודקוד חדש המחובר לכל קודקוד מקורי, עם הצביעה שלו. בצעדים המאוחרים הקלט מוחלף ב-K₄ ומושווים פונקציית הזהות, קודקוד מבודד נוסף, והבנייה האמיתית.מופע קלט של 3COLG = C₅v₁1v₂2v₃1v₄2v₅3C₅ ∈ 3COL ✓
קשת של G (נשמרת)צבע 1 (מקווקו)צבע 2 (רציף)צבע 3 (מנוקד)

נכונות — שני הכיוונים

3COL ∈ ⟹ 4COL ∈

נניח G∈3COLG\in\mathrm{3COL}; קיימת צביעה חוקית f:V→{1,2,3}f:V\to\{1,2,3\}. נגדיר g:V^→{1,2,3,4}g:\hat V\to\{1,2,3,4\} על ידי g(v)={f(v)v∈V4אחרתg(v)=\begin{cases} f(v) & v\in V\\ 4 & \text{אחרת}\end{cases} תהא e=xy∈E^e=xy\in\hat E.

  • אם e∈Ee\in E: אז g(x)=f(x)g(x)=f(x) ו-g(y)=f(y)g(y)=f(y), ומכיוון ש-ff חוקית ב-GG נובע g(x)≠g(y)g(x)\ne g(y).
  • אחרת ee קשת חדשה, ולכן x=v^x=\hat v או y=v^y=\hat v. הקודקוד v^\hat v צבוע 44 והשני צבוע בצבע מ-{1,2,3}\{1,2,3\}, ולכן שוב g(x)≠g(y)g(x)\ne g(y).

לכן gg צביעה חוקית ב-4 צבעים, כלומר G^∈4COL\hat G\in\mathrm{4COL}.

4COL ∈ ⟹ 3COL ∈

נניח G^∈4COL\hat G\in\mathrm{4COL}; קיימת צביעה חוקית g:V^→{1,2,3,4}g:\hat V\to\{1,2,3,4\}. ללא הגבלת הכלליות g(v^)=4g(\hat v)=4 — הצבעים סימטריים לחלוטין, ואם v^\hat v קיבל צבע אחר נחליף את שמות שני הצבעים.

נגדיר f(v)=g(v)f(v)=g(v) לכל v∈Vv\in V, ונראה שהטווח בפועל הוא {1,2,3}\{1,2,3\}: יהי x∈Vx\in V. מכיוון שחיברנו את v^\hat v לכל קודקודי VV, מתקיים xv^∈E^x\hat v\in\hat E, ולכן g(x)≠g(v^)=4g(x)\ne g(\hat v)=4. לכן f(x)∈{1,2,3}f(x)\in\{1,2,3\} לכל x∈Vx\in V.

כעת תהא xy∈Exy\in E. לא הסרנו קשתות, ולכן גם xy∈E^xy\in\hat E, ומחוקיות gg ב-G^\hat G נקבל f(x)=g(x)≠g(y)=f(y)f(x)=g(x)\ne g(y)=f(y). לכן ff צביעה חוקית של GG בשלושה צבעים, כלומר G∈3COLG\in\mathrm{3COL}.

סיבוכיות הרדוקציה

זמןO(|V| + |E|)
מקוםO(|V| + |E|)
גודל הפלט|V| + 1 vertices, |E| + |V| edges

הבנייה מוסיפה קודקוד אחד ו-∣V∣|V| קשתות, ולכן היא ליניארית בגודל הקלט. הפלט גדול מהקלט בפחות מפי שניים ועוד קבוע.

מה זה קונה

4COL\mathrm{4COL} היא NP-שלמה. יחד עם 2COL∈P\mathrm{2COL}\in\mathrm P מתקבלת התמונה המלאה: k=2k=2 קל, k≥3k\ge3 קשה — קפיצה חדה בדיוק במקום אחד.

מלכודות

  • הזהות אינה עובדת. אם GG הוא 33-צביע אז בפרט הוא 44-צביע — הכיוון הראשון עובד, וזו בדיוק הסיבה לחשוד. הכיוון השני קורס: K4K_4 הוא 44-צביע ובוודאות אינו 33-צביע, ולכן K4∈4COLK_4\in\mathrm{4COL} אבל K4∉3COLK_4\notin\mathrm{3COL}.

  • קודקוד חדש בלי קשתות אינו מספיק. הצעד "לכל x∈Vx\in V מתקיים g(x)≠4g(x)\ne4" נשען כולו על קיום הקשת xv^x\hat v. בלי הקשתות אין מניעה שקודקוד ב-VV ייצבע ב-44. דוגמה נגדית: K4K_4 בתוספת קודקוד מבודד הוא 44-צביע, ואילו K4K_4 אינו 33-צביע.

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

השרשרת

נשענת על

מאיפה זה נקרא

  • שיעור 11משפט 2: 4COL\mathrm{4COL} היא NP-complete
  • שיעור 10הרחבה (מוכחת בשיעור 11): 3COL≤p4COL\mathrm{3COL} \le_p \mathrm{4COL}