7 Barevnost a dalsi tezke problémy Pro motivaci této lekce se podíváme hlouběji do historie počátků grafů v matematice. Kromě slavného problému sedmi mostů v Královci (dnešním Kaliningradě) je za další historický milník vývoje teorie grafů považován problém čtyř barev pocházející z poloviny 19. století: Kolik nejméně barev je třeba použít na obarvení politické mapy pro rozlišení sousedních států? Na rozdíl od sedmi mostů, problém čtyř barev zůstal nevyřešený po více než 100 let a stimuloval rozvoj skoro všech moderních oblastí teorie grafů. Někteří však kladou prapočátky grafů v matematice 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 vede v moderním pojetí k dalšímu zajímavému a obtížnému problému tzv. Hamiltonovské kružnice v grafu. . . Stručný přehled lekce • Definice barevnosti grafu, základní vlastnosti. • Varinaty problému barvení. • Další „obtížné" problémy jako Hamiltonovská kružnice. • Algoritmická složitost (NP-úplnost) základních grafových problémů. Petr Hliněný, Fl MU Brno 1 Fl: 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 rozlišit, atd). Samozř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ě, c Definice: Obarvením grafu G pomocí k barev myslíme libovolné zobrazení c:V(Q)^{l,2,...,k} takové, že každé dva vrcholy spojené hranou dostanou různé barvy, tj. c(u) ^ c(v) pro všechny {u,v} G E(G). Definice 7.1. Barevnost grafu G je nejmenší číslo x{G) Pro které existuje obarvení grafu G pomocí x{G) barev, c Čí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. ________str Hliněný, Fl MU Brn MA010: Barevnost a další Lema 7.3. Nechť G je jednoduchý graf (bez smyček) na n vrcholech. Pak \(G) < n a rovnost nastává právě když G c; Kn je úplný graf. a 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 x(G) / Definice: Graf G je k-degenerovaný, pokud každý podgraf G obsahuje vrchol stupně nejvýše k. Příkladem fc-degenerovaného grafu je každý graf stupně nejvýše k, ale na druhou stranu k-degenerované grafy mohou mít vysoké stupně. (Nestačí však mít jen nízký nejmenší stupeň!) Věta 7.6. Každý k-degenerovaný graf lze správně hladově obarvit k + 1 barvami. Důkaz: Jelikož graf G je fc-degenerovaný vybereme libovolný jeho vrchol v\ stupně nejvýše k a rekurzivní aplikací tohoto postupu obarvíme podgraf G — v\, který je podle definice také fc-degenerovaný Nakonec si všimneme, že < k sousedé vrcholu v\ dostanou nejvýše k různých barev, takže v\ dobarvíme zbylou barvou. D Důležité aplikace této věty uvidíme v příští lekci, avšak jedno zajímavé zesílení (Brook-sovu větu) si uvedeme nyní: Petr Hliněný, Fl MU Brno 6 Fl: MA010: Barevnost a další Věta 7.7. Nechť G je souvislý jednoduchý graf maximálního stupně k > 2. Pak x(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.5. Nechť tedy k > 3. V jednom směru je jasné, že x(Kk+i) = 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.6. c • Prvním krokem nahlédneme, že pak G obsahuje dva nespojené vrcholy u,v se společným sousedem w. Pokud aleje graf G— {u,v} nesouvislý, pak graf příslušně rozdělíme a indukcí po částech obarvíme. • 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 «sodo jednoho vrcholu je (k — 1)-degenerovaný c • Tudíž graf H hladově obarvíme k barvami podle Věty 7.6. 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 — \ barev a G celý obarvíme. D Detr Hliněný, Fl MU Bn Fl: 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? d Není! Lze nalézt grafy s libovolně vysokou barevností neobsahující ani trojúhelní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. Petr Hliněný, Fl MU Bn -I: MA010: Barevnost a další Definice 7.10. 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 Xe(G) grafu, c Na rozdíl od běžné barevnosti umíme hranovou barevnost docela ostře aproximovat. Věta 7.11. (Vizing) Pro každý jednoduchý graf platí A(G) < \e{G) < A(G) + 1. Platí, že většina grafů splňuje A(G) = Xe(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ý, Fl MU Brno 9 Fl: MA010: Barevnost a další Definice 7.12. Výběrová barevnost grafu G. Je dán graf G spolu s přiřazenými „seznamy barev" L : V (G) —> (fc) (fc-prvkové podmnožiny). Nyní hledáme obarvení cch(V(G)) —> IN takové, že žádné dva sousední vrcholy nedostanou stejnou barvu a navíc cch(v) G 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, c Výběrová barevnost může (kupodivu!) být libovolně „vzdálena" běžné barevnosti. Tvrzení 7.13. Pro každé k nalezneme bipartitní graf s výběrovou barevností větší než k. d Fakt: Hranová výběrová barevnost úplných bipartitních grafů úzce souvisí se známým problémem latinských obdélníků. etr Hliněný, Fl MU Brno 10 Fl: MA010: Barevnost a další 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 C G prochází všemi vrcholy G. Graf G je Hamiltonovský, pokud obsahuje Hamiltonovskou kružnici, c 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.14. (Dirac) Každý graf na n > 3 vrcholech s minimálním stupněm > n/2 je Hamiltonovský. c Důkaz (náznak): Nechť P je nejdelší cesta v grafu G s vrcholy po řadě «o, «i,..., «fc. Podle její maximality leží každý soused uq i «fc na P. Pak existuje 0 < i < k takové, že MoMj+i G E(G) a zároveň u^ui G E(G). Pak moMj+i Pu^ui P tvoří kružnici v G a snadno plyne, že se jedná o Hamiltonovskou kružnici. D etr Hliněný, Fl MU Brno 11 Fl: MA010: Barevnost a další 7.3 ArP-ú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', pokud jeho odpověď ANO lze prokázat (ve smyslu „uhodnout a ověřit") výpočtem, který běží v polynomiálním čase. ATV-úp\né problémy jsou zhruba řečeno ty, které ve třídě MV mají nejvyšší obtížnost řešení. Od jednoho A/'P-ú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. c Nyní si ukážeme vhodnými převody, že oněch „nejobtížnějších" (7VP-ú 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í TVP-úplných úloh se totiž všeobecně považuje za nemožné. Problém 7.15. 3-SAT (splnitelnost logických formulí ve spec. verzi) Následující problém je MV-ú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ý, Fl MU Brno 12 Fl: MA010: Barevnost a další Problém 7.16. 3-COL (3-obarvení grafu) Následující problém je MV-ú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. c 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é Xj 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. (xi V -iXj V . ..) Pak G má 3-obarvení právě když je $ splnitelná, jak si lze ověřit na obrázku. D Petr Hliněný, Fl MU Brne -I: 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 podmnožinu velikosti (aspoň) kl c 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: H 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 G 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 G V (H) náleží do I právě jeden vrchol. Podle toho již určíme jednu ze tří barev pro vrchol v v H. D ________t Hliněný, Fl MU Brn I: MA010: Barevnost a další ^ Vstup: Graf G a přirozené číslo k. Výstup: Lze v G najít vrcholové pokrytí, tj. množinu C C V(G) takovou, že každá hrana G má alespoň jeden konec v C, o velikosti nejvýše kl c 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 i. Všimněme si, že doplněk C = V (G) \I nezávislé množiny /je vlastně vrcholovým pokrytím. Takže v našem převodu stačí použít stejný graf G a k = n — í. ü nezávislá množina vrcholové pokrytí 3etr Hliněný, Fl MU Brno 15 Fl: MA010: Barevnost a další Problém 7.19. DOM (dominující množina) Následující problém je NV-úplný: Vstup: Graf G a přirozené číslo k. Výstup: Lze v G najít dominující množinu, tj. množinu D C V(G) takovou, že každá vrchol G má některého souseda v D, o velikosti nejvýše kle Důkaz (náznak): Problém dominující množiny jasně patří do J\ÍV a jeho úplnost je dokázána následujícím schematickým polynomiálním převodem. H G Pro daný graf H vytvoříme graf G přidáním, pro každou hranu e G E (H), nového vrcholu ve spojeného hranami do obou koncových vrcholu 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 také k, což není obtížné. ü :tr Hliněný. Fl MU Bri Fl: MA010: Barevnost a další Problém 7.20. HC (Hamiľtonovský cyklus) Následující problém je ATP-úplný: Vstup: Orientovaný graf G. Výstup: Lze v G najít orientovanou kružnici (cyklus) procházející všemi vrcholyľc Problém 7.21. HK (Hamiltonovská kružnice) Následující problém je ATP-úplný: Vstup: Graf G. Výstup: Lze v G najít kružnici procházející všemi vrcholy? c Důkaz: 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. D -*etr Hlinený, hl MU Brn( Fl: MA010: Barevnost a další Příběh problému vrcholového pokrytí Bylo nebylo, jednou se dva slovutní informatici (při surfovaní 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 ATV-úp\né) tak rozdílné algoritmické chování. . . Ale dost pohádek, více konkrétních informací čtenář najde v [R. Downey and M. Fellows, Parameterized 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 AÍV-téiké. a 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-ť\c vrcholů grafu G. To je i pro malé fixní hodnoty k, třeba k = 10,20 v praxi neproveditelné. • Avšak vrcholové pokrytí velikosti k dokážeme nalézt jednoduchým algoritmem v čase 0(2k ■ n), což pro malé fixní hodnoty k dává skvěle použitelný lineární algoritmus! Petr Hliněný, Fl MU Brno 18 Fl: MA010: Barevnost a další Algoritmus 7.23. k-\IQ. (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 kl □ Pro inicializaci položíme C = 0 a F = E (G). • Pokud F = 0, vracíme C jako vrcholové 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ěláme: — C' = C U {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'. c 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 0(2k -n). Poznámka: Dnes je již známo, že faktor 2 lze promyšlenějším přístupem „vylepšit" na mnohem menší základ mocniny. (2006: 1.2738fc) 3etr Hliněný, Fl MU Brno 19 Fl: MA010: Barevnost a další