10   Dekompozice grafů, algoritmy a minory
Další autorův výběr tématu nas zavede ke strukturální teorii grafu - k různým jejich dekompozicím, grafovým minorům a navazujícím efektivním algoritmům pro jinak teZke problemý.
Obecnou inspirací nam je znamý fakt, ze vetšinu jinak tezkých problemu lze rešit snadno a efektivne na stromech. Podobna situace nastava treba u intervalových grafu nebo obecne u chordalních grafu. Proto se podívame na grafý, ktere jsou svým zpusobem „stromum blízke", ve smýslu existence jejich vhodne dekompozice.
Vrcholem teto lekce je formulace hlavního výsledku takzvane „Graph Minors Theorý" od Robertsona a Seýmoura, který lze bez nadsazký prohlasit za asi nejvetsí výsledek, ktereho dosud teorie grafu dosahla (i v porovnaní s Vetou o ctýrech barvach). c
StrůCny přehled lekce
• Úvodní zamyšlení nad řešením obtížných problémů.
• Stromová šířka grafů z mnoha stran. Nékteré jiné „šířkové" param.
• Úkazky použití dekompozic grafů na efektivní algoritmy.
• Néco o grafových minorech a strůktůrainí teorii.
Petr Hliněný,  FI MU Brno 1 FI: 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 NP-téžké grafové problémy, například 3-obarvení grafu nebo nežavisla množina vrcholU. c
Oba tyto problémy snadno vyrešíme na intervalových grafech.
Algoritmus 10.1. Naležení nezávislé množiny v intervalovém grafu
Předpokládejme, že graf G je dany svou intervalovou reprezentací (v případě potřeby je možno tuto reprezentaci efektivne sestrojit). Maximální nezavislou množinu nalezneme nasledovne.
• Usporadame intervaly reprezentující G podle jejich pravych koncU. c
• Do nežavislé množiny hladové (v tomto usporadan í) vlož íme vždy prvn í interval neprot ínaj íc í se s predchož ími vybranymi.
V
Petr Hliněný,  FI MU Brno
FI: MA010: Dekompozice a minorý
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 žkonstruhujeme simplicialní dekompozici našeho grafu G (Věta 9.4). c
• Graf G je k-degenerovany, kde k = uj(G) — 1 je nejvetší stupen si m plicialního vrcholů v nekterem kroku simplicialní dekompozice G. Hladove tudíž můžeme G obarvit k +1 barvami a to je optimalní (nebot mame v G kliku velikosti k + 1).
c
Algoritmus 10.3. Nalezení nezávisle množiny chordálního grafu
• Opet žkonstruhujeme simplicialní dekompozici naseho grafu G (Veta 9.4).
• V poradí teto dekompozice hladove přidavame vrcholy do nežavisle množiny. (Tento postup je přímým žobecnením Algoritmu 10.1, viž take Veta 9.5.) c
Možna zobecnení?
Zajímavou a užitecnou otažkou ted' je, jak takove postupy žobecnit na sirsítrídy grafu, ktere mají nejakou specifickou omežující (ale ne přílis) vlastnost - „parametr".
_Petr Hliněný,  FI MU Brno_3_FI: MA010: Dekompozice a minory_
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, Ze ekvivalentní definice jiZ uvaZovali matematici leta pred nimi, například v souvislosti s takzvanými „k-trees" nebo se simplicialními dekompozicemi. (DUsledkem tohoto vývoje je take bohatost mzných definic stejneho pojmu. ..) c
Připomeňme, ze velikost nejvetsí kliky v grafu G se oznacuje uj(G).
Definice: Stromovou šířkou (tree-width) grafu G nazveme nejmensí pňirozene k takove, ze existuje chordalní graf H s uj(H) = k + 1 obsahující G jako podgraf (H D G).
Například každý podgraf následuj íc ífio chrodaln ího grafu ma tree-width < 2:
Kde je vSak v teto definici nejaký „strom"? Je, ale skrýtý - pod ívejte se na Vetu 9.5 popisuj íc í chordaln í grafý jako prunikove grafý podstromu ve strome.
_Petr Hliněný,  FI MU Brno_4_FI: MA010: Dekompozice a minory_
Jinou možnost popisu ukazuje:
Definice: Vrcholy V (G) grafu G uspořádáme do posloupnosti (permutace) (vi, v2,..., vn). Pro i = 1, 2,..., n definujme l(vi) jako pocet vsech indexu j G {1,... ,i — 1} takových, že vrcholy Vj a Vj jsou v G spojeny cestou používající pouze vrcholy z množiny {vj, Vj, vj+1,..., vn}. c
Druhou stromovou šířkou grafu G nazveme nejmensí hodnotu vyrazu maxv l(v) přes vsechny permutace vrcholu V(G).
Všimněte si, ze uspořádán í vrcholů z teto definice je vlastně zpětnou simpliciáln í dekompozic í chordáln ího grafu H D G z předchoz í definice (viz take Veta 9.4).
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ý,  FI MU Brno
FI: MA010: Dekompozice a minorý
Ještě další, značně odlišný, přístup má tato definice:
Definice: Pro libovolný strom T uvaZujeme (libovolně) zobrazení t : E (G) — V (T). Pro vrchol t G V (T) označíme Ti,... ,Td jednotlive komponenty lesa T — t a F =
t-1 (V(T,)). OznaCme
ÍT(t) = |V(G)| + (d — 1) • c(G) c(G — F,),
kde c(H) znaCí počet souvislých komponent grafu H.
t : E —
Třetí stromovou šířkou grafu G pak definujeme jako nejmensí moznou, přes vsechný dvojice T,t, hodnotu výrazu maxteV(T) lT(t).
Petr Hliněný,  FI MU Brno
FI: MA010: Dekompozice a minorý
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í mozne definice málokdy přijde reC).
Definice 10.4. Stromová dekompozice grafu G.
Stromovou dekompozici grafu G nazveme strom T spolu se systemem množin Xt (zvaných „balíky") pro t G V (T), kde
• X t C V (G) a Uŕey (t ) X t = V (G), □
• pro každou hranu e = uv G E (G) je u, v G X t pro nejake t G V (T), c
• (interpolační vlastnost) pro každý vrchol v G V (G) tvoří podmnožina vsech t G V (T) s v G X t podstrom v T. □
Šířkou dekompozice T, X rozumíme nejvetsí hodnotu |X t| — 1 pro t G V (T) a čtvrtou stromovou šířkou grafu G nazveme nejmensí moznou síŠku stromove dekompozice G.
1
2
{1, 5, 6, 8}   {1, 2, 3, 6}
{1, 3, 6, 8}
{1, 3,4, 8}   {3, 6, 7, 8}
4
3
V
Petr Hliněný,  FI MU Brno
FI: MA010: Dekompozice a minorý
Přes veškerou zdanlivou odlišnost uvedených definic platí následovné.
Věta 10.5. Všechny čtyři vyše uvedené definice stromové šířky definují přesně tutéž hodnotu, pokud graf G ma neprázdnou množinu hran.
DUkaz plneho znení teto vetý je však nad rámec našeho textu. O čětnících a zloději
Na zaver si představme hru na četníky a žlodeje s temito pravidly: Zlodej se bleskovou rýchlostí pohybuje po hranach grafu pres vrcholy neobsazene Cetníký (jeho pohýb vZdý skonCí ve vrcholu, ne „uprostřed" hraný). Naopak četníci se grafem vubec nepohýbují, jen přiletají do a odletají z vrcholu helikopterou. Zlodej je chýcen ve svem vrcholu z přiletivsím cetníkem, pokud jsou i vsichni sousede z zrovna obsazeni cetníký.
Věta 10.6. Nejmenší počet četníku potřebnych k žaručenemu chycení žlodeje v grafu G je roven stromove šířce G plus 1.
Petr Hliněný,  FI MU Brno
FI: MA010: Dekompozice a minorý
10.3   Některé další parametry
Definice: Cestní dekompozici a šířku (path-width) grafu G definujeme stejně jako v Definici 10.4, jen poZadujeme navíc, aby T byla cesta. c
Definice: Vrcholy V (G) grafu G uspořadáme do posloupnosti (permutace) (vi, v2,..., vn). Bandwidth grafu G definujeme jako nejmensí hodnotu vyrazu maxVíVj e£(G) |i — j I pres vsechny permutace vrcholu V (G). c
Vetvene dekompozice
Graf je kubický, pokud ma vsechny vrcholy stupne 3. Strom je podkubicky, pokud ma vsechny vrcholy stupne < 3.
Definice: Pro libovolný graf G a podmnoZinu X C E (G) definujeme funkci souvislosti
\g(X) jako počet vrcholu G, ktere jsou konci nekterych hran z X i hran z E(G) \ X
(separace mnoziny X).
V
Petr Hliněný,  FI MU Brno
FI: MA010: Dekompozice a minorý
Definice 10.7. Vetvená dekompozice grafu G
Necht T je podkubický strom a t : E(G) — L(T) je bijekce hran grafu G do listu L(T) stromu T. Pro kazdou hranu x stromu T definujeme sířku x jako AG(X), kde X = t-1(V(T1)) pro jednu z komponent T1,T2 lesa T
T
E \ X
sířka(x) := AG(X) = AG(E \ X)
Pak šířkou dekompozice T, t je maximální šířka ze všech hran T a větvenou šířkou grafu G je nejmenší moZná šířka vetvene dekompozice G. c
Petr Hliněný,  FI MU Brno_10_FI: MA010: Dekompozice a minory
_
Jiný přístup
Necht G je graf a X C V(G). Jako funkci hodnosti řežu yg (F) na mnozine F oznacíme hodnost X x (V \ X )-matice A = (aiij) nad binárním tělesem GF (2), kde auv = 1 pro u G X a v G V \ X, prave kdýz uv je hranou v G. □
Děfinicě 10.9. Rankova dekompozice grafu G
Necht T je podkubický strom a t : V(G) —> L(T) je bijekce vrcholu grafu G do listu L(T) stromu T. Pro kazdou hranu x stromu T definujeme sířku x jako yg(X), kde X = t-1( V (Ti)) pro jednu z komponent Ti,T2 lesa T - x. □
Pak sírkou dekompozice T, t je maximílní sírka ze vsech hran T a rankovou siřkou grafu G je nejmensí mozní sírka rankove dekompozice G.
d
(0 0 11)
(10 0 1 e
1 0
0 0   1 0 1
1 0   0 0 0
6
Petr Hliněný,  FI MU Brno_12_FI: MA010: Dekompozice a minorý
10.4   Efektivní algoritmy na dekompozicích
Jiz víme z 7.17, ze urcení velikosti nejvetsí nezavisle mnoziny v grafu je NP-uplný problem. Stromova dekompozice fixní síňky vsak tento problem umoznuje ňesit velice snadno.
Algoritmus 10.10. Nezávisia mnoZina na stromove dekompozici
Danou stromovou dekompozici vstupního grafu si libovolne „zakořeníme".
• V kazdem liste dekompozice vyňesíme problem hrubou silou v konstantním case.c
• Ve smeru od listu ke koreni sbírame nasledující informaci:
V kazdem balíku B dekompozice, pro kazdou X C B, velikost nejvetsí nezavisle mnoziny I v grafu indukovanem na podstromu pod B takove, ze I n B = X. c
• Vzhledem k interpolacn í vlastnosti nasí dekompozice lze výse popsanou informaci v kazdem bal íku dekompozice zjistit v konstantn ím case pouze ze znalosti stejne informace ze vsech jeho potomku v dekompozici.
Výsledný algoritmus pracuje v case umernem poctu uzlu dekompozice, tedy v linearn ím case!
V
Petr Hliněný,  FI MU Brr
FI: MA010: Dekompozice a minory
Další problém hledání párování v grafu sice je polynomiálně řešitelný, ale zjišťování poctu všech párování uZ je #V-úplné, neboli stejne teZke (beznádejne) jako výpočet permanentu matice nebo spočítaní všech řešení SAT problemu.
Algoritmus 10.11. PoCet párovaní na vetvene dekompozici
Opet ši vetvenou dekompozici vštupního grafu libovolne „zakoreníme".
• V kazdem lište dekompozice je rešení trivialní. c
• Ve šmeru od lištu ke koreni šb írame našleduj íc í informaci:
V kazde hrane dekompozice, pro kazdou podmnozinu X C S vrcholu šeparace S indukovane touto hranou v dekompozici, pocet všech parovan í, ktera ze šeparace S „obšazuj í" prave vrcholy X. c
• Opet lze výše popšanou informaci na kazde hrane dekompozice zjištit v kon-štantn ím caše pouze ze znalošti štejne informace z obou jejich podštromm v dekompozici (vzajemným vynašoben ím a šecten ím poctu).
Výšledný algoritmuš pracuje v caše umernem poctu hran dekompozice, tedy opet v linearním caše.
Petr Hliněný,  FI MU Brno_14_FI: MA010: Dekompozice a minory
r
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 postupne [Courcelle / Arnborg, Lagergren, Seese / Borie, Parker, Toveý].
Veta 10.12. Každá vlastnost grafů, která je vyjádřitelná v tzv. (E)MSO jazyce, se dá vypočítat v lineárnám Case pro všechny grafy omezené stromové sišky.
Pro žjednodusení nebudeme přesne definovat, co (E)MSO jažyk žnamena, ale žhruba jde o jažyk, ktery ma dovoleno kvantifikovat pres podmnožiny vrcholu a hran grafu a enumerovat pocty prvku množin. Vetsina grafovych vlastností, ktere jsme žatím probírali, spada do teto kategorie.
Petr Hliněný,  FI MU Brr
FI: MA010: Dekompozice a minory
10.5   Minory v gráfech
Definice: Ríkame, ze graf G je minorem grafu H, pokud lze G získat z H kontrakcemi hran a vypoustením vrcholu a hran.
•-
Robertson-Seymourová vetá
Vetá 10.13. Mejme libovolnou grafovou vlastnost </>, která je uzavřená na minory (tj. pokud G ma </>, pak kaZdy minor G ma také </>).
Pak existuje konečne mnoho grafu Fi,..., Fi (zakézané minory) takových, Ze G ma 4> prave kdyZ G neobsahuje minor isomorfní Zadnému z Fi,..., Fi.
Mimo jiné lze tudíž vlastnost </> rozhodnout v čase O(n3) pro kaZdyý n-vrcholový graf G.
Poznámká: Tato veta je zcela nekonstruktivní, neboli nepodává žádný návod, jak zmíněný algoritmus sestrojit!
Petr Hliněný,  FI MU Brn
FI: MA010: Dekompozice a minorý
□