Triangulierte Graphen

Triangulierte Graphen
triangulierter Graph

allgemeiner:

Beispiele:

  • Intervallgraphen
  • Bäume
  • Dreiecksgraphen

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

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


Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Perfekte Graphen — perfekter Graph Beispiele: Triangulierte Graphen Bipartite Graphen Vollständige Graphen Cographen In der Graphentheorie heißt ein Graph perfekt, wenn für jeden induzierten Subgraphen gilt, dass seine Cliquenzahl mit seiner …   Deutsch Wikipedia

  • Chordale Graphen — triangulierter Graph allgemeiner: perfekter Graph Schnittgraph Beispiele: Intervallgraphen Bäume Dreiecksgraphen In der Graphentheorie nennt man einen Graphen G trianguliert oder chordal, wenn er ei …   Deutsch Wikipedia

  • Perfekter Graph — Beispiele: Triangulierte Graphen Bipartite Graphen Vollständige Graphen Co Graphen In der Graphentheorie heißt ein Graph perfekt, wenn für jeden induzierten Subgraphen gilt, dass seine Cliquenzahl mit seiner chromatischen Zahl übereinstimmt. Ein… …   Deutsch Wikipedia

  • Chordal — triangulierter Graph allgemeiner: perfekter Graph Schnittgraph Beispiele: Intervallgraphen Bäume Dreiecksgraphen In der Graphentheorie nennt man einen Graphen G trianguliert oder chordal, wenn er ei …   Deutsch Wikipedia

  • Chordaler Graph — triangulierter Graph allgemeiner: perfekter Graph Schnittgraph Beispiele: Intervallgraphen Bäume Dreiecksgraphen In der Graphentheorie nennt man einen Graphen G trianguliert oder chordal, wenn er ei …   Deutsch Wikipedia

  • Triangulierter Graph — 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… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”