Multimediaexpo.cz je již 18 let na českém internetu !!
K-strom
Z Multimediaexpo.cz
k-strom je druh grafu.
Definice
k-strom se definuje rekurzivně takto:
- Kk+1 je k-strom
- 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.
| 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. |