Stromový rozklad

Z Multimediaexpo.cz

Graf na osmi vrcholech a jeho stromový rozklad. Každý vrchol musí mít ve stromě souvislý výskyt a každá hrana musí být obsažena v některém uzlu. Šířka tohoto rozkladu je 2, protože největší uzel má velikost 3.

Stromový rozklad je jeden ze způsobů, jak charakterizovat graf.

Definice

Strom T je stromový rozklad grafu G, pokud jeho vrcholy jsou tvořeny podmnožinami V(G) a platí:

1. žádný X z V(T) není prázdný a každý v z V(G) je v nějakém X
2. pro každou hranu {v,w} grafu G existuje X z V(T) takové, že {v,w} je podmnožinou X
3. vrcholy rozkladu T obsahující libovolný vrchol v grafu G indukují souvislý podstrom (v má v T souvislý výskyt)

Vrcholům stromového rozkladu se říká uzly, aby se odlišily od vrcholů původního grafu.

Pro každý graf existuje stromový rozklad, například triviální rozklad, který jedinému uzlu přiřadí všechny vrcholy.

Šířka rozkladu

Šířka rozkladu je velikost největšího uzlu bez jedné.

Stromová šířka

Stromová šířka grafu tw(G) se definuje jako \(\min_T \max_{X \in V(T)}|X|-1\), tedy nejmenší možná šířka rozkladu přes všechny rozklady.

Třídy grafů omezené stromové šířky

1. grafy stromové šířky 0 jsou pouze grafy bez hran, hrana vynutí uzel velikosti alespoň 2
2. grafy stromové šířky nejvýše 1 jsou lesy, každý les má rozklad takový, že uzly odpovídají hranám
3. grafy stromové šířky nejvýše 2 jsou sériově paralelní grafy

Třídy grafů omezené stromové šířky jsou uzavřené na minory, žádné minorové operace nezvyšují stromovou šířku. Odebrání vrcholu se v rozkladu projeví odebráním vrcholu ze všech uzlů, odebrání hrany se neprojeví vůbec, kontrakce nahrazením jednoho vrcholu jeho sousedem přes kontrahovanou hranu a odstraněním duplicit.

Chordální grafy

Související informace naleznete také v článku: Chordální graf.

Chordální graf je takový, který neobsahuje cyklus délky alespoň 4 jako indukovaný podgraf (každý takový cyklus má chordu — hranu spojující vrcholy, které nejsou na cyklu za sebou). Tyto grafy jsou specifické tím, že pro ně existuje stromový rozklad takový, že každý uzel indukuje kliku, ten je navíc snadné zkonstruovat. Platí, že pro každý graf je stromová šířka rovna nejmenší klikovosti přes všechny chordální nadgrafy bez jedné.