http://www.multimediaexpo.cz/mmecz/index.php?action=history&feed=atom&title=K-stromK-strom - Historie editací2026-05-25T16:10:01ZHistorie editací této stránkyMediaWiki 1.16.5http://www.multimediaexpo.cz/mmecz/index.php?title=K-strom&diff=943793&oldid=prevSysop: + Nový článek2015-10-08T09:35:03Z<p>+ Nový článek</p>
<p><b>Nová stránka</b></p><div>'''''k''-strom''' je druh [[graf (teorie grafů)|grafu]].<br />
<br />
== Definice ==<br />
''k''-strom se definuje rekurzivně takto:<br />
# K<sub>k+1</sub> je ''k''-strom<br />
# Graf, který vznikne ze dvou k-stromů identifikací dvou podgrafů isomorfních K<sub>k</sub>, je ''k''-strom<br />
<br />
Druhý bod je ekvivalentní s „Graf, který vznikne připojením vrcholu ke ''k''-stromu tak, že jeho sousedství indukuje K<sub>k</sub>, je ''k''-strom“ – aneb jeden ze sjednocovaných grafů je právě K<sub>k+1</sub>.<br />
<br />
== Vlastnosti ==<br />
[[Strom (graf)|Strom]] je ''1''-strom.<br />
<br />
''k''-stromy jsou [[chordální graf|chordální]].<br />
<br />
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).<br />
<br />
''k''-stromy mají nejvýše ''k|V|'' hran. To plyne snadno z konstrukce pomocí přidávání vrcholů s ''k'' sousedy.<br />
<br />
<br />
{{Článek z Wikipedie}}<br />
[[Kategorie:Typy grafů]]</div>Sysop