Triangulierter Graph

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.

Literatur

• Jorge L. Ramírez Alfonsín, Bruce A. Reed: Perfect Graphs. Wiley 2001, ISBN 9780471489702, S. 14 (eingeschränkte Online-Version in der Google Buchsuche-USA)
• Sven Oliver Krumke und Hartmut Noltemeier: Graphentheoretische Konzepte und Algorithmen. 2. Auflage Vieweg-Teubner 2009. ISBN 9783834806291. S. 61

Weblinks

• Eric W. Weisstein: Chordal Graph. In: MathWorld. (englisch)