V sobotu 2. listopadu proběhla mohutná oslava naší plnoletosti !!
Multimediaexpo.cz je již 18 let na českém internetu !!
V tiskové zprávě k 18. narozeninám brzy najdete nové a zásadní informace.
Multimediaexpo.cz je již 18 let na českém internetu !!
V tiskové zprávě k 18. narozeninám brzy najdete nové a zásadní informace.
Chordální graf
Z Multimediaexpo.cz
Chordální graf je takový graf, který neobsahuje kružnici velikosti alespoň 4 jako indukovaný podgraf.
Příklady
- Lesy (neobsahují žádný cyklus, tím spíše ne velký indukovaný)
- Úplné grafy (každý indukovaný podgraf je klika, tedy ne kružnice větší než 3)
- k-stromy
Vlastnosti
- Indukovaný podgraf chordálního grafu je opět chordální.
- Chordální graf obsahuje vrchol, jehož sousedství indukuje kliku.
- 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.
- Toto schéma se dá použít pro vytvoření 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.
- Každý graf má stromovou šířku odpovídající nejmenší možné klikovosti chordálního nadgrafu.
- Chordální graf je průnikový graf podstromů ve stromě. To je vidět právě převodem na stromovou dekompozici a zpět.
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. |