Perfekter Graph - LinkFang.de





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, wurde schon 1972 von László Lovász bewiesen und wird 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

Einzelnachweise

  1. Grötschel, Lovász, Alexander 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. In: Combinatorica, Bd. 25, Nr. 2, 2005, S. 143–186
  3. Chudnovsky, Robertson, Seymour, Thomas: The strong perfect graph theorem. In: Annals of Mathematics, Bd. 164, 2006, S. 51–229

Kategorien: Graphenklasse

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Perfekter Graph (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.