Chordaler Graph

In der Graphentheorie nennt man einen Graphen G {\displaystyle G} chordal oder trianguliert, genau dann wenn er einer der folgenden äquivalenten Bedingungen genügt:

• Jeder induzierte Kreis ist ein Dreieck. Ein Kreis ist dabei induziert, genau dann wenn zwischen seinen Knoten keine weiteren Kanten im Ursprungsgraphen 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 chordalen Graphen lässt sich die Berechnung der Parameter Cliquenzahl, chromatische Zahl, Unabhängigkeitszahl und Cliquenüberdeckungszahl – für beliebige Graphen NP-schwere Probleme – in Linearzeit durchführen. Die Charakterisierung über simpliziale Ecken ermöglicht einen Chordalitätstest in Linearzeit. Als perfekte Eliminationsordnung bezeichnet man dabei eine Knotenreihenfolge ( v 1 , v 2 , … , v n ) , V = { v 1 , v 2 , … , v n } {\displaystyle (v_{1},v_{2},\ldots ,v_{n}),V=\{v_{1},v_{2},\ldots ,v_{n}\}} des Graphen G = ( V , E ) {\displaystyle G=(V,E)} , sodass für jeden Graphen mit der (durch Eliminierung der Knoten v 1 {\displaystyle v_{1}} bis v i − 1 {\displaystyle v_{i-1}} ) eingeschränkten Knotenmenge G i = ( { v i , … , v n } , E i ) {\displaystyle G_{i}=(\{v_{i},\ldots ,v_{n}\},E_{i})} gilt: v i {\displaystyle v_{i}} ist simplizial in G i {\displaystyle G_{i}} . Jeder (in Bezug auf die gewählte Ordnung) „kleinste“ Knoten in G i {\displaystyle G_{i}} bildet also mit seinen Nachbarn eine Clique.

• Jorge L. Ramírez Alfonsín, Bruce A. Reed: Perfect Graphs. Wiley 2001, ISBN 978-0-471-48970-2, 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 978-3-8348-0629-1. S. 61

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