Überlegungen zum Vier-Farben-Satz
Auch wenn ich der Ausbildung nach nicht Mathematiker bin, habe ich mir zum Vier-Farben-Satz (siehe Wikipedia) mehrmals Gedanken gemacht. Da ich in meiner Diplomarbeit in Informatik auch ein graphentheoretisches Thema behandelt habe, bin ich in gewissem Sinne sogar dafür qualifiziert, mir zu diesem Problem Gedanken zu machen.
Grundsätzlich ist das Vier-Farben-Problem natürlich schon gelöst, deswegen spricht man ja auch vom Vier-Farben-Satz. Aber der Beweis ist eben nicht gerade elegant. Im Originalbeweis werden über 1400 Fälle unterschieden. Erst vor weniger als 20 Jahren gelang es, die Fallunterscheidungen auf weniger als die Hälfte zu reduzieren. Wer weiß, vielleicht ist selbst das noch redundant. Ich hatte jedenfalls heute im Schlaf folgenden Einfall:
Gegeben ist ein einfacher, ungerichteter Graph G. Wenn zwei Knoten durch eine Kante verbunden sind, bedeutet das, dass sie im reduzierten Graphen G' voneinander verschieden sein müssen. Der reduzierte Graph G' sei der minimale (die Anzahl der Knoten betreffend) Graph, der in dieser Beziehung die gleichen Eigenschaften wie G hat. Das heißt, zwei Knoten in G' sind genau dann durch eine Kante verbunden, wenn die entsprechenden Knoten auch in G durch eine Kante verbunden sind.
Dieser reduzierte Graph G' hat die gleiche chromatische Zahl wie G. (Chromatische Zahl = minimale Anzahl von Farben, mit denen ein Graph gefärbt werden kann, so dass miteinander durch eine Kante verbundene Knoten zwei verschiedene Farben aufweisen.)
G' hat die Eigenschaft, dass es sich um einen vollständigen Graphen handelt, das heißt, jeder Knoten ist mit jedem anderen Knoten verbunden. Bei G' handelt es sich also um K_n.
Nun ist aber bekannt, dass K_n nur für n <= 4 planar ist. Wenn n >= 5, dann ist K_n nicht planar.
Der Vier-Farben-Satz besagt, dass jeder planare Graph mit maximal vier Farben färbbar ist. Nun ist jeder K_n mit genau n Farben färbbar. Zu zeigen ist: Jeder planare Graph G kann zu einem Graphen G' mit identischer chromatischer Zahl reduziert werden, so dass G' K_n mit n <= 4 entspricht.
Das ist deswegen eine wahre Aussage, weil der Reduktionsalgorithmus wie folgt abläuft:
1. Solange möglich, reduziere die Anzahl der Knoten durch ersatzloses Streichen von Knoten. Dadurch werden in der Regel auch Kanten entfernt. Da keine neuen Kanten hinzukommen, können keine Kreuzungen auftreten. Somit bleibt die Planarität des Graphen erhalten.
2. Wenn das nicht mehr möglich ist, dann überprüfe, ob man zwei bestehende Knoten zu einem neuen Knoten zusammenfassen kann. Das wird dann gemacht, wenn es Knoten gibt, die nur mit einer Kante inzident sind. Zwei solcher Knoten können zu einem Knoten zusammengefasst werden. Dieser neue Knoten ist dann mit den beiden adjazenten Knoten benachbart.
3. Probiere noch einmal, ob nun der erste Schritt wieder möglich ist. Falls nein: fertig. Andernfalls springe zum ersten Schritt.
Der zweite Schritt könnte, wenn er vor dem ersten Schritt angewandt würde, Kreuzungen einfügen. Aufgrund der genannten Reihenfolge der Schritte tritt dieser Fall aber nicht ein. Der zweite Schritt kommt zum Einsatz, wenn ein Zwischengraph G* einen K_n als Teilgraphen enthält und zudem Kanten, mit denen nur ein Knoten inzident ist. Bei n <= 2 ist trivial, dass diese Knoten zusammengefasst werden können, ohne dass eine neue Kreuzung entsteht. Bei 3 <= n <= 4 ist dies auch möglich, weil es immer möglich ist, diese nur mit einer Kante inzidenten Knoten in der "Außenfläche" anzuordnen. So kommt es nie zu Kreuzungen.
Meine Frage ans Publikum: Was fehlt an diesem Beweis? Mein erster Einfall war: Ich muss noch zeigen, dass jeder planare Graph zu einem K_n reduzierbar ist. Aber das habe ich doch schon gesagt: "G' hat die Eigenschaft, dass es sich um einen vollständigen Graphen handelt, das heißt, jeder Knoten ist mit jedem anderen Knoten verbunden. Bei G' handelt es sich also um K_n." Oder ist das eine Behauptung, für die ich noch einen Beweis liefern muss?
Eine kurze Skizze, wie der Algorithmus Knoten entfernt und Knoten zusammenfasst.
Erstes Beispiel:
G sei:
Hier gilt unter anderem:
A ist zu B und C adjazent
D ist zu B und C adjazent
Daher kann ich einen der beiden Knoten (A oder D) ersatzlos streichen. Übrig bleibt ein Dreieck (K_3) ABC. Die chromatische Zahl ist also 3.
Zweites Beispiel:
G sei:
Wenn ich den Knoten E betrachte:
E ist zu C und F adjazent.
Das gilt aber auch für den Knoten D. Dieser ist zwar nicht nur zu C und F adjazent, sondern auch zu B. Trotzdem kann ich den Knoten E ersatzlos streichen. Es genügt, dass die Menge der Knoten, zu denen E adjazent ist, eine Teilmenge jener Knotenmenge ist, zu der D adjazent ist.
Übrig bleibt zunächst also der gleiche Graph, aber ohne den Knoten E.
Nun ist der Knoten F nur zu D adjazent. Da es mehrere andere Knoten gibt, die ebenfalls zu D adjazent sind, kann ich F streichen. Bleibt übrig: das Viereck ABCD.
Nun gilt:
A ist zu B und C adjazent.
D ist zu B und C adjazent.
Also kann ich einen dieser beiden Knoten (A oder D) ersatzlos streichen. Nehmen wir D, dann bleibt übrig ein Gebilde mit dem Knoten A in der Mitte, der mit den beiden Knoten B und C verbunden ist. Hier kann ich wiederum entweder B oder C streichen, weil beide nur zu A adjazent sind. Übrig bleibt also ein K_2, die chromatische Zahl des Graphen G ist daher 2.
Drittes Beispiel:
G sei:
D ist zu B und E adjazent.
C ist zu A, B, E und F adjazent.
Ich kann also D ersatzlos streichen. Analog auf der anderen Seite:
F ist zu C und E adjazent.
B ist zu A, C und E adjazent.
Ich kann also F ersatzlos streichen.
Dann habe ich dasselbe Gebilde wie im ersten Beispiel. Die chromatische Zahl ist also 3.
Viertes Beispiel:
G sei:
A ist zu B und C adjazent.
E ist zu B und C adjazent.
Ich kann also E streichen.
Nun habe ich den Fall, dass ich den zweiten Schritt anwenden muss. Da D und F nur jeweils mit einer Kante inzident sind, kann ich sie zu einem neuen Knoten zusammenfassen. Dieser ist dann sowohl zu B als auch zu C adjazent.
Es ergibt sich also wieder ein Gebilde wie im ersten Beispiel, die chromatische Zahl ist also 3.
Fünftes Beispiel:
G sei:
Hier sind die Nachbarknotenmengen von A und C Teilmengen der Nachbarknotenmenge von B, analog sind die Nachbarknotenmengen von F und H Teilmengen der Nachbarknotenmenge von G, deswegen kann ich A, C, F und H ersatzlos streichen. Bleibt wieder ein Gebilde wie im ersten Beispiel übrig.
Sechstes Beispiel:
G sei:
Hier wird die Sache schon schwieriger. Hier kann man wie folgt argumentieren: Sowohl A als auch D sind zu C adjazent sowie zu einem Knoten x, der folgende Eigenschaft hat: Er ist zu C adjazent sowie zu dem jeweiligen Knoten, den wir vorhin betrachtet haben (also A bzw. D). Somit kann man entweder A und D sowie einen dieser beiden Knoten x (also B oder E) ersatzlos streichen. Bleibt übrig K_3, also ist die chromatische Zahl 3.
Siebtes Beispiel:
G sei:
Hier gilt: Die Adjazenzen von C und E sind Teilmengen der Adjazenzmenge von D, also kann ich C und E ersatzlos streichen und erhalte wieder das Gebilde von Beispiel 6. Die chromatische Zahl ist also 3.
Achtes Beispiel:
G sei:
Hier kann ich zunächst, analog zum siebten Beispiel, E entfernen, dann F. Nun kann ich G, H und I zu einem neuen Knoten vereinigen, der an C und D grenzt. Dann kann ich wieder Knoten streichen und erhalte eine chromatische Zahl von 3.
Diese Beispiele sollen veranschaulichen, wie der Algorithmus abläuft. Wahrscheinlich fehlt der Beweis, dass dieser Algorithmus mit jedem planaren Graphen funktioniert.
Grundsätzlich ist das Vier-Farben-Problem natürlich schon gelöst, deswegen spricht man ja auch vom Vier-Farben-Satz. Aber der Beweis ist eben nicht gerade elegant. Im Originalbeweis werden über 1400 Fälle unterschieden. Erst vor weniger als 20 Jahren gelang es, die Fallunterscheidungen auf weniger als die Hälfte zu reduzieren. Wer weiß, vielleicht ist selbst das noch redundant. Ich hatte jedenfalls heute im Schlaf folgenden Einfall:
Gegeben ist ein einfacher, ungerichteter Graph G. Wenn zwei Knoten durch eine Kante verbunden sind, bedeutet das, dass sie im reduzierten Graphen G' voneinander verschieden sein müssen. Der reduzierte Graph G' sei der minimale (die Anzahl der Knoten betreffend) Graph, der in dieser Beziehung die gleichen Eigenschaften wie G hat. Das heißt, zwei Knoten in G' sind genau dann durch eine Kante verbunden, wenn die entsprechenden Knoten auch in G durch eine Kante verbunden sind.
Dieser reduzierte Graph G' hat die gleiche chromatische Zahl wie G. (Chromatische Zahl = minimale Anzahl von Farben, mit denen ein Graph gefärbt werden kann, so dass miteinander durch eine Kante verbundene Knoten zwei verschiedene Farben aufweisen.)
G' hat die Eigenschaft, dass es sich um einen vollständigen Graphen handelt, das heißt, jeder Knoten ist mit jedem anderen Knoten verbunden. Bei G' handelt es sich also um K_n.
Nun ist aber bekannt, dass K_n nur für n <= 4 planar ist. Wenn n >= 5, dann ist K_n nicht planar.
Der Vier-Farben-Satz besagt, dass jeder planare Graph mit maximal vier Farben färbbar ist. Nun ist jeder K_n mit genau n Farben färbbar. Zu zeigen ist: Jeder planare Graph G kann zu einem Graphen G' mit identischer chromatischer Zahl reduziert werden, so dass G' K_n mit n <= 4 entspricht.
Das ist deswegen eine wahre Aussage, weil der Reduktionsalgorithmus wie folgt abläuft:
1. Solange möglich, reduziere die Anzahl der Knoten durch ersatzloses Streichen von Knoten. Dadurch werden in der Regel auch Kanten entfernt. Da keine neuen Kanten hinzukommen, können keine Kreuzungen auftreten. Somit bleibt die Planarität des Graphen erhalten.
2. Wenn das nicht mehr möglich ist, dann überprüfe, ob man zwei bestehende Knoten zu einem neuen Knoten zusammenfassen kann. Das wird dann gemacht, wenn es Knoten gibt, die nur mit einer Kante inzident sind. Zwei solcher Knoten können zu einem Knoten zusammengefasst werden. Dieser neue Knoten ist dann mit den beiden adjazenten Knoten benachbart.
3. Probiere noch einmal, ob nun der erste Schritt wieder möglich ist. Falls nein: fertig. Andernfalls springe zum ersten Schritt.
Der zweite Schritt könnte, wenn er vor dem ersten Schritt angewandt würde, Kreuzungen einfügen. Aufgrund der genannten Reihenfolge der Schritte tritt dieser Fall aber nicht ein. Der zweite Schritt kommt zum Einsatz, wenn ein Zwischengraph G* einen K_n als Teilgraphen enthält und zudem Kanten, mit denen nur ein Knoten inzident ist. Bei n <= 2 ist trivial, dass diese Knoten zusammengefasst werden können, ohne dass eine neue Kreuzung entsteht. Bei 3 <= n <= 4 ist dies auch möglich, weil es immer möglich ist, diese nur mit einer Kante inzidenten Knoten in der "Außenfläche" anzuordnen. So kommt es nie zu Kreuzungen.
Meine Frage ans Publikum: Was fehlt an diesem Beweis? Mein erster Einfall war: Ich muss noch zeigen, dass jeder planare Graph zu einem K_n reduzierbar ist. Aber das habe ich doch schon gesagt: "G' hat die Eigenschaft, dass es sich um einen vollständigen Graphen handelt, das heißt, jeder Knoten ist mit jedem anderen Knoten verbunden. Bei G' handelt es sich also um K_n." Oder ist das eine Behauptung, für die ich noch einen Beweis liefern muss?
Eine kurze Skizze, wie der Algorithmus Knoten entfernt und Knoten zusammenfasst.
Erstes Beispiel:
G sei:
Hier gilt unter anderem:
A ist zu B und C adjazent
D ist zu B und C adjazent
Daher kann ich einen der beiden Knoten (A oder D) ersatzlos streichen. Übrig bleibt ein Dreieck (K_3) ABC. Die chromatische Zahl ist also 3.
Zweites Beispiel:
G sei:
Wenn ich den Knoten E betrachte:
E ist zu C und F adjazent.
Das gilt aber auch für den Knoten D. Dieser ist zwar nicht nur zu C und F adjazent, sondern auch zu B. Trotzdem kann ich den Knoten E ersatzlos streichen. Es genügt, dass die Menge der Knoten, zu denen E adjazent ist, eine Teilmenge jener Knotenmenge ist, zu der D adjazent ist.
Übrig bleibt zunächst also der gleiche Graph, aber ohne den Knoten E.
Nun ist der Knoten F nur zu D adjazent. Da es mehrere andere Knoten gibt, die ebenfalls zu D adjazent sind, kann ich F streichen. Bleibt übrig: das Viereck ABCD.
Nun gilt:
A ist zu B und C adjazent.
D ist zu B und C adjazent.
Also kann ich einen dieser beiden Knoten (A oder D) ersatzlos streichen. Nehmen wir D, dann bleibt übrig ein Gebilde mit dem Knoten A in der Mitte, der mit den beiden Knoten B und C verbunden ist. Hier kann ich wiederum entweder B oder C streichen, weil beide nur zu A adjazent sind. Übrig bleibt also ein K_2, die chromatische Zahl des Graphen G ist daher 2.
Drittes Beispiel:
G sei:
C ist zu A, B, E und F adjazent.
Ich kann also D ersatzlos streichen. Analog auf der anderen Seite:
F ist zu C und E adjazent.
B ist zu A, C und E adjazent.
Ich kann also F ersatzlos streichen.
Dann habe ich dasselbe Gebilde wie im ersten Beispiel. Die chromatische Zahl ist also 3.
Viertes Beispiel:
G sei:
A ist zu B und C adjazent.
E ist zu B und C adjazent.
Ich kann also E streichen.
Nun habe ich den Fall, dass ich den zweiten Schritt anwenden muss. Da D und F nur jeweils mit einer Kante inzident sind, kann ich sie zu einem neuen Knoten zusammenfassen. Dieser ist dann sowohl zu B als auch zu C adjazent.
Es ergibt sich also wieder ein Gebilde wie im ersten Beispiel, die chromatische Zahl ist also 3.
Fünftes Beispiel:
G sei:
Hier sind die Nachbarknotenmengen von A und C Teilmengen der Nachbarknotenmenge von B, analog sind die Nachbarknotenmengen von F und H Teilmengen der Nachbarknotenmenge von G, deswegen kann ich A, C, F und H ersatzlos streichen. Bleibt wieder ein Gebilde wie im ersten Beispiel übrig.
Sechstes Beispiel:
G sei:
Hier wird die Sache schon schwieriger. Hier kann man wie folgt argumentieren: Sowohl A als auch D sind zu C adjazent sowie zu einem Knoten x, der folgende Eigenschaft hat: Er ist zu C adjazent sowie zu dem jeweiligen Knoten, den wir vorhin betrachtet haben (also A bzw. D). Somit kann man entweder A und D sowie einen dieser beiden Knoten x (also B oder E) ersatzlos streichen. Bleibt übrig K_3, also ist die chromatische Zahl 3.
Siebtes Beispiel:
G sei:
Hier gilt: Die Adjazenzen von C und E sind Teilmengen der Adjazenzmenge von D, also kann ich C und E ersatzlos streichen und erhalte wieder das Gebilde von Beispiel 6. Die chromatische Zahl ist also 3.
Achtes Beispiel:
G sei:
Hier kann ich zunächst, analog zum siebten Beispiel, E entfernen, dann F. Nun kann ich G, H und I zu einem neuen Knoten vereinigen, der an C und D grenzt. Dann kann ich wieder Knoten streichen und erhalte eine chromatische Zahl von 3.
Diese Beispiele sollen veranschaulichen, wie der Algorithmus abläuft. Wahrscheinlich fehlt der Beweis, dass dieser Algorithmus mit jedem planaren Graphen funktioniert.
Kommentare
Kommentar veröffentlichen