Perfekte Graphen

Perfekte Graphen
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. Es kann in polynomieller Zeit bestimmt werden, ob ein Graph perfekt ist. 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.

Die zweite Charakteristik ist als schwacher Satz über perfekte Graphen bekannt und wurde schon 1972 von Laszlo Lovasz 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[1]. 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

Verweise

  1. ↑ 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:

  • Schwacher Perfekte-Graphen-Satz — Der schwache Perfekte Graphen Satz (oder auch nur Perfekte Graphen Satz und Satz von Lovász) ist ein mathematischer Satz aus der Graphentheorie, der sich mit Strukturen, die bei Eckenfärbungen auftreten, beschäftigt. Er wurde 1972 erstmals von… …   Deutsch Wikipedia

  • Perfekte Paarung — Eine Paarung (Matching) ist in der Graphentheorie eine Teilmenge der Kanten eines Graphen, in der keine zwei Kanten einen gemeinsamen Knoten besitzen. Paarungen haben innerhalb der Graphentheorie einen weiten Anwendungsbereich. Inhaltsverzeichnis …   Deutsch Wikipedia

  • Färbung von Graphen — 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

  • Paarungen in Graphen — Eine Paarung (Matching) ist in der Graphentheorie eine Teilmenge der Kanten eines Graphen, in der keine zwei Kanten einen gemeinsamen Knoten besitzen. Paarungen haben innerhalb der Graphentheorie einen weiten Anwendungsbereich. Inhaltsverzeichnis …   Deutsch Wikipedia

  • Durchlaufbarkeit von Graphen — Es gibt in der Graphentheorie zahlreiche Probleme, die sich mit dem Durchlaufen von Graphen befassen. Man unterscheidet Probleme beim Durchlaufen der Kanten von Problemen beim Durchlaufen der Knoten. Im Folgenden werden die wichtigsten Probleme… …   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

  • Satz von Lovász — Der schwache Perfekte Graphen Satz (oder auch nur Perfekte Graphen Satz ) ist ein mathematischer Satz aus der Graphentheorie, der sich mit Strukturen, die bei Eckenfärbungen auftreten, beschäftigt. Er wurde 1972 erstmals von László Lovász… …   Deutsch Wikipedia

  • Bipartition (Graphentheorie) — 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

  • 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

  • Färbung (Graphentheorie) — 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

Share the article and excerpts

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