Cesko.wiki Stromový rozklad
Author
Albert FloresGraf 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í: # žádný X z V(T) není prázdný a každý v z V(G) je v nějakém X # pro každou hranu {v,w} grafu G existuje X z V(T) takové, že {v,w} je podmnožinou X # 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
# grafy stromové šířky 0 jsou pouze grafy bez hran, hrana vynutí uzel velikosti alespoň 2 # grafy stromové šířky nejvýše 1 jsou lesy, každý les má rozklad takový, že uzly odpovídají hranám # 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
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. +more Platí, že pro každý graf je stromová šířka rovna nejmenší klikovosti přes všechny chordální nadgrafy bez jedné.