Multimediaexpo.cz je již 18 let na českém internetu !!
Stromový rozklad
Z Multimediaexpo.cz
m (Nahrazení textu „<math>“ textem „<big>\(“) |
m (Nahrazení textu „</math>“ textem „\)</big>“) |
||
| Řádka 19: | Řádka 19: | ||
== Stromová šířka == | == Stromová šířka == | ||
| - | '''Stromová šířka''' grafu tw(G) se definuje jako <big>\(\min_T \max_{X \in V(T)}|X|-1</ | + | '''Stromová šířka''' grafu tw(G) se definuje jako <big>\(\min_T \max_{X \in V(T)}|X|-1\)</big>, tedy nejmenší možná šířka rozkladu přes všechny rozklady. |
== Třídy grafů omezené stromové šířky == | == Třídy grafů omezené stromové šířky == | ||
Aktuální verze z 14. 8. 2022, 14:53
Stromový rozklad je jeden ze způsobů, jak charakterizovat graf.
Obsah |
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
- 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é.
| Náklady na energie a provoz naší encyklopedie prudce vzrostly. Potřebujeme vaši podporu... Kolik ?? To je na Vás. Náš FIO účet — 2500575897 / 2010 |
|---|
| Informace o článku.
Článek je převzat z Wikipedie, otevřené encyklopedie, do které přispívají dobrovolníci z celého světa. |