Chordaler Graph

Ein triangulierter Graph (auch chordaler Graph genannt) ist in der Graphentheorie ein Graph, in dem alle induzierten Kreis (Graphentheorie)e Dreiecke sind. Ein Kreis ist dabei induziert, wenn zwischen seinen Knoten keine weiteren Kanten im Ursprungsgraph existieren.

Da triangulierten Graphen auch immer perfekte Graphen sind, lassen sich in ihnen bestimmte Grapheigenschaften effizient berechnen. So läßt sich beispielsweise eine größte Clique in O(n+m) bestimmen und damit unter anderem auch eine minimale Färbung.

Triangulierte Graphen sind nicht zu verwechseln mit den (maximal planaren) Dreiecksgraphen. Es lässt sich zwar zeigen, dass Dreiecksgraphen trianguliert sind, aber umgekehrt müssen triangulierte Graphen nicht unbedingt Dreiecksgraphen sein, wie zum Beispiel ein nicht planarer vollständiger Graph zeigt.