Petr Hliněný, FI MU Brno 1 FI: MA010: Barevnost a další
7 Barevnost a další těžké problémy
Již dříve jsme si připomínali jeden z historických kamenů teorie grafů ­ slavný problém sedmi
mostů v Královci (dnešním Kaliningradě). Další neméně slavný problém pochází z poloviny
19. století a je obvykle zvaný problémem čtyř barev.
Na rozdíl od sedmi mostů, problém čtyř barev zůstal nevyřešený po více než 100 let!
Kolik barev je třeba použít na obarvení politické mapy pro rozlišení sousedních států?
Někteří matematici však kladou prapočátky teorie grafů daleko před Eulerovými sedmi mosty či
problémem čtyř barev, až ke středověké otázce, zda lze šachovým koněm obejít celou šachovnici
bez opakování.
Tato otázka nakonec vede k dalšímu zajímavému a obtížnému problému tzv. Hamiltonovské
kružnice v grafu. . . 2
Stručný přehled lekce
* Definice barevnosti grafu, základní vlastnosti.
* Varinaty problému barvení. Další problémy jako Hamiltonovská kruž-
nice.
* Algoritmická obtížnost základních grafových problémů.
Petr Hliněný, FI MU Brno 2 FI: MA010: Barevnost a další
7.1 Barevnost grafu
Nejprve si uveďme pojem barevnosti ­ představme si, že hrany grafu nám říkají, že jejich
koncové vrcholy musí být barevně odlišené (třeba proto, že reprezentují sousední státy,
nebo proto, že jinak jsou si příliš podobné a je třeba je jinak rozlíšit, atd). 2Samozřejmě
bychom mohli každému vrcholu grafu dát jinou barvu, ale k čemu by pak takový problém
byl? My bychom chtěli použít barev celkem co nejméně. 2
Definice: Obarvením grafu G pomocí k barev myslíme libovolné zobrazení
c : V (G)  {1, 2, . . ., k}
takové, že každé dva vrcholy spojené hranou dostanou různé barvy, tj. c(u) = c(v) pro
všechny {u, v}  E(G).
Definice 7.1. Barevnost grafu G
je nejmenší číslo (G) pro které existuje obarvení grafu G pomocí (G) barev. 2
Čísla 1, 2, . . ., k z předchozí definice tak nazýváme barvami vrcholů (je to pohodlnější,
než popisovat barvy běžnými jmény jako bílá, červená, atd).
Poznámka: Uvědomme si, že barevnost lze definovat pouze pro graf bez smyček, protože oba
konce smyčky mají vždy stejnou barvu a nic s tím nenaděláme.
Petr Hliněný, FI MU Brno 3 FI: MA010: Barevnost a další
Lema 7.2. Nechť G je jednoduchý graf (bez smyček) na n vrcholech. Pak (G)  n
a rovnost nastává právě když G  Kn je úplný graf. 2
Důkaz: Stačí každý vrchol obarvit jinou barvou a máme skutečné obarvení n barvami
dle definice. Navíc pokud některá dvojice u, v vrcholů není spojená hranou, můžeme
volit lepší obarvení c(u) = c(v) = 1 a zbylé vrcholy různými barvami 2, 3, . . . , n - 1,
tj. pak (G) < n. 2
Petr Hliněný, FI MU Brno 4 FI: MA010: Barevnost a další
Příklad 7.3. Vraťme se k příkladu ,,barvení mapy z úvodu lekce a ukažme si, jak mapy
souvisejí s grafy a jejich barevností.
1
1 2
3 4
2
3
1
a
b c
d e
f
g
h
s
s s
s s
s
s
s
a
b
c
d
e
f
g
h
2
Jednotlivé oblasti na mapě (předpokládáme, že každý stát má souvislé území, tj. státy =
oblasti) prohlásíme za vrcholy našeho grafu a sousední dvojice států spojíme hranami. Nezapomeňme,
že ,,sousední znamená sdílení celého úseku hranice, ne jen jednoho rohu. 2
Při troše snahy také najdeme lepší obarvení uvedené mapy využívající pouhých tří barev:
2
1 2
3 1
2
3
1
s
s s
s s
s
s
s
2
1
2
3
1
2
3
1
2
Petr Hliněný, FI MU Brno 5 FI: MA010: Barevnost a další
Věta 7.4. Neprázdný graf G má barevnost 1 právě když nemá žádné hrany.
G má barevnost 2 právě když nemá žádnou kružnici liché délky jako podgraf. 2
Důkaz: Pokud graf nemá hrany, můžeme všechny vrcholy obarvit stejnou barvou 1.
Naopak pokud mají všechny vrcholy stejnou barvu, nemůže graf mít žádnou hranu.2
Druhá část: Na jednu stranu, lichou kružnici nelze obarvit dvěma barvami, viz obrázek.
Na druhou stranu si představme, že zvolíme libovolný vrchol v grafu G s barvou 1 a
ostatní vrcholy obarvíme takto: Vrcholy, jejichž vzdálenost od v je lichá, obarvíme 2.
Vrcholy, jejichž vzdálenost od v je sudá, obarvíme 1.
s s
s
s
s
1 2
1
2
??
s
s
s
s
s
s
s
v
2
1
1
2
1
2
12
Pokud bychom tak získali třeba dva vrcholy spojené hranou f v sudé vzdálenosti od v, získáme
uzavřený sled S liché délky přes f a v. Stejně tak pro dva vrcholy v liché vzdálenosti.
Vezmeme-li ze sledu S ty hrany, které se opakují lichý počet krát, dostaneme Eulerovský podgraf
T lichého počtu hran. Jak již víme (Oddíl 4.1), T pak obsahuje kružnici a tudíž jej lze
induktivně sestrojit jako hranově-disjunktní sjednocení kružnic. Avšak sjednocení kružnic sudé
délky nevytvoří T liché velikosti, spor. Proto naše obarvení za daných předpokladů nemůže
dát stejnou barvu sousedním vrcholům, a tudíž dvě barvy stačí. 2
Petr Hliněný, FI MU Brno 6 FI: MA010: Barevnost a další
Hladové obarvování
Definice: Graf G je k-degenerovaný, pokud každý podgraf G obsahuje vrchol stupně
nejvýše k.
Příkladem k-degenerovaného grafu je každý graf stupně nejvýše k, ale na druhou stranu kdegenerované
grafy mohou mít vysoké stupně. (Nestačí však mít jen nízký nejmenší stupeň!)
2
Věta 7.5. Každý k-degenerovaný graf lze správně hladově obarvit k + 1 barvami. 2
Důkaz: Jelikož graf G je k-degenerovaný, vybereme libovolný jeho vrchol v1 stupně
nejvýše k a rekurzivní aplikací tohoto postupu obarvíme podgraf G - v1, který je
podle definice také k-degenerovaný. Nakonec si všimneme, že  k sousedé vrcholu v1
dostanou nejvýše k různých barev, takže v1 dobarvíme zbylou barvou. 2
Důležité aplikace této věty uvidíme v příští lekci, avšak jedno zajímavé zesílení (Brooksovu
větu) si uvedeme nyní:
Petr Hliněný, FI MU Brno 7 FI: MA010: Barevnost a další
Věta 7.6. Nechť G je souvislý jednoduchý graf maximálního stupně k  2. Pak
(G)  k až na případy, kdy G je úplný graf nebo lichá kružnice.
Důkaz (náznak): Pro k = 2 plyne tvrzení z Věty 7.4. Nechť tedy k  3. V jednom
směru je jasné, že (Kk+1) = k + 1. Naopak tedy předpokládejme, že G není úplný.
Zároveň se omezme jen na případ, že G má všechny stupně rovné k, neboť jinak lze
aplikovat postup z Věty 7.5. 2
* Prvním krokem nahlédneme, že pak G obsahuje dva nespojené vrcholy u, v se
společným sousedem w. Pokud ale je graf G-{u, v} nesouvislý, pak graf příslušně
rozdělíme a indukcí po částech obarvíme. 2
* Přidejme tedy předpoklad, že G-{u, v} je souvislý. Druhým krokem nahlédneme,
že graf H vzniklý z G - w ztotožněním u s v do jednoho vrcholu je (k - 1)degenerovaný.
2
* Tudíž graf H hladově obarvíme k barvami podle Věty 7.5. Po opětovném ,,rozpojení
vrcholů u, v získáme obarvení G-w k barvami takové, že u, v mají stejnou
barvu. Nyní w má v sousedství nejvýše k - 1 barev a G celý obarvíme.
2
Petr Hliněný, FI MU Brno 8 FI: MA010: Barevnost a další
Grafy vysoké barevnosti
Ke správnému pochopení barevnosti grafu je nezbytné se zamyslet, které grafy mají
vysokou barevnost. Jedná se například o grafy obsahující velké kliky (úplné podgrafy).
Je to však vše? 2
Není! Lze nalézt grafy s libovolně vysokou barevností neobsahující ani trojúhelníky.
Tvrzení 7.7. (Mycielski) Graf získaný z grafu G následující konstrukcí (viz obrázek)
má barevnost (G) + 1 a neobsahuje trojúhelníky, pokud je neobsahuje ani G.
2
Nejobecněji lze říci následující překvapivé tvrzení:
Věta 7.8. (Erd˝os) Pro každá c, r > 0 existuje graf s barevností alespoň c a neobsahující
kružnice kratší než r.
Petr Hliněný, FI MU Brno 9 FI: MA010: Barevnost a další
7.2 Variace na barevnost a jiné
Definice 7.9. Hranová barevnost grafu G.
Hledáme obarvení ce(E(G))  {1, 2, . . ., k} takové, že žádné dvě hrany se společným
vrcholem nedostanou stejnou barvu.
Nejmenší možný počet barev k, pro které hranové obarvení existuje, se nazývá hranová
barevnost e(G) grafu. 2
Na rozdíl od běžné barevnosti umíme hranovou barevnost docela ostře aproximovat.
Věta 7.10. (Vizing) Pro každý jednoduchý graf platí (G)  e(G)  (G) + 1.
Platí, že většina grafů splňuje (G) = e(G). Umíte jednoduše sestrojit (a dokázat) příklady
pro druhý případ?
Problém přesného určení hranové barevnosti grafu však stále zůstává algoritmicky velmi
obtížný a také úzce souvisí s problémem čtyř barev.
Petr Hliněný, FI MU Brno 10 FI: MA010: Barevnost a další
Definice 7.11. Výběrová barevnost grafu G.
Je dán graf G spolu s přiřazenými ,,seznamy barev L : V (G)  
k (k-prvkové
podmnožiny). Nyní hledáme obarvení cch(V (G))   takové, že žádné dva sousední
vrcholy nedostanou stejnou barvu a navíc cch(v)  L(v) pro každý vrchol v.
Nejmenší možná délka k seznamů barev, pro kterou výběrové obarvení vždy existuje
(tj. pro každou možnou takovou volbu seznamů), se nazývá výběrová barevnost ch(G)
grafu. 2
Výběrová barevnost může (kupodivu!) být libovolně ,,vzdálena běžné barevnosti.
Tvrzení 7.12. Pro každé k nalezneme bipartitní graf s výběrovou barevností větší
než k. 2
Fakt: Hranová výběrová barevnost úplných bipartitních grafů úzce souvisí se známým
problémem latinských obdélníků.
Petr Hliněný, FI MU Brno 11 FI: MA010: Barevnost a další
Hamiltonovské grafy
Definice: Kružnice C obsažená v grafu G se nazývá Hamiltonovská, pokud C prochází
všemi vrcholy G. Obdobně mluvíme o Hamiltonovské cestě P v G, pokud cesta P  G
prochází všemi vrcholy G.
Graf G je Hamiltonovský, pokud obsahuje Hamiltonovskou kružnici. 2
Možná to zní překvapivě, ale i problém Hamiltonovské kružnice úzce souvisel s řešením
problému čtyř barev. To je však mimo rámec našeho textu.
Věta 7.13. (Dirac) Každý graf na n  3 vrcholech s minimálním stupněm  n/2 je
Hamiltonovský. 2
Důkaz (náznak): Nechť P je nejdelší cesta v grafu G s vrcholy po řadě u0, u1, . . . , uk.
Podle její maximality leží každý soused u0 i uk na P. Pak existuje 0 < i < k takové,
že u0ui+1  E(G) a zároveň ukui  E(G). Pak u0ui+1 P ukui P tvoří kružnici v G a
snadno plyne, že se jedná o Hamiltonovskou kružnici. 2
Petr Hliněný, FI MU Brno 12 FI: MA010: Barevnost a další
7.3 N P-úplnost grafových problémů
Definice složitostní třídy NP se týká výhradně rozhodovacích problémů (s ,,ANO/NE odpovědí).
Dá se neformálně říci, že problém patří do třídy NP, pokud jeho odpověď ANO lze
prokázat (ve smyslu ,,uhodnout a ověřit ) výpočtem, který běží v polynomiálním čase.
NP-úplné problémy jsou zhruba řečeno ty, které ve třídě NP mají nejvyšší obtížnost řešení.
Od jednoho NP-úplného problému A se dostaneme k jinému B tzv. polynomiálním převodem:
Ukážeme, jak bychom ze známého postupu řešení B efektivně nalezli řešení (libovolné
instance) A. 2
Nyní si ukážeme vhodnými převody, že oněch ,,nejobtížnějších (NP-úplných) problémů
je v teorii grafů mnoho, bohužel by se dalo říci většina. To ostatně ukazuje,
proč jsme zatím v praxi tak málo úspěšní při počítačovém řešení mnohých praktických
problémů ­ přesné a efektivní řešení NP-úplných úloh se totiž všeobecně považuje za
nemožné.
Problém 7.14. 3-SAT (splnitelnost logických formulí ve spec. verzi)
Následující problém je NP-úplný:
Vstup: Logická formule  v konjunktivním normálním tvaru taková, že každá klauzule
obsahuje nejvýše 3 literály.
Výstup: Existuje logické ohodnocení proměnných tak, aby výsledná hodnota  byla 1
(pravda)?
Petr Hliněný, FI MU Brno 13 FI: MA010: Barevnost a další
Problém 7.15. 3-COL (3-obarvení grafu)
Následující problém je NP-úplný:
Vstup: Graf G.
Výstup: Lze vrcholy G korektně obarvit 3 barvami?
Důkaz (náznak): Ukážeme si polynomiální převod z problému 3-SAT. 2
Sestrojíme graf G pro danou formuli . Základem grafu je trojúhelník, jehož vrcholy
označíme X, T, F. Každé proměnné xi ve  přiřadíme dvojici vrcholů spojených s X.
Každé klauzuli ve  přiřadíme podgraf na 6 vrcholech (z nichž tři jsou spojené s T ), jako
na obrázku. Nakonec volné ,,půlhrany z obrázku pospojujeme dle toho, jaké literály
vystupují v klauzulích.
s
s
s
X
F
T
s
s
s
s
x1
x1
...
xi
xi
s
s
s
...
ss
s
(x1  xi  . . .)
Pak G má 3-obarvení právě když je  splnitelná, jak si lze ověřit na obrázku. 2
Petr Hliněný, FI MU Brno 14 FI: MA010: Barevnost a další
Problém 7.16. IS (nezávislá množina)
Následující problém je NP-úplný:
Vstup: Graf G a přirozené číslo k.
Výstup: Lze v G najít nezávislou podmnožinu velikosti (aspoň) k? 2
Důkaz: Ukážeme polynomiální převod z problému 3-COL.
Nechť H je graf na n vrcholech, který je za úkol obarvit třemi barvami. Položíme k = n
a graf G sestrojíme ze tří disjunktních kopií grafu H takto:
s
s
s
s
s
H
v
s
s
s
s
s
s
s
s
s
s
s
s
s
s
s
G
Tv
2
Pokud c : V (H)  {1, 2, 3} je obarvení H třemi barvami, v grafu G lze vybrat k = n
nezávislých vrcholů tak, že pro každý v  V (H) vezmeme c(v)-tou kopii vrcholu v
v grafu G. Naopak pokud I je nezávislá množina v grafu G o velikosti k = n, pak
z každého trojúhelníku Tv, v  V (H) náleží do I právě jeden vrchol. Podle toho již
určíme jednu ze tří barev pro vrchol v v H. 2
Petr Hliněný, FI MU Brno 15 FI: MA010: Barevnost a další
Problém 7.17. VC (vrcholové pokrytí)
Následující problém je NP-úplný:
Vstup: Graf G a přirozené číslo k.
Výstup: Lze v G najít vrcholové pokrytí, tj. množinu C  V (G) takovou, že každá
hrana G má alespoň jeden konec v C, o velikosti nejvýše k? 2
Důkaz: Ukážeme polynomiální převod z problému IS. Nechť G je graf na n vrcholech,
v němž máme najít nezávislou množinu I velikosti . Všimněme si, že doplněk C =
V (G) \ I nezávislé množiny I je vlastně vrcholovým pokrytím. Takže v našem převodu
stačí použít stejný graf G a k = n - . 2
s s
ss
s s
ss
f
f
f
s s
ss
s s
ss
f
f
f f
f
nezávislá množina vrcholové pokrytí
Petr Hliněný, FI MU Brno 16 FI: MA010: Barevnost a další
Problém 7.18. DOM (dominující množina)
Následující problém je NP-úplný:
Vstup: Graf G a přirozené číslo k.
Výstup: Lze v G najít dominující množinu, tj. množinu D  V (G) takovou, že každá
vrchol G má některého souseda v D, o velikosti nejvýše k?2
Důkaz (náznak): Problém dominující množiny jasně patří do NP a jeho úplnost je
dokázána následujícím schematickým polynomiálním převodem.
s s
ss
s
f
ff

s s
ss
s
s
s
s
s
s
s
f
ff
Graf H vytvoříme z grafu G přidáním, pro každou hranu e  E(G), nového vrcholu ve
spojeného hranami do obou koncových vrcholů hrany e. (Tak se vlastně z každé hrany
stane trojúhelník s třetím novým vrcholem, viz naznačený obrázek.) Číselný parametr k
zůstane tentokrát nezměněn. Nyní zbývá dokázat, že G má vrcholové pokrytí velikosti
k, právě když H má dominující množinu velikosti právě k, což není obtížné. 2
Petr Hliněný, FI MU Brno 17 FI: MA010: Barevnost a další
Problém 7.19. HC (Hamiltonovský cyklus)
Následující problém je NP-úplný:
Vstup: Orientovaný graf G.
Výstup: Lze v G najít orientovanou kružnici (cyklus) procházející všemi vrcholy?2
Problém 7.20. HK (Hamiltonovská kružnice)
Následující problém je NP-úplný:
Vstup: Graf G.
Výstup: Lze v G najít kružnici procházející všemi vrcholy? 2
Důkaz:
sv

s s s
Pv
Použijeme snadný převod z předchozího problému HC. Každý vrchol v orientovaného
grafu H nahradíme třemi vrcholy tvořícími cestu Pv délky 2 v grafu G. Orientované
hrany grafu H přicházející do v pak přivedeme do prvního vrcholu cesty Pv, hrany
odcházející z v naopak vedeme z posledního vrcholu cesty Pv. 2
Petr Hliněný, FI MU Brno 18 FI: MA010: Barevnost a další
7.4 Příběh problému vrcholového pokrytí
Bylo nebylo, jednou se dva slovutní informatici (při surfování na moři?) začali zabývat otázkou,
proč dva tak ,,podobné problémy jako vrcholové pokrytí a dominující množina mají (přestože
oba NP-úplné) tak rozdílné algoritmické chování. . .
Ale dost pohádek, více konkrétních informací čtenář najde v [R. Downey, M. Fellows, Parametrized
complexity, Springer 1999]. Mimo jiné se dozví, že tato zdánlivě okrajová otázka
dala vzniknout zcela novému pohledu na výpočetní složitost problémů, který jde ,,jaksi mimo
klasickou polynomiální hierarchii a umožňuje docela rozumně řešit i některé problémy, které
jsou jinak NP-těžké. 2
Takže v čem spočívá zásadní rozdíl v našich znalostech o řešení problémů dominující
množiny a vrcholového pokrytí?
* Pokud se v analýze zaměříme na hodnotu parametru k vstupu, tak dominující
množinu velikosti k stejně nedokážeme nalézt rychleji než probráním prakticky
všech k-tic vrcholů grafu G.
To je i pro malé fixní hodnoty k, třeba k = 10, 20 v praxi neproveditelné. 2
* Avšak vrcholové pokrytí velikosti k dokážeme nalézt jednoduchým algoritmem
v čase O(2k
 n), což pro malé fixní hodnoty k dává skvěle použitelný lineární
algoritmus!
Petr Hliněný, FI MU Brno 19 FI: MA010: Barevnost a další
Algoritmus 7.21. k-VC (vrcholové pokrytí)
Pro fixní k vyřešíme následující problém.
Vstup: Graf G.
Výstup: Lze v G najít vrcholové pokrytí o velikosti nejvýše k? 2
Pro inicializaci položíme C =  a F = E(G).
* Pokud F = , vracíme C jako vrcholové pokrytí.
Jinak pokud |C|  k, vracíme odpověď NE.
* Vybereme libovolnou hranu f = uv  F a pro oba její konce x = u, v uděláme:
­ C
= C  {x} a F
vytvoříme z F odebráním všech hran vycházejících z
vrcholu x v G.
­ Rekurzivně zavoláme tento algoritmus pro G, C
a F
. 2
Kolik tento algoritmus provede rekurzivních volání celkem? Každý průchod generuje
dvě další volání, ale jen do fixní hloubky k, takže ve výsledku bude čas výpočtu jen
O(2k
 n).
Poznámka: Dnes je již známo, že faktor 2k
lze promyšlenějším přístupem ,,vylepšit na mnohem
menší základ mocniny. (2006: 1.2738k
)