7   Barevnost a další těžké problémy
Pro motivaci teto lekce se pod íváme hlouběji do historie počátků grafu v matematice. Krome slavného problemu sedmi mostů v Královci (dneSn ím Kaliningrade) je za dalSÍ historický miln ík vývoje teorie grafů povaZovan problém Ctyr barev pochazej íc í z poloviny 19. stolet í: Kolik nejmene barev je treba pouZ ít na obarven í politicke mapý pro rozlisen í sousedn ích statů?
Na rozd íl od sedmi mostu, problem ctýr barev zustal nevýresený po více nez 100 let a stimuloval rozvoj skoro vsech modern ích oblast í teorie grafu.
Nekterí vsak kladou prapocatký grafu v matematice daleko pred Eulerovými sedmi mostý ci problemem ctýr barev, az ke stredoveke otazce, zda lze sachovým koném obejít celoů Šachovnici bez opakovan í. Tato otazka vede v modern ím pojetí k dalsímu zaj ímavemu a obtlznemu problemu tzv. Hamiltonovske kružnice v grafu. . . c
Stručný přehled lekce
• Definice barevnosti grafu, základní vlastnosti.
• Varinaty problemu barvení.
• DalSí „obtíZne" probiemy jako Hamiltonovska kruZnice.
• Algoritmicka sloZitost (NP-Uplnost) zakladních grafových problemU.
_Petr Hliněný,  FI MU Brno_1_FI: MA010: Barevnost a další
7.1   Barevnost grafu
Nejprve si uved'me pojem barevnosti - představme si, ze hrany grafu nam říkají, ze jejich koncové vrcholy musí byt barevně odlisene (treba proto, ze reprezentují sousední staty, nebo proto, ze jinak jsou si přílis podobne a je treba je jinak rozlísit, atd).□Samozrejme bychom mohli kazdemu vrcholu grafu dat jinou barvu, ale k Cemu by pak takovy problem byl? My bychom chteli pouzít barev celkem co nejmene. □
Definice: Obarvením grafu G pomocí k barev myslíme libovolne zobrazení
c : V (G) ^{1, 2,...,k}
takove, ze kazde dva vrcholy spojene hranou dostanou mzne barvy, tj. c(u) = c(v) pro vsechny {u,v} G E (G).
Definice 7.1. Barevnost grafu G
je nejmensí císlo x(G) pro ktere existuje obarvení grafu G pomocí x(G) barev. □
Čísla 1, 2,..., k z předchozí definice tak nazývame barvami vrcholu (je to pohodlnejsí, nez popisovat barvy beznymi jmeny jako bíla, červena, atd).
Poznámka: Uvědomme si, ze barevnost lze definovat pouze pro graf bez smyček, protože oba konce smyčky mají vzdy stejnou barvu a nič s tím nenadelame.
_Petr Hliněný,  FI MU Brno_2_FI: MA010: Barevnost a další
Lema 7.3. Nechť G je jednoduchý graf (bez smyček) na n vrcholech. Pak x(G) < n a rovnost nastává právě kdyZ G ~ Kn je úplný graf. c
Důkaz: Stačí každý vrchol obarvit jinou barvou a mame skutečné obarvení n barvami dle definice. Navíc pokud néktera dvojice u, v vrcholU není spojena hranou, mUžeme volit lepSí obarvení c(u) = c(v) = 1 a žbýle vrcholy mžnými barvami 2, 3,..., n — 1, tj. pak x(G) < n. □
Petr Hliněný,  FI MU Brno
FI: MA010: Barevnost a další
Příklad 7.4. Vraime se k příkladu „barvení" mapy z úvodu lekce a ukažme si, jak mapy souvisejí s grafy a jejich barevností.
Jednotlivé oblasti na mape (předpokládáme, ze každý stát má souvisle uzem í, tj. státy = oblasti) prohlásíme za vrcholy naseho grafu a sousedn í dvojice státu spoj íme hranami. Nezapomeňme, že „sousedn í" znamená sd ílen í celeho useku hranice, nejen jednoho rohu. c
Při trose snahy take najdeme lepsí obarven í uvedene mapy vyuz ívaj íc í pouhých trí barev:
Věta 7.5. Neprázdný graf G má barevnost 1 právě když nemá žádné hrany.
G má barevnost < 2 práve když nemá žádnou kružnici liché délky jako podgraf. c
Důkaz: Pokud graf nema hrany, můžeme všechny vrcholy obarvit stejnou barvou 1. Naopak pokud mají všechny vrcholy stejnou barvu, nemůže graf mít žadnou hranu.c
Druha cast: Na jednu stranu, lichou kružnici nelže obarvit dvema barvami, viž obrížek. Na druhou stranu si představme, že žvolíme libovolný vrchol v grafu G s barvou 1 a ostatní vrcholy obarvíme takto: Vrcholy, jejichž vždalenost od v je l ich a, obarvíme 2. Vrcholy, jejichž vždalenost od v je suda, obarvíme 1.
v A 1
1 .-. 2
2 ✓ 1 i
\ 2 * 1
» 2
/ 1c
Pokud bychom tak z ískali treba dva vrcholy spojené hranou f v sude vzdálenosti od v, z ískame uzavřený sled S liche delky přes f a v. Stejne tak pro dva vrcholy v liche vzdalenosti. Ponechame-li ze sledu S ty hrany, ktere se opakuj í lichy pocet krat, dostaneme Eulerovsky podgraf T licheho poctu hran. Jak jiz v íme (Odd íl 4.1), T pak obsahuje kruznici a tud íz jej lze induktivne sestrojit jako hranove-disjunktn í sjednocen í kruznic. Avsak sjednocen í kruznic sude delky nevytvorí T liche velikosti, spor. Proto nase obarven í za danych predpokladu nemuze dat stejnou barvu sousedn ím vrcholum, a tud íz dve barvy stac í. □
_Petr Hliněný,  FI MU Brno_5_FI: MA010: Barevnost a další
Hladové obarvování
Definice: Graf G je k-degenerovaný, pokud každý podgraf G obsahuje vrchol stupne nejvýše k.
Příkladem k-degenerovaneho grafu je každý graf stupne nejvýše k, ale na druhou stranu k-degenerovane grafý mohou m ít výsoke stupne. (Nestač í však m ít jen n ížký nejmenš í stupen!)
Véta 7.6. Každý k-degenerovany graf lze správně hladové obarvit k + 1 barvami. c
Důkaz: Jelikož graf G je k-degenerovaný, vybereme libovolný jeho vrchol v\ stupne nejvýše k a rekurzivní aplikací tohoto postupu obarvíme podgraf G — vi, který je podle definice take k-degenerovaný. Nakonec si vsimneme, že < k sousede vrcholu v1 dostanou nejvýse k mžných barev, takže v1 dobarvíme žbýlou barvou. □
Duležite aplikace teto vetý uvid íme v přístí lekci, avsak jedno žaj ímave žesílen í (Brooksovu vetu) si uvedeme nýní:
Petr Hliněný,  FI MU Brno
FI: MA010: Barevnost a další
Věta 7.7. Necht: G je souvislý jednoduchý graf maximálního stupně k > 2. Pak x(G) < k až na případy, kdý G je Úplný graf nebo lichá kružnice.
Důkaz (naznak): Pro k = 2 plyne tvrzení z Vety 7.5. Nechť tedy k > 3. V jednom smeru je jasne, Ze x(Kk+i) = k + 1. Naopak tedy předpokládejme, Ze G není úplný. Zaroven se omezme jen na případ, Ze G ma vSechny stupne rovne k, nebol: jinak lze aplikovat postup z Vety 7.6. c
• Prvním krokem nahledneme, ze pak G obsahuje dva nespojene vrcholy u, v se spoleCnym sousedem w. Pokud aleje graf G— {u, v} nesouvisly, pak graf príslusne rozdelíme a indukcí po castech obarvíme. c
• Přidejme tedy předpoklad, ze G —{u, v} je souvisly. Druhym krokem nahledneme, ze graf H vznikly z G — w ztotoznením u s v do jednoho vrcholu je (k — 1)-degenerovany. c
• Tudíz graf H hladove obarvíme k barvami podle Vety 7.6. Po opetovnem „rozpojení" vrcholu u, v získame obarvení G — w k barvami takove, ze u, v mají stejnou barvu. Nyní w ma' v sousedství nejvyse k — 1 barev a G cely obarvíme.
□
Petr Hliněný,  FI MU Brno
FI: MA010: Barevnost a další
Grafy vysoké barevnosti
Ke správnému pochopení barevnosti grafu je nezbytne se zamyslet, ktere grafy mají vysokou barevnost. Jedna se například o grafy obsahující velke kliky (Úplne podgrafy). Je to vsak vse? c
Není! Lze nalezt grafy s libovolně vysokou barevností neobsahující ani trojuhelníky.
Tvrzení 7.8. (Mycielski) Graf získaný z grafu G následující konstrukcí (viz obrázek) má barevnost x(G) + 1 a neobsahuje trojúhelníky, pokud je neobsahuje ani G.
Nejobecněji lze říci následující překvapivé tvrzení:
Věta 7.9. (Erdós) Pro každá c,r > 0 existuje graf s barevností alespoň c a neobsahující kružnice kratší než r.
c
v
Petr Hliněný,  FI MU Brno
FI: MA010: Barevnost a další
7.2   Variace na barevnost a jiné Definice 7.10. Hranova barevnost grafu G.
Hledáme obarvení ce(E(G)) — {1, 2,..., k} takové, ze žadné dve hrany se společným vrcholem nedostanou stejnou barvu.
NejmenSí možný počet barev k, pro ktere hranove obarvení existuje, se nažýva hranová barevnost Xe(G) grafu. c
Na rozdíl od bežne barevnosti umíme hranovou barevnost docela ostre aproximovat.
Veta 7.11. (Vizing) Pro každý jednoduchý graf platí A(G) < xe(G) < A(G) + 1.
Plat í, ze vetsina grafu splňuje A(G) = Xe(G). Um íte jednoduse sestrojit (a dokázat) príklady pro druhy prípad?
Problem presneho určení hranove barevnosti grafu vsak stale zustava algoritmicky velmi obtížný a take uzce souvisí s problemem čtyř barev.
Petr Hliněný,  FI MU Brno
FI: MA010: Barevnost a další
Definice 7.12. Vyberova barevnost grafu G.
Je dan graf G spolu s přiraženými „sežnamý barev" L : V(G) — (^) (k-prvkove podmnožiny). Nýn í hledame obarven í cch(V(G)) — N takove, že žadne dva sousedn í vrcholý nedostanou stejnou barvu a navíc cch(v) G L(v) pro každý vrchol v.
Nejmensí možna delka k sežnarrm barev, pro kterou výberove obarven í vždý existuje (tj. pro každou možnou takovou volbu sežnamm), se nažýva výberova barevnost ch(G) grafu. c
Výberova barevnost muže (kupodivu!) být libovolne „vždalena" bežne barevnosti.
Tvrzení 7.13. Pro každé k nalezneme bipartitnl graf s výberovou barevností větší než k. c
Fakt: Hranova výberova barevnost uplných bipartitních grafu užce souvisí se žnamým problemem latinských obdelnlkU.
Petr Hliněný,  FI MU Brr
FI: MA010: Barevnost a další
r
Hamiltonovske grafy
Definice: Kružnice C obsazena v grafu G se nazývá Hamiltonovská, pokud C prochází vsemi vrcholy G. Obdobne mluvíme o Hamiltonovske ceste P v G, pokud cesta P C G prochazí vSemi vrcholy G.
Graf G je Hamiltonovsky, pokud obsahuje Hamiltonovskou kruznici. c
Mozna to zní překvapivě, ale i problem Hamiltonovske kruznice uzce souvisel sřesením problemu ctýř barev. To je vsak mimo ramec naseho textu.
Veta 7.14. (Dirac) Každý graf na n > 3 vrcholech s minimálním stupněm > n/2 je Hamiltonovsky. c
DUkaž (naznak): Necht P je nejdelsí cesta v grafu G s vrcholy po řade u0, u1,..., uk. Podle její maximalitý lezí kazdý soused u0 i uk na P. Pak existuje 0 < i < k takove, ze uoui+i G E (G) a zaroven ukuj G E (G). Pak uoui+i Puk uj P tvoří kruznici v G a snadno plýne, ze se jedna o Hamiltonovskou kruznici. □
Petr Hliněný,  FI MU Brr
FI: MA010: Barevnost a další
7.3   NP-ůplnost grafových problěmů
Definice složitostní třídy MV 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 MV, pokůd jeho odpovéd' ANO lze prokázat (ve smyslů „ůhodnoůt a overit") výpoctem, který beží v polynomiálním case.
MV-ůplne problemy jsoů zhrůba receno ty, ktere ve tríde MV mají nejvyssí obtížnost resení.
Od jednoho MV-ůplneho problemů A se dostaneme k jinemů B tzv. polynomiálním převodem: Ukázeme, jak bychom ze známeho postůpů resení B efektivne nalezli resení (libovolne instance) A. c
Nyní si ukazeme vhodnymi převody, ze onech „nejobtíznějsích" (NP-uplnych) problemu je v teorii grafu mnoho, bohuzel by se dalo říci vetsina. To ostatne ukazuje, proc jsme zatím v praxi tak malo uspesní při pocítacovem řesení mnohych praktickych problemu - přesne a efektivní řesení NP-íplnych úloh se totiz vseobecne povazuje za
Problěm 7.15. 3-SAT (splnitělnost logických formulí vě spěc. věrzi)
Nýsledujřcř problém je NP-řplný:
Vstup: Logicka formule $ v konjunktivním normálním tvaru takoví, ze kazda klauzule
obsahuje nejvyřse 3 literaly. Výstup: Existuje logicke ohodnocení promennych tak, aby vysledna hodnota $ byla 1
nemořzne.
(pravda)?
V
Petr Hliněný,  FI MU Brr
FI: MA010: Barevnost a další
Problem 7.16. 3-COL (3-obarvení grafu)
Nasledující problém je MV-Úplný:
Vstup: Graf G.
Výstup: Lže vrcholy G korektne obarvit 3 barvami?
DUkaz (nažnak): Ukažeme si polynomialn í převod ž problemu 3-SAT. c
Sestroj íme graf G pro danou formuli $.  Zakladem grafu je trojuheln ík, jehož vrcholy
ožnac íme X, T, F. Každe promenne xj ve $ přiřad íme dvojici vrcholu spojenych s X.
Každe klaužuli ve $ přiřad íme podgraf na 6 vrcholech (ž nichž tři jsou spojene s T), jako na obražku. Nakonec volne „pulhrany" ž obražku pospojujeme dle toho, jake literaly vystupuj í v klaužul ích.
xi —xi
(xi V —xj V ...)
V
Pak G má 3-obarven í právě když je $ splnitelná, jak si lze ověřit na obrázku.
Petr Hliněný,  Fl MU Brno_13_FI: MA010: Barevnost a další
□
Problém 7.17. IS (nezávislá množina)
Následující problém je MV-úplný:
Vstup: Graf G a přirozené číslo k.
Výstup: Lze v G najít nezávislou podmnoZinu velikosti (aspon) k? c Důkaz: UkaZeme polynomialní převod z problemu 3-COL.
Necht H je graf na n vrcholech, ktery je za Ukol obarvit třemi barvami. Polozíme k = n a graf G sestrojíme ze trí disjunktních kopií grafu H takto:
H
/		r""	i
	—		
			
			
' —-—,	t——		
G
Pokud c : V (H) —> {1, 2, 3} je obarvení H třemi barvami, v grafu G lze vybrat k = n nezavislych vrcholu tak, ze pro kazdy v G V (H) vezmeme c(v)-tou kopii vrcholu v v grafu G. Naopak pokud I je nezavisla mnozina v grafu G o velikosti k = n, pak z kazdeho trojuhelníku Tv, v G V (H) nalezí do I prave jeden vrchol. Podle toho jiz urcíme jednu ze tří barev pro vrchol v v H. □
Petr Hliněný,  FI MU Brno_14_FI: MA010: Barevnost a další
V •
r
Problém 7.18. VC (vrcholové pokrytí)
Nasledující problém je MV-uplný:
Vstup: Graf G a prirozene Číslo k.
Výstup: Lze v G najít vrcholove pokryti, tj. mnozinu C C V (G) takovou, ze kazda hrana G ma alespon jeden konec v C, o velikosti nejvýse k? c
Důkaz: Ukazeme polynomialní prevod z problemu IS. Necht G je graf na n vrcholech, v nemz mame najít nezavislou mnozinu I velikosti l. Vsimneme si, ze doplnek C = V (G) \ I nezavisle mnoziny I je vlastne vrcholovým pokrytím. Takze v nasem převodu
stací pouzít stejny graf G a k
□
nezávislá mnozina
vrcholove pokrytí
Petr Hliněný,  FI MU Brn
FI: MA010: Barevnost a další
Problém 7.19. DOM (dominující množina)
Následující problém je MV-úplný:
Vstup: Graf G a přirozené c íslo k.
Výstup: Lze v G naj ít dominuj íc í mnoZinu, tj. mnoZinu D C V (G) takovou, Ze kaZda vrchol G ma některého souseda v D, o velikosti nejvýSe k?c
DUkaž (naznak): Problem dominuj íc í mnoZiný jasne patří do MV a jeho uplnost je dokazana nasleduj ícím schematickým polýnomialn ím prevodem.
H
G
Pro daný graf H vytvoříme graf G přidan ím, pro kaZdou hranu e G E (H), noveho vrcholu ve spojeneho hranami do obou koncových vrcholu hraný e. (Tak se vlastne z kaZde hraný stane trojuheln ík s třet ím novým vrcholem, viz naznacený obrazek.) Č íselný parametr k zustane tentokrat nezmenen. Nýn í zbýva dokazat, Ze G ma vr-cholove pokrýt í velikosti k, prave kdýZ H ma dominuj íc í mnoZinu velikosti take k, coZ nen í obt íZne. □
Petr Hliněný,  FI MU Brn
FI: MA010: Barevnost a další
Problém 7.20. HC (Hamiltonovský cyklus)
Následující problém je MV-úplný:
Vstup: Orientovaný graf G.
Výstup: Lze v G naj ít orientovanou kružnici (cýklus) procházej íc í všemi vrcholý?c
Problém 7.21. HK (Hamiltonovska kružnice)
Následující problém je MV-úplný:
Vstup: Graf G.
Výstup: Lze v G naj ít kružnici prochazej íc í všemi vrcholy? c DUkaž:
Pouzijeme snadný převod z předchozího probiemu HC. Kazdý vrchol v orientovaneho grafu H nahrad íme třemi vrcholý tvoříc ími cestu Pv delký 2 v grafu G. Orientovane hraný grafu H prichazej íc í do v pak privedeme do prvn ího vrcholu cestý Pv, hraný
odchazej íc í z v naopak vedeme z posledn ího vrcholu cestý Pv.
□
V
Petr Hliněný,  FI MU Brr
FI: MA010: Barevnost a další
7.4   Príbéh problémů vrcholového pokrytí
Bylo nebylo, jednou se dva slovutn í informatici (pri surfovan í na mori?) začali zabývat otázkou, proc dva tak „podobne" problémy jako vrcholové pokryt í a dominuj íc ímnoZina maj í(prestoZe oba NP-uplne) tak rozd ílne algoritmicke chovan í. . .
Ale dost pohadek, více konkretn ích informac í ctenar najde v [R. Downey and M. Fellows, Parameterized complexity, Springer 1999]. Mimo jine se dozví, ze tato zdanlive okrajova otazka dala vzniknout zcela novemu pohledu na vypocetn í slozitost problemu, ktery jde „jaksi mimo" klasickou polynomialn í hierarchii a umozňuje docela rozumne resit i nektere problemy, ktere jsou jinak NP-tezke. c
Takze v cem spocíva zasadní rozdíl v nasich znalostech o řesení problemu dominující mnoziny a vrcholoveho pokrytí?
• Pokud se v analyze zameříme na hodnotu parametru k vstupu, tak dominující mnozinu velikosti k stejne nedokazeme nalezt rychleji nez probraním prakticky vsech k-tic vrcholu grafu G.
To je i pro male fixní hodnoty k, treba k = 10, 20 v praxi neproveditelne. c
• Avsak vrcholove pokrytí velikosti k dokazeme nalezt jednoduchym algoritmem v case O(2k • n), coz pro male fixní hodnoty k dava skvele pouzitelny linearní algoritmus!
Petr Hlineny,  FI MU Brno 18 FI: MA010: Barevnost a další
Algoritmus 7.23. k-VC (vrcholově pokrytí)
Pro fixná k vyreSáme nasledující problem.
Vstup: Graf G.
Výstup: Lže v G najít vrcholove pokrytí o velikosti nejvyse k? c Pro inicializaci položíme C = 0 a F = E (G).
• Pokud F = 0, vracíme C jako vrcholove pokrytí. Jinak pokud |C| > k, vracíme odpoveď NE.
• Vybereme libovolnou hranu f = uv G F a pro oba její konce x = u, v udžlame:
— C' = C U {x} a F' vytvoěáme z F odebranám vžech hran vychazejících z vrcholu x v G.
— Rekurzivně zavolame tento algoritmus pro G, C' a F'. c
Kolik tento algoritmus provede rekurživních volaní celkem? Každy pruchod generuje dve dalsí volaní, ale jen do fixní hloubky k, takže ve vysledku bude cas vypočtu jen
O(2k • n).
Poznámka: Dnes je jiz znamo, ze faktor 2k lze promyslenejsím prístupem „vylepsit" na mnohem mensí zaklad mocniny. (2006: 1.2738fc)
Petr Hliněný,  FI MU Brr
FI: MA010: Barevnost a další