Perfekter Graph

Perfekter Graph
perfekter Graph

Beispiele:

In der Graphentheorie heißt ein Graph perfekt, wenn für jeden induzierten Subgraphen gilt, dass seine Cliquenzahl mit seiner chromatischen Zahl übereinstimmt. Ein induzierter Subgraph eines Graphen besteht dabei aus einer Teilmenge der Knoten und allen inzidenten Kanten.

In einem perfekten Graphen können chromatische Zahl, Cliquenzahl und Stabilitätszahl in polynomieller Zeit berechnet werden,[1] deren Berechnung auf allgemeinen Graphen NP-vollständig ist. Es kann in polynomieller Zeit bestimmt werden, ob ein Graph perfekt ist.[2] Beispiele für perfekte Graphen sind bipartite Graphen, Kantengraphen bipartiter Graphen und deren Komplemente. Sie bilden die Basis für den starken perfekten Graphensatz und werden daher in diesem Zusammenhang auch als einfache perfekte Graphen (englisch basic) bezeichnet. Weitere Beispiele für perfekte Graphen sind triangulierte Graphen und chordal bipartite Graphen.

Nach dem Satz über perfekte Graphen sind folgende Aussagen äquivalent:

  1. G ist ein perfekter Graph
  2. Das Komplement von G ist perfekt.
  3. G enthält weder einen ungeraden Kreis der Länge mindestens 5 noch das Komplement eines solchen Kreises als induzierten Subgraphen.
    Graphen mit dieser Eigenschaft heißen Berge Graphen oder schwach chordal.

Die zweite Charakteristik ist als schwacher Satz über perfekte Graphen bekannt und wurde schon 1972 von László Lovász bewiesen, deshalb nun Satz von Lovász genannt. Die dritte Charakteristik ist auch als starker Satz über perfekte Graphen bekannt und wurde erst im Mai 2002 bewiesen.[3] Beide Aussagen wurden schon 1960 von Claude Berge als Vermutung aufgestellt (auf einer Konferenz in Halle-Wittenberg, veröffentlicht wurde seine Vermutung erst 1963).

Literatur

  • Perfect Problems Internetseite von Vašek Chvátal über Perfekte Graphen.
  • Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke: Exakte Algorithmen für schwere Graphenprobleme, Springer-Verlag, Berlin Heidelberg, 2010, ISBN 978-3-642-04499-1

Verweise

  1. ↑ Grötschel, Lovász, Schrijver: "Geometric Algorithms and Combinatorial Optimization", Springer-Verlag, 1988, Kapitel 9, "Stable Sets in Graphs", S. 273–303
  2. ↑ Chudnovsky, Cornuéjols, Liu, Seymour, Vušković: "Recognizing Berge Graphs", Combinatorica, Bd. 25, Nr. 2, 2005, S.143–186
  3. ↑ Chudnovsky, Robertson, Seymour, Thomas: "The strong perfect graph theorem", Annals of Mathematics, Bd. 164, 2006, S.51–229

Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

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

  • Paarer Graph — bipartiter Graph allgemeiner: perfekter Graph k partiter Graph Beispiele: Vollständig bipartite Graphen Bäume …   Deutsch Wikipedia

  • Line Graph — Definition Der Kantengraph (engl. line graph) L(G): = (V ,E ) eines ungerichteten Graphen G = (V,E) ist in der Graphentheorie der Graph mit folgenden Eigenschaften: V = E, das heißt jede Kante von G ist ein Knoten in L(G). Je zwei Knoten aus V… …   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

  • Co-Graph — In der Informatik ist ein Co Graph ein ungerichteter Graph    , welcher sich mit bestimmten elementaren Operationen konstruieren lässt. Auf Co Graphen lassen sich viele schwere Probleme wie z. B. UNABHÄNGIGE MENGE, CLIQUE und… …   Deutsch Wikipedia

  • Eindeutig k-färbbarer Graph — Darstellung einer kartographischen Färbung als Graph Eine Färbung eines ungerichteten Graphen ordnet jedem Knoten bzw. jeder Kante im Graphen eine Farbe zu. In der Graphentheorie beschäftigt man sich meist nur mit sogenannten „zulässigen“ oder… …   Deutsch Wikipedia

  • K-chromatischer Graph — Darstellung einer kartographischen Färbung als Graph Eine Färbung eines ungerichteten Graphen ordnet jedem Knoten bzw. jeder Kante im Graphen eine Farbe zu. In der Graphentheorie beschäftigt man sich meist nur mit sogenannten „zulässigen“ oder… …   Deutsch Wikipedia

  • K-färbbarer Graph — Darstellung einer kartographischen Färbung als Graph Eine Färbung eines ungerichteten Graphen ordnet jedem Knoten bzw. jeder Kante im Graphen eine Farbe zu. In der Graphentheorie beschäftigt man sich meist nur mit sogenannten „zulässigen“ oder… …   Deutsch Wikipedia

  • K-kantenfärbbarer Graph — Darstellung einer kartographischen Färbung als Graph Eine Färbung eines ungerichteten Graphen ordnet jedem Knoten bzw. jeder Kante im Graphen eine Farbe zu. In der Graphentheorie beschäftigt man sich meist nur mit sogenannten „zulässigen“ oder… …   Deutsch Wikipedia

  • K-knotenfärbbarer Graph — Darstellung einer kartographischen Färbung als Graph Eine Färbung eines ungerichteten Graphen ordnet jedem Knoten bzw. jeder Kante im Graphen eine Farbe zu. In der Graphentheorie beschäftigt man sich meist nur mit sogenannten „zulässigen“ oder… …   Deutsch Wikipedia

  • 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

Share the article and excerpts

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