Triangulierter Graph
{| class="prettytable float-right"|- bgcolor=#abcdef
| triangulierter Graph
|-
|
|- bgcolor=#fedcba
|
allgemeiner:
|- bgcolor=#abcdef
|
• Graph]
• -
|
|-' target='blank'>bgcolor=#fedcba
|
Beispiele:
|- bgcolor=#abcdef
|
*(Graphentheorie)|Bäume]
•_
• }
In' target='blank'>der Kreis ist ein Dreieck. Ein Kreis ist dabei induziert, wenn zwischen seinen Ecke 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 zwar trianguliert, aber umgekehrt müssen triangulierte Graphen nicht unbedingt Dreiecksgraphen sein, wie ein nicht planarer vollständiger Graph zeigt.
