Chordaler Graph

Chordaler Graph
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:

  • Schwach chordaler Graph — In der Graphentheorie heißt ein Graph G schwach chordal (engl. weakly chordal), falls jeder induzierte Kreis in G die Länge 3 oder 4 hat. Eine wichtige Unterklasse der schwach chordalen Graphen sind die chordal bipartiten Graphen. Kategorie:… …   Deutsch Wikipedia

  • Bogen (Graph) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • K-regulärer Graph — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Kubischer Graph — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Metrischer Graph — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Regulärer Graph — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Schleifenfreier Graph — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Schleifenloser Graph — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Ungerichteter Graph — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Abstand (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

Share the article and excerpts

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