Chordale Graphen

triangulierter Graph

allgemeiner:

perfekter Graph Schnittgraph

Beispiele:

Intervallgraphen Bäume Dreiecksgraphen

In der Graphentheorie nennt man einen Graphen G trianguliert oder chordal, wenn er einer der folgenden äquivalenten Bedingungen genügt:

• Jeder induzierte Kreis ist ein Dreieck. Ein Kreis ist dabei induziert, wenn zwischen seinen Ecken keine weiteren Kanten im Ursprungsgraph existieren.
• Jeder minimale a-b-Trenner zu zwei Ecken a und b ist eine Clique.
• Jeder induzierte Teilgraph enthält eine simpliziale Ecke (Rose, 1970), also eine Ecke, deren Nachbarn eine Clique bilden.
• G ist Schnittgraph einer Menge von Teilbäumen eines Baums (Gavril, 1974).

In triangulierten Graphen lässt sich die Berechnung der Parameter α, θ, ω und χ – für beliebige Graphen ein NP-vollständiges Problem – in Linearzeit durchführen. Die Charakterisierung über simpliziale Ecken ermöglicht einen Chordalitätstest in Linearzeit.

Triangulierte Graphen sind nicht zu verwechseln mit den (maximal planaren) Dreiecksgraphen. Dreiecksgraphen sind nicht alle trianguliert, wie man sich an einem Graphen überlegen kann, welcher aus einem Kreis der Länge $l\ge 4$ besteht, in dessen Inneren und Äußeren je ein weiterer Knoten liegt, der mit allen Knoten des Kreises benachbart ist. Umgekehrt müssen triangulierte Graphen auch nicht unbedingt Dreiecksgraphen sein, wie ein nicht planarer vollständiger Graph zeigt.