V sobotu 2. listopadu proběhla mohutná oslava naší plnoletosti !!
Multimediaexpo.cz je již 18 let na českém internetu !!

Stromový rozklad

Z Multimediaexpo.cz

(Rozdíly mezi verzemi)
m (1 revizi)
m (Nahrazení textu „</math>“ textem „\)</big>“)
 
(Nejsou zobrazeny 2 mezilehlé verze.)
Řádka 1: Řádka 1:
-
{{Wikipedia-cs|Stromový rozklad|700}}
+
[[Soubor:Tree decomposition.png|thumb|230px|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 (teorie grafů)|graf]].
 +
 +
== Definice ==
 +
 +
[[Strom (teorie grafů)|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 [[Podgraf#Indukovaný podgraf|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 <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 ==
 +
# 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í graf]]y
 +
 +
Třídy grafů omezené stromové šířky jsou uzavřené na [[Minor (teorie grafů)|minory]], žádné [[Minor (teorie grafů)#Minorové operace|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 [[Podgraf#Indukovaný podgraf|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 [[Klika (teorie grafů)|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é.
 +
 +
 +
{{Článek z Wikipedie}}
[[Kategorie:Grafové pojmy]]
[[Kategorie:Grafové pojmy]]

Aktuální verze z 14. 8. 2022, 14:53

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.

Obsah

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é.


Citováno z „http://ww2000w.multimediaexpo.cz/mmecz/index.php/Stromov%C3%BD_rozklad“