Triangulierter Graph

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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

Eigenschaften[Bearbeiten]

In triangulierten Graphen lässt sich die Berechnung der Parameter \alpha, \theta, \omega und \chi – für beliebige Graphen ein NP-äquivalentes Problem – 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.

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[Bearbeiten]

Weblinks[Bearbeiten]