K-strom Z Multimediaexpo.cz stránky K-strom Nemáte oprávnění „upravit tuto stránku“. Důvod: Požadovanou činnost smějí provádět jen uživatelé ve skupinách Automaticky schválení uživatelé, RCRedaktors. Můžete si prohlédnout a zkopírovat zdrojový kód této stránky: '''''k''-strom''' je druh [[graf (teorie grafů)|grafu]]. == Definice == ''k''-strom se definuje rekurzivně takto: # K<sub>k+1</sub> je ''k''-strom # Graf, který vznikne ze dvou k-stromů identifikací dvou podgrafů isomorfních K<sub>k</sub>, je ''k''-strom 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>. == Vlastnosti == [[Strom (graf)|Strom]] je ''1''-strom. ''k''-stromy jsou [[chordální graf|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. {{Článek z Wikipedie}} [[Kategorie:Typy grafů]] Šablona použitá na této stránce: Šablona:Článek z Wikipedie (ukázat zdroj) Návrat na stránku „K-strom“.
