Chordaler Graph
# Chordaler Graph

In der Graphentheorie nennt man einen Graphen $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).

## Eigenschaften

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},\ldots ,v_{n}),V=\{v_{1},v_{2},\ldots ,v_{n}\}$ des Graphen $G=(V,E)$, sodass für jeden Graphen mit der (durch Eliminierung der Knoten $v_{1}$ bis $v_{i-1}$) eingeschränkten Knotenmenge $G_{i}=(\{v_{i},\ldots ,v_{n}\},E_{i})$ gilt: $v_{i}$ ist simplizial in $G_{i}$. Jeder (in Bezug auf die gewählte Ordnung) „kleinste“ Knoten in $G_{i}$ bildet also mit seinen Nachbarn eine Clique.

