Chordální graf

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
Chordální graf a jeho optimální stromová dekompozice (s nejmenší možnou šířkou)

Chordální graf je takový graf, který neobsahuje kružnici velikosti alespoň 4 jako indukovaný podgraf.

Příklady[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

  • 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.