http://www.multimediaexpo.cz/mmecz/index.php?action=history&feed=atom&title=Chord%C3%A1ln%C3%AD_graf 2026-05-25T15:29:00Z Historie editací této stránky MediaWiki 1.16.5 http://www.multimediaexpo.cz/mmecz/index.php?title=Chord%C3%A1ln%C3%AD_graf&diff=943792&oldid=prev 2015-10-08T09:31:40Z

<p>+ Nový článek</p> <p><b>Nová stránka</b></p><div>[[Soubor:Tree decomposition.png|thumb|230px|Chordální graf a jeho optimální stromová dekompozice (s&amp;nbsp;nejmenší&amp;nbsp;možnou šířkou)]]<br /> '''Chordální graf''' je takový [[graf (teorie grafů)|graf]], který neobsahuje [[Kružnice (graf)|kružnici]] velikosti alespoň 4 jako [[Podgraf#Indukovaný podgraf|indukovaný podgraf]].<br /> <br /> == Příklady ==<br /> * Lesy (neobsahují žádný cyklus, tím spíše ne velký indukovaný)<br /> * Úplné grafy (každý indukovaný podgraf je [[klika (teorie grafů)|klika]], tedy ne kružnice větší než 3)<br /> * [[k-strom|''k''-stromy]]<br /> <br /> == Vlastnosti ==<br /> * Indukovaný podgraf chordálního grafu je opět chordální.<br /> * Chordální graf obsahuje vrchol, jehož sousedství indukuje kliku.<br /> * Spojením předchozích vlastností získáme, že se každý chordální dá získat z prázdného grafu tak, že postupně připojujeme vrcholy k nějaké klice. Této možnosti výstavby/rozebrání se říká ''vrcholové perfektní eliminační schéma''.<br /> * Toto schéma se dá použít pro vytvoření [[Stromový rozklad|stromového rozkladu]] minimální šířky, kde každý uzel indukuje kliku. Naopak z každé stromové dekompozice je možné zrekonstruovat chordální graf, který je nadgrafem původního, tak, že se z každého uzlu udělá klika.<br /> * Každý graf má stromovou šířku odpovídající nejmenší možné klikovosti chordálního nadgrafu.<br /> * Chordální graf je [[průnikový graf]] podstromů ve stromě. To je vidět právě převodem na stromovou dekompozici a zpět.<br /> <br /> <br /> {{Článek z Wikipedie}}<br /> [[Kategorie:Typy grafů]]</div>

Sysop