Black-Friday-2019-12-Multimediaexpo.png

K-strom

Z Multimediaexpo.cz

Přejít na: navigace, hledání

k-strom je druh grafu.

Definice

k-strom se definuje rekurzivně takto:

  1. Kk+1 je k-strom
  2. Graf, který vznikne ze dvou k-stromů identifikací dvou podgrafů isomorfních Kk, je k-strom

Druhý bod je ekvivalentní s „Graf, který vznikne připojením vrcholu ke k-stromu tak, že jeho sousedství indukuje Kk, je k-strom“ – aneb jeden ze sjednocovaných grafů je právě Kk+1.

Vlastnosti

Strom je 1-strom.

k-stromy jsou chordální.

Grafy stromové šířky nejvýše k jsou právě podgrafy k-stromů. To, že k-stromy mají stromovou šířku k lze vidět z jejich definice – při připojení vrcholu ke klice se v dekompozici vytvoří uzel, který obsahuje nový vrchol i jeho sousedství, a připojí se k uzlu obsahujícímu sousedstvi (které tvoří kliku a proto musí být celé v nějakém uzlu).

k-stromy mají nejvýše k|V| hran. To plyne snadno z konstrukce pomocí přidávání vrcholů s k sousedy.


Osobní nástroje
Jmenné prostory
Varianty
Akce
Hlavní funkce
Navigace
Nástroje
Příspěvky a dary
Další informace