Perfekter Graph
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.
| perfekter Graph |
| Beispiele: |
Eigenschaften
In einem perfekten Graphen können chromatische Zahl, Cliquenzahl und Stabilitätszahl in polynomieller Laufzeit 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 bezeichnet. Weitere Beispiele für perfekte Graphen sind chordale Graphen und chordal bipartite Graphen.
Nach dem Satz über perfekte Graphen sind folgende Aussagen äquivalent:
- ist ein perfekter Graph.
- Der Komplementgraph von ist perfekt.
- Weder selbst noch sein Komplementgraph enthält einen ungeraden Zyklus der Länge mindestens 5 als induzierten 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.[3] Beide Aussagen wurden schon 1960 von Claude Berge als Vermutung aufgestellt.
Sätze über perfekte Graphen
In allen Graphen stellt die Cliquenzahl eine Untergrenze für die chromatische Zahl dar, da allen Knoten in einer 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 Teilgraphen. Bei Graphen, die nicht perfekt sind, können sich die chromatische Zahl und die Cliquenzahl unterscheiden. Zum Beispiel erfordert ein Zyklus der Länge fünf drei Farben in jeder Färbung, aber seine größte Clique hat die Größe zwei.
Ein Beweis dafür, dass eine Klasse von 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. 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 Komplementgraphen von 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 besagt, dass eine minimale Knotenüberdeckung in einem bipartiten Graphen einem maximalen Matching entspricht und umgekehrt. Es kann als die Perfektion der Komplementgraphen von bipartiten Graphen interpretiert werden. Ein anderer Satz über bipartite Graphen, dass ihr chromatischer Index ihrem maximalen Knotengrad entspricht, entspricht der Perfektion der Kantengraphen von bipartiten Graphen.
Der schwache Perfekte-Graphen-Satz von László Lovász besagt, dass ein 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ängigen Menge gleich der Cliquenüberdeckungszahl ist.[4][5]
Der starke Perfekte-Graphen-Satz von Chudnovsky, Robertson, Seymour und Thomas liefert eine andere Charakterisierung perfekter Graphen. Ein induzierter 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 nicht perfekt sein, da seine chromatische Zahl und seine Cliquenzahl ist. Alternativ folgt dies aus dem 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.[6]
Literatur
- Vašek Chvátal: 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
Einzelnachweise
- Grötschel, Lovász, Alexander Schrijver: Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, 1988, Kapitel 9, Stable Sets in Graphs, S. 273–303
- Chudnovsky, Cornuéjols, Liu, Seymour, Vušković: Recognizing Berge Graphs. In: Combinatorica, Bd. 25, Nr. 2, 2005, S. 143–186
- Chudnovsky, Robertson, Seymour, Thomas: The strong perfect graph theorem. In: Annals of Mathematics, Bd. 164, 2006, S. 51–229
- Lovász, László: A characterization of perfect graphs. In: Journal of Combinatorial Theory. 13, Nr. 2, 1972, S. 95–98. doi:10.1016/0095-8956(72)90045-7.
- Lovász, László: Perfect graphs. In: Academic Press. 1983, S. 55–87.
- Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: The strong perfect graph theorem. In: Annals of Mathematics. 164, Nr. 1, 2006, S. 51–229. arxiv:math/0212070. doi:10.4007/annals.2006.164.51.