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.
Obecnou inspirací nám je poměrně zřejmý fakt, že většinu jinak těžkých problémů lze
řešit snadno a efektivně na stromech. 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). 2
Stručný přehled lekce
* Stromová šířka grafu z mnoha 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
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 ,,k-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 (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
Jinou možnost popisu ukazuje:
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
Ještě další, značně odlišný, přístup má tato definice:
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ě 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.1. Stromová dekompozice grafu G.
Stromovou dekompozicí grafu G nazveme strom T spolu se systémem množin Xt
(zvaných balíky) 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.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
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 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
(separace množiny 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
Petr Hliněný, FI MU Brno 8 FI: MA010: Dekompozice a minory
Jiný přístup
Nechť G je graf a X  V (G). Jako funkci hodnosti řezu G(F) na množině F označíme
hodnost X × (V \ X)-matice A = (ai,j) nad binárním tělesem GF(2), kde au,v = 1
pro u  X a v  V \ X, 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 9 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
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.
2
* 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  B, velikost největší nezávislé
množiny I v grafu indukovaném na podstromu pod B takové, že I  B = X. 2
* 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! 2
Petr Hliněný, FI MU Brno 10 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í
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
Opět si větvenou dekompozici vstupního grafu libovolně ,,zakořeníme .
* V každém listě dekompozice je řešení triviální. 2
* 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  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. 2
* 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. 2
Petr Hliněný, FI MU Brno 11 FI: MA010: Dekompozice a minory
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.8. 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.
Petr Hliněný, FI MU Brno 12 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!