imported>Ulanwp: 3 fehlende Sprachparameter eingefügt; 3 Datumsparameter konvertiert

2026-04-23T07:16:12Z

3 fehlende Sprachparameter eingefügt; 3 Datumsparameter konvertiert

Neue Seite

{| class="wikitable float-right"
|-
|style="background:#ABCDEF"| '''perfekter Graph'''
|-
|
|-
|style="background:#FEDCBA"| Beispiele:
|-
|style="background:#ABCDEF"|
* [[Chordaler Graph|Chordale Graphen]]
* [[Bipartiter Graph|Bipartite Graphen]]
* [[Vollständiger Graph|Vollständige Graphen]]
* [[Co-Graph]]en
* [[Vergleichbarkeitsgraph]]en
|}

[[Datei:Paley9-perfect.svg|mini]]

In der [[Graphentheorie]] heißt ein [[Graph (Graphentheorie)|Graph]] '''perfekt''', wenn für jeden [[Induzierter Teilgraph|induzierten Subgraphen]] gilt, dass seine [[Cliquenzahl]] mit seiner [[Chromatische Zahl|chromatischen Zahl]] übereinstimmt. Ein induzierter Subgraph eines Graphen besteht dabei aus einer Teilmenge der [[Knoten (Graphentheorie)|Knoten]] und allen [[Inzidenz (Graphentheorie)|inzidenten]] [[Kante (Graphentheorie)|Kanten]].

== Eigenschaften ==
In einem perfekten Graphen können chromatische Zahl, Cliquenzahl und [[Stabilitätszahl]] in polynomieller [[Laufzeit (Informatik)|Laufzeit]] berechnet werden,<ref>[[Martin Grötschel|Grötschel]], [[László Lovász|Lovász]], [[Alexander Schrijver]]: ''Geometric Algorithms and Combinatorial Optimization''. Springer-Verlag, 1988, Kapitel 9, ''Stable Sets in Graphs'', S. 273–303</ref> deren Berechnung auf allgemeinen Graphen [[NP-vollständig]] ist. Es kann in polynomieller Zeit bestimmt werden, ob ein Graph perfekt ist.<ref>[[Maria Chudnovsky|Chudnovsky]], Cornuéjols, Liu, [[Paul Seymour (Mathematiker)|Seymour]], Vušković: ''Recognizing Berge Graphs''. In: ''Combinatorica'', Bd. 25, Nr. 2, 2005, S. 143–186</ref> Beispiele für perfekte Graphen sind [[Bipartiter Graph|bipartite Graphen]], [[Kantengraph]]en 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''' bezeichnet. Weitere Beispiele für perfekte Graphen sind [[chordale Graphen]] und [[Chordal bipartiter Graph|chordal bipartite Graphen]].

Nach dem '''Satz über perfekte Graphen''' sind folgende Aussagen äquivalent:
# ''<math>G</math>'' ist ein perfekter [[Graph (Graphentheorie)|Graph]].
# Der [[Komplementgraph]] von ''<math>G</math>'' ist perfekt.
# Weder ''<math>G</math>'' selbst noch sein [[Komplementgraph]] enthält einen ungeraden [[Zyklus (Graphentheorie)|Zyklus]] der Länge mindestens 5 als induzierten [[Teilgraph|Teilgraphen]]. Graphen mit dieser Eigenschaft heißen '''Berge-Graphen'''.

Die zweite Charakteristik ist als '''schwacher Perfekte-Graphen-Satz''' 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 Perfekte-Graphen-Satz''' bekannt und wurde erst im Mai 2002 bewiesen.<ref>[[Maria Chudnovsky|Chudnovsky]], [[Neil Robertson (Mathematiker)|Robertson]], [[Paul Seymour (Mathematiker)|Seymour]], [[Robin Thomas (Mathematiker)|Thomas]]: ''The strong perfect graph theorem''. In: ''Annals of Mathematics'', Bd. 164, 2006, S. 51–229</ref> Beide Aussagen wurden schon 1960 von [[Claude Berge]] als Vermutung aufgestellt.

== Sätze über perfekte Graphen ==
In allen [[Graph (Graphentheorie)|Graphen]] stellt die [[Cliquenzahl]] eine Untergrenze für die chromatische Zahl dar, da allen [[Knoten (Graphentheorie)|Knoten]] in einer [[Clique (Graphentheorie)|Clique]] in jeder richtigen Farbe unterschiedliche Farben zugewiesen werden müssen. Die perfekten Graphen sind diejenigen, für die diese Untergrenze fest ist, nicht nur im Graphen selbst, sondern in allen induzierten [[Teilgraph|Teilgraphen]]. Bei Graphen, die nicht perfekt sind, können sich die chromatische Zahl und die Cliquenzahl unterscheiden. Zum Beispiel erfordert ein [[Zyklus (Graphentheorie)|Zyklus]] der Länge fünf drei Farben in jeder [[Färbung (Graphentheorie)|Färbung]], aber seine größte Clique hat die Größe zwei.

Ein Beweis dafür, dass eine Klasse von [[Graph (Graphentheorie)|Graphen]] perfekt ist, kann als [[Min-Max-Theorem]] angesehen werden: Die minimale Anzahl von Farben, die für diese Graphen benötigt wird, entspricht der maximalen Größe einer [[Clique (Graphentheorie)|Clique]]. Viele wichtige Min-Max-Theoreme in der [[Kombinatorik]] können mit diesen Begriffen ausgedrückt werden.

Zum Beispiel besagt der [[Satz von Dilworth]], dass die minimale Anzahl von Ketten in einer Partition einer [[Halbordnung]] in Ketten der maximalen Größe einer [[Antikette]] entspricht und so umformuliert werden kann, dass die [[Komplementgraph|Komplementgraphen]] von [[Vergleichbarkeitsgraph|Vergleichbarkeitsgraphen]] perfekt sind. Der Satz von Mirsky besagt, dass die minimale Anzahl von Antiketten in einer Partition in Antiketten der maximalen Größe einer Kette entspricht und in gleicher Weise der Perfektion von Vergleichbarkeitsgraphen entspricht.

Die Perfektion von Permutationsgraphen entspricht der Aussage, dass in jeder Folge von geordneten Elementen die Länge der längsten aufsteigenden [[Teilfolge]] der minimalen Anzahl von Folgen in einer Partition in aufsteigende Teilfolgen entspricht. Der Satz von Erdős-Szekeres ist eine einfache Folgerung aus dieser Aussage.

Der [[Satz von König (Graphentheorie)|Satz von König]] besagt, dass eine minimale [[Knotenüberdeckung]] in einem [[Bipartiter Graph|bipartiten Graphen]] einem [[Maximales Matching|maximalen Matching]] entspricht und umgekehrt. Es kann als die Perfektion der [[Komplementgraph|Komplementgraphen]] von bipartiten Graphen interpretiert werden. Ein anderer Satz über bipartite Graphen, dass ihr [[chromatischer Index]] ihrem maximalen [[Knotengrad]] entspricht, entspricht der Perfektion der [[Kantengraph|Kantengraphen]] von bipartiten Graphen.
[[Datei:7-hole and antihole.svg|mini|Ein [[Zyklus (Graphentheorie)|Zyklus]] mit sieben [[Knoten (Graphentheorie)|Knoten]] und sein [[Komplementgraph]], der jeweils eine optimale Färbung und eine maximale [[Clique (Graphentheorie)|Clique]] zeigt. Weil kein [[Graph (Graphentheorie)|Graph]] eine Anzahl von Farben verwendet, die gleich seiner Cliquengröße ist, ist keiner perfekt.]]
Der [[Schwacher Perfekte-Graphen-Satz|schwache Perfekte-Graphen-Satz]] von [[László Lovász]] besagt, dass ein [[Graph (Graphentheorie)|Graph]] genau dann perfekt ist, wenn sein [[Komplementgraph]] perfekt ist. Somit entspricht die Perfektion eines Graphen definiert als die Gleichheit der maximalen Cliquengröße und der chromatischen Zahl in jedem induzierten Teilgraphen der Aussage, dass die Größe einer maximalen [[Unabhängige Menge|unabhängigen Menge]] gleich der Cliquenüberdeckungszahl ist.<ref>{{cite journal |author=Lovász, László |authorlink=László Lovász |date=1972 |title=A characterization of perfect graphs |journal=Journal of Combinatorial Theory |volume=13 |issue=2 |pages=95–98 |doi=10.1016/0095-8956(72)90045-7 |language=en}}</ref><ref>{{cite journal |author=Lovász, László |authorlink=László Lovász |date=1983 |title=Perfect graphs |journal=Academic Press |pages=55–87 |language=en}}</ref>

Der [[starke Perfekte-Graphen-Satz]] von Chudnovsky, Robertson, Seymour und Thomas liefert eine andere Charakterisierung perfekter Graphen. Ein induzierter [[Zyklus (Graphentheorie)|Zyklus]] mit einer ungeraden Länge von mindestens 5 wird als ''ungerades Loch'' bezeichnet. Ein induzierter Teilgraph, der der [[Komplementgraph]] eines ungeraden Lochs darstellt, wird als ''ungerades Antiloch'' bezeichnet. Ein ungerader Zyklus mit einer Länge von mehr als 3 kann nicht perfekt sein, da seine chromatische Zahl drei und seine [[Cliquenzahl]] zwei ist. In ähnlicher Weise kann der Komplementgraph eines ungeraden Zyklus der Länge ''<math>2 \cdot k + 1</math>'' nicht perfekt sein, da seine chromatische Zahl ''<math>k + 1</math>'' und seine Cliquenzahl ''<math>k</math>'' ist. Alternativ folgt dies aus dem [[Schwacher Perfekte-Graphen-Satz|Perfekte-Graphen-Satz]] und daraus, dass der komplementäre ungerade Zyklus nicht perfekt ist. Weil diese Graphen nicht perfekt sind, muss jeder perfekte Graph ein Berge-Graph sein, ein Graph ohne ungerade Löcher und ohne ungerade Antilöcher.<ref>{{cite journal |first1=Maria |last1=Chudnovsky |first2=Neil |last2=Robertson |first3=Paul |last3=Seymour |first4=Robin |last4=Thomas |date=2006 |title=The strong perfect graph theorem |journal=[[Annals of Mathematics]] |volume=164 |issue=1 |pages=51–229 |doi=10.4007/annals.2006.164.51 |arxiv=math/0212070 |url=http://annals.princeton.edu/annals/2006/164-1/p02.xhtml |language=en}}</ref>

== Literatur ==
* [[Vašek Chvátal]]: [http://www.cs.concordia.ca/~chvatal/perfect/problems.html ''Perfect Problems''.] ü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

== Weblinks ==
* [http://www.graphclasses.org/classes/gc_56.html ''perfect''] – Eintrag im Information System on Graph Classes and their Inclusions
* [http://www.graphclasses.org/classes/gc_274.html ''Berge''] – Eintrag im Information System on Graph Classes and their Inclusions

== Einzelnachweise ==
<references />

[[Kategorie:Graphenklasse]]

Perfekter Graph - Versionsgeschichte

imported>Ulanwp: 3 fehlende Sprachparameter eingefügt; 3 Datumsparameter konvertiert