Petr Hliněný, FI MU Brno 1 FI: MA010: Dekompozice a minory 10 Dekompozice grafů, minory a algoritmy Další autorův výběr tématu nás zavede blíže ke strukturální teorii grafů, k různým jejich dekompozicím, grafovým minorům a navazujícím efektivním algoritmům pro jinak těžké problémy. Vrcholem této lekce je formulace hlavního výsledku takzvané ,,Graph Minors Theory od Robertsona a Seymoura, který lze bez nadsázky prohlásit za asi největší výsledek, kterého dosud teorie grafů dosáhla (i v porovnání s Větou o čtyřech barvách). 2 Stručný přehled lekce * Stromová šířka grafu ze čtyř stran. * Některé jiné "šířkové" parametry. * Ukázky použití dekompozic grafů na efektivní algoritmy. * Něco o grafových minorech a strukturální teorii. Petr Hliněný, FI MU Brno 2 FI: MA010: Dekompozice a minory 10.1 Tree-width ­ čtyři definice Velikost největší kliky v grafu G označujeme (G). Definice: Stromovou šířkou (tree-width) grafu G nazveme nejmenší přirozené k takové, že exituje chordální graf H s (H) = k + 1 obsahující G jako podgraf (H G). 2 ........ Definice: Vrcholy V (G) grafu G uspořádáme do posloupnosti (permutace) (v1, v2, . . . , vn). Pro i = 1, 2, . . ., n definujme (vi) jako počet všech indexů j {1, . . . , i - 1} takových, že vrcholy vi a vj jsou v G spojeny cestou používající pouze vrcholy z množiny {vj, vi, vi+1, . . . , vn}. Druhou stromovou šířkou grafu G nazveme nejmenší hodnotu výrazu maxv (v) přes všechny permutace vrcholů V (G). Petr Hliněný, FI MU Brno 3 FI: MA010: Dekompozice a minory Definice: Pro libovolný strom T uvažujeme (libovolné) zobrazení : E(G) V (T ). Pro vrchol t V (T ) označíme T1, . . . , Td jednotlivé komponenty lesa T - t a Fi = -1 V (Ti) . Označme (t) = |V (G)| + (d - 1) c(G) - d i=1 c(G - Fi), kde c(H) značí počet souvislých komponent grafu H. T1 T2 T3 x : E FxF1 F2 F3 Třetí stromovou šířkou grafu G pak definujeme jako nejmenší možnou, přes všechny dvojice T, , hodnotu výrazu max tV (T ) (t). Petr Hliněný, FI MU Brno 4 FI: MA010: Dekompozice a minory Nakonec si uvedeme ještě jednu definici, která se většinou uvádí jako ta první a hlavní (a na ostatní možné definice málokdy přijde řeč). Definice 10.1. Stromová dekompozice grafu G. Stromovou dekompozicí grafu G nazveme strom T spolu se systémem množin Xt pro t V (T ), kde * Xt V (G) a tV (T ) X t = V (G), * pro každou hranu e = uv E(G) je u, v Xt pro nějaké t V (T ), * (interpolační vlastnost) pro každý vrchol v V (G) tvoří podmnožina všech t V (T ) s v X t podstrom v T . 2 Šířkou dekompozice T, X rozumíme největší hodnotu |Xt| - 1 pro t V (T ) a čtvrtou stromovou šířkou grafu G nazveme nejmenší možnou šířku stromové dekompozice G. 2 Věta 10.2. Všechny čtyři výše uvedené definice stromové šířky definují přesně tutéž hodnotu, pokud graf G má neprázdnou množinu hran. Petr Hliněný, FI MU Brno 5 FI: MA010: Dekompozice a minory 10.2 Některé další parametry Definice: Cestní dekompozici a šířku (path-width) grafu G definujeme stejně jako v Definici 10.1Tree-width ­ čtyři definicetheorem.10.1, jen požadujeme navíc, aby T byla cesta. 2 Definice: Vrcholy V (G) grafu G uspořádáme do posloupnosti (permutace) (v1, v2, . . . , vn). Bandwidth grafu G definujeme jako nejmenší hodnotu výrazu maxvivj E(G) |i - j| přes všechny permutace vrcholů V (G). 2 Graf je kubický, pokud má všechny vrcholy stupně 3. Strom je podkubický, pokud má všechny vrcholy stupně 3. Pro libovolný graf G a podmnožinu F E(G) definujeme funkci souvislosti G(F) jako počet vrcholů G, které jsou konci některých hran z F i hran z E(G) \ F. F E \ F Petr Hliněný, FI MU Brno 6 FI: MA010: Dekompozice a minory Definice 10.3. Větvená dekompozice grafu G Nechť T je podkubický strom a : E(G) L(T ) je bijekce hran grafu G do listů L(T ) stromu T . Pro každou hranu x stromu T definujeme šířku x jako G(X), kde X = -1 V (T1) pro jednu z komponent T1, T2 lesa T - x. x T X E \ X šířka(x) := G(X) = G(E \ X) 2 Pak šířkou dekompozice T, je maximální šířka ze všech hran T a větvenou šířkou grafu G je nejmenší možná šířka větvené dekompozice G. 2 s s s s s s a b c d e f s s s s s ab bc bdac ad ss s s ef ae af be bf s s s scd de df ce cf Petr Hliněný, FI MU Brno 7 FI: MA010: Dekompozice a minory Věta 10.4. (Robertson and Seymour) Pokud graf G má stromovou šířku t a větvenou šířku b > 1, tak b t + 1 3 2 b .2 ........ Nechť G je graf a F E(G). Jako funkci hodnosti řezu G(F) na množině F označíme hodnost F × (E \ F)-matice A = (ai,j) nad binárním tělesem GF(2), kde au,v = 1 pro u F a v E \ F, právě když uv je hranou v G. 2 Definice 10.5. Ranková dekompozice grafu G Nechť T je podkubický strom a : V (G) L(T ) je bijekce vrcholů grafu G do listů L(T ) stromu T . Pro každou hranu x stromu T definujeme šířku x jako G(X), kde X = -1 V (T1) pro jednu z komponent T1, T2 lesa T - x. Pak šířkou dekompozice T, je maximální šířka ze všech hran T a rankovou šířkou grafu G je nejmenší možná šířka rankové dekompozice G. 2 Fakt: Rankovou šířku grafu lze omezit funkcí jeho větvené šířky, ale naopak toto neplatí ­ třeba úplné grafy mají rankovou šířku 1, kdežto jejich větvená i stromová šířka roste nade všechny meze. Petr Hliněný, FI MU Brno 8 FI: MA010: Dekompozice a minory 10.3 Efektivní algoritmy na dekompozicích Jak jistě víte, určení velikosti největší nezávislé množiny v grafu je NP-úplný problém. Stromová dekompozice fixní šířky však tento problém umožňuje řešit velice snadno. Algoritmus 10.6. Nezávislá množina na stromové dekompozici 2 Problém hledání (maximálního) párování v grafu sice je polynomiálně řešitelný, ale zjišťování počtu všech párování už je #P-úplné, neboli stejně těžké (beznadějné) jako výpočet permanentu matice nebo spočítání všech řešení SAT problému. Algoritmus 10.7. Počet párování na větvené dekompozici 2 Poslední ukázka řeší problém 3-obarvení grafu s jeho rankovou dekompozicí fixní šířky a představuje netradiční nový přístup k takové problematice. . . Algoritmus 10.8. 3-obarvení na rankové dekompozici 2 Pro zvídavé čtenáře na závěr zařazujeme následující těžkou otázku: Dokázali byste efektivně nalézt Hamiltonovskou kružnici v grafu na jeho rankové dekompozici fixní šířky? Petr Hliněný, FI MU Brno 9 FI: MA010: Dekompozice a minory 10.4 Minory v grafech Definice: Říkáme, že graf G je minorem grafu H, pokud lze G získat z H kontrakcemi hran a vypouštěním vrcholů a hran. s s ss s s s ss s s s ss s s s ss s s ss s s s s ss s ss s s s ss s 2 Robertson­Seymourova věta Věta 10.9. Mějme libovolnou grafovou vlastnost , která je uzavřená na minory (tj. pokud G má , pak každý minor G má také ). Pak existuje konečně mnoho grafů F1, . . . , F (zakázané minory) takových, že G má právě když G neobsahuje minor isomorfní žádnému z F1, . . . , F. Mimo jiné lze tudíž vlastnost rozhodnout v čase O(n3 ) pro každý n-vrcholový graf G. 2 Poznámka: Tato věta je zcela nekonstruktivní, neboli nepodává žádný návod, jak zmíněný algoritmus sestrojit!