10 Dekompozice grafů, algoritmy a minory Další autorův výběr tématu nás zavede 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. Obecnou inspirací nám je známý fakt, že většinu jinak těžkých problémů lze řešit snadno a efektivně na stromech. Podobná situace nastává třeba u intervalových grafů nebo obecně u chordálních grafů. Proto se podíváme na grafy, které jsou svým způsobem „stromům blízké", ve smyslu existence jejich vhodné dekompozice. 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). □ Stručný přehled lekce • Úvodní zamyšlení nad řešením obtížných problémů. • Stromová šířka grafu z mnoha stran. Některé jiné „šířkové" parám. • Ukázky použití dekompozic grafů na efektivní algoritmy. • Něco o grafových minorech a strukturální teorii. Petr Hliněný, Fl MU Brno, 2013 1/16 Fl: MA010: Dekompozice a minory 10.1 Obtížné problémy na speciálních grafech V Lekci 7 jsme uvedli některé „neřešitelně obtížné", přesněji TVP-těžké grafové problémy, například 3-obarvení grafu nebo nezávislá množina vrcholů. □ Oba tyto problémy snadno vyřešíme na intervalových grafech. Algoritmus 10.1. Nalezení nezávislé množiny v intervalovém grafu Předpokládejme, že graf G je daný svou intervalovou reprezentací (v případě potřeby je možno tuto reprezentaci efektivně sestrojit). Maximální nezávislou množinu nalezneme následovně. • Uspořádáme intervaly reprezentující G podle jejich pravých konců. • Do nezávislé množiny hladově (v tomto uspořádání) vložíme vždy první interval neprotínající se s předchozími vybranými. Petr Hliněný, Fl MU Brno, 2013 2/16 Fl: MA010: Dekompozice a mi nory Také na obecnějších chordálních grafech můžeme navrhovat rychlé a povětšinou i snadné algoritmy. Algoritmus 10.2. Určení barevnosti chordálního grafu • Snadno zkonstruhujeme simpliciální dekompozici našeho grafu G (Věta 9.6). • Graf G je fc-degenerovaný, kde k — w(G) — 1 je největší stupeň simpliciálního vrcholu v některém kroku simpliciální dekompozice G. Hladově tudíž můžeme G obarvit k+í barvami a to je optimální (neboť máme v G kliku velikosti k + 1). □ Algoritmus 10.3. Nalezení nezávislé množiny chordálního grafu • Opět zkonstruhujeme simpliciální dekompozici našeho grafu G (Věta 9.6). • V pořadí této dekompozice hladově přidáváme vrcholy do nezávislé množiny. (Tento postup je přímým zobecněním Algoritmu 10.1, viz také Věta 9.8.) Možná zobecnění? Zajímavou a užitečnou otázkou teď je, jak takové postupy zobecnit na širší třídy grafů, které mají nějakou specifickou omezující (ale ne příliš) vlastnost - „parametr". Petr Hliněný, Fl MU Brno, 2013 3/16 Fl: MA010: Dekompozice a mi nory 10.2 Tree-width - čtyři definice Název „tree-width" byl zaveden Robersonem a Seymourem počátkem 80-tých let, ale pak se ukázalo, že ekvivalentní definice již uvažovali matematici léta před nimi, například v souvislosti s takzvanými ,,/j-trees" nebo se simpliciálními dekompozicemi. (Důsledkem tohoto vývoje je také bohatost různých definic stejného pojmu.. .) □ Připomeňme, že velikost největší kliky v grafu G se označuje lj(G). Definice: Stromovou sirkou (tree-width) grafu G nazveme nejmenší přirozené k takové, že existuje chordální graf H s lú(H) — k + 1 obsahující G jako podgraf (H D G). Například každý podgraf následujícího chrodálního grafu má tree-width < 2: Kde je však v této definici nějaký „strom"? Je, ale skrytý - podívejte se na Větu 9.8 popisující chordální grafy jako průnikové grafy podstromů ve stromě. Petr Hliněný, Fl MU Brno, 2013 4/ 16 Fl: MA010: Dekompozice a mi nory Jinou možnost popisu ukazuje: Definice: Vrcholy V(G) grafu G uspořádáme do posloupnosti (permutace) (t>i, t>2,..., vn). Pro í — 1,2,..., n definujme £(ví) jako počet všech indexů j € {í,..., í — 1} takových, že vrcholy Vi a Vj jsou v G spojeny cestou používající pouze vrcholy z množiny {vj, Vi, f^+i,..., vn}. Druhou stromovou šírkou grafu G nazveme nejmenší hodnotu výrazu maxv £(v) přes všechny permutace vrcholu V(G). Všimněte si, že uspořádání vrcholu z této definice je vlastně zpětnou simpliciální dekompozicí chordálního grafu H D G z předchozí definice (viz také Věta 9.6). V nakresleném příkladě grafu C5 vidíme uspořádání vrcholů se šířkou 2. (Tečkované hrany ukazují tzv. chordální doplnění grafu, relevantní k první definici tree-width.) Petr Hliněný, Fl MU Brno, 2013 5/16 Fl: MA010: Dekompozice a mi nory Ještě další, značně odlišný, přístup má tato definice: Definice: Pro libovolný strom T uvažujeme (libovolné) zobrazení t : E (G) —>• V (T). Pro vrchol t G V (T) označíme Ti,..., T d jednotlivé komponenty lesa T — t a Fi — T-^iyiTi)). Označme d £T(t) = \V(G)\ + (d- 1) • c(G) - ^ c(G - Fi): i=l kde c(H) značí počet souvislých komponent grafu H. t : E ^ Třetí stromovou šířkou grafu G pak definujeme jako nejmenší možnou, přes všechny dvojice T, t, hodnotu výrazu max teV^ £T(t). Petr Hliněný, FI MU Brno, 2013 6/16 FI: MA010: Dekompozice a mi nory Nakonec si uvedeme ještě původní definici Robertsona a Seymoura, 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.4. Stromová dekompozice grafu G. Stromovou dekompozicí grafu G nazveme strom T spolu se systémem množin Xt (zvaných „balíky") pro t G V (T), kde • Xt C V{G) a Utev(T) xt = ^(G), • pro každou hranu e — uv E E (G) je u,v e Xt pro nějaké í e V (T), • (interpolační vlastnost) pro každý vrchol v e V (G) tvoří podmnožina všech í G V(T) s í; e Xt podstrom v T. □ Sirkou dekompozice T, 2,..., vn). Bandwidth grafu G definujeme jako nejmenší hodnotu výrazu max^^g^Q) \í — j\ přes všechny permutace vrcholů V(G). □ Větvené dekompozice Graf je kubický, pokud má všechny vrcholy stupně 3. Strom je podkubický, pokud má všechny vrcholy stupně < 3. Definice: Pro libovolný graf G a podmnožinu X C E(G) definujeme funkci souvislosti \c(X) jako počet vrcholů G, které jsou konci některých hran z X i hran z E(G) \X (separace množiny X). Petr Hliněný, Fl MU Brno, 2013 9/16 Fl: MA010: Dekompozice a minory Definice 10.7. Větvená dekompozice grafu G Nechť T je podkubický strom a t : E (G) —>• L (T) je bijekce hran grafu G do listů L (T) stromu T. Pro každou hranu x stromu T definujeme šírku x jako Xq(X), kde X = t-~í(V{T1)) pro jednu z komponent Ti,T2 lesa T — x. šířka(x) := AG(X) = AG(S \ X) □ Pak šířkou dekompozice T, 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. □ Jiný přístup Nechť G je gráfa X C V(G). Jako funkci hodnosti řezu 'ja(F) na množině F označíme hodnost X x (V \ X)-matice A — (a,ij) nad binárním tělesem GF(2), kde aUtV — 1 pro ueXaveV\X, právě když uv je hranou v G. Definice 10.9. Ranková dekompozice grafu G Nechť T je podkubický strom a t : V(G) —>• L(T) je bijekce vrcholů grafu G do listů L(T) stromu T. Pro každou hranu x stromu T definujeme šírku x jako 7g(X), kde X = r"1 (V(Ti)) pro jednu z komponent Ti, T2 lesa T — x. □ Pak šířkou dekompozice T, t je maximální šířka ze všech hran T a rankovou šířkou grafu G je nejmenší možná šířka rankové dekompozice G. A °\ / 0 A 0 1 / ll 0 oj „ \o o/ y v —t—o— -L-Q 10.4 Efektivní algoritmy na dekompozicích Již víme z 7.18, že určení velikosti největší nezávislé množiny v grafu je TVP-úplný problém. Stromová dekompozice fixní šírky však tento problém umožňuje řešit velice snadno. Algoritmus 10.10. Nezávislá množina na stromové dekompozici Danou stromovou dekompozici vstupního grafu si libovolně „zakořeníme". • V každém listě dekompozice vyřešíme problém hrubou silou v konstantním čase.n • Ve směru od listů ke kořeni sbíráme následující informaci: V každém balíku B dekompozice, pro každou X C B, velikost největší nezávislé množiny I v grafu indukovaném na podstromu pod B takové, že I n B — X. □ • Vzhledem k interpolační vlastnosti naší dekompozice lze výše popsanou informaci v každém balíku dekompozice zjistit v konstantním čase pouze ze znalosti stejné informace ze všech jeho potomků v dekompozici. Výsledný algoritmus pracuje v čase úměrném počtu uzlů dekompozice, tedy v lineárním čase! Další problém hledání párování v grafu sice je polynomiálně řešitelný, ale zjišťování počtu všech párování už je ^V-úplné, neboli stejně těžké (beznadějné) jako výpočet permanentu matice nebo spočítání všech řešení S AT problému. Algoritmus 10.11. Počet párování na větvené dekompozici Opět si větvenou dekompozici vstupního grafu libovolně „zakořeníme". • V každém listě dekompozice je řešení triviální. □ • Ve směru od listů ke kořeni sbíráme následující informaci: V každé hraně dekompozice, pro každou podmnožinu X C S vrcholů separace S indukované touto hranou v dekompozici, počet všech párování, která ze separace S „obsazují" právě vrcholy X. □ • Opět lze výše popsanou informaci na každé hraně dekompozice zjistit v konstantním čase pouze ze znalosti stejné informace z obou jejich podstromů v dekompozici (vzájemným vynásobením a sečtením počtů). Výsledný algoritmus pracuje v čase úměrném počtu hran dekompozice, tedy opět v lineárním čase. Jeden všeobecný výsledek Nápadná vzájemná podobnost předchozích algoritmů určitě není náhodná, chtěli jsme jimi ilustrovat jeden důležitý obecný princip, který objevili postupně [Courcelle / Arnborg, Lagergren, Seese / Borie, Parker, Tovey]. Věta 10.12. Každá vlastnost grafů, která je vyjádřitelná v tzv. (E)MSO jazyce, se dá vypočítat v lineárním čase pro všechny grafy omezené stromové šířky. Pro zjednodušení nebudeme přesně definovat, co (E)MSO jazyk znamená, ale zhruba jde o jazyk, který má dovoleno kvantifikovat přes podmnožiny vrcholů a hran grafu a enumerovat počty prvků množin. Většina grafových vlastností, které jsme zatím probírali, spadá do této kategorie. 10.5 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. Robertson—Seymourova věta Věta 10.13. 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ů F\,... ,Ft (zakázané minory) takových, že G má právě když G neobsahuje minor isomorfní žádnému z Fi,..., Fg. Mimo jiné lze tudíž vlastnost rozhodnout v čase 0(n3) pro každý n-vrcholový graf G. Poznámka: Tato věta je zcela nekonstruktivní, neboli nepodává žádný návod, jak zmíněný algoritmus sestrojit!