Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 26

Uff, das wär geschafft. Nicht nur Vorli braucht jetzt erstmal Urlaub. Irgendwas mit Bergen und Meer. Land egal.


Die Länder auf der Erde bilden zusammenhängende Gebiete (Exklaven werden ausgeschlossen), ihre Grenzen bilden kurvige Wege. Wir repräsentieren diese Situation durch einen Nachbarschaftsgraphen, wobei die Länder zu Knotenpunkten werden und zwei Knotenpunkte miteinander durch eine Kante verbunden werden, wenn die zugehörigen Länder eine Grenze gemeinsam haben, wobei wir Berührungen in einem einzigen Punkt ausschließen. Wenn man bei einer Karte jedem Land eine Farbe geben möchte derart, dass angrenzende Länder unterschiedliche Farben bekommen, so bedeutet dies, für den Graphen eine zulässige Färbung zu finden. Eine wichtige Frage der Graphentheorie ist, mit wie vielen Farben dies möglich ist. Da die Länder in der Ebene gegeben sind, ist der zugehörige Graph planar. Deshalb ist die Frage letztlich, was die chromatische Zahl eines ebenen Graphen ist. Wir werden hier den sogenannten Fünf-Farben-Satz beweisen, der besagt, dass man für jeden ebenen Graphen eine zulässige Färbung mit höchstens fünf Farben finden kann. Als Einstimmung beweisen wir zuerst den Sechs-Farben-Satz.

Wenn auch nur punktweise Berührungen zwischen Ländern als Grenzen denkbar sind, so lässt sich dies nicht durch einen planaren Graphen realisieren, da dann beliebig große vollständige Graphen auftreten können.



Satz  

Für jeden ebenen Graphen

besteht eine zulässige Färbung mit höchstens sechs Farben.

Beweis  

Wir führen Induktion über die Anzahl der Knoten, wobei die Aussage bei höchstens Knoten unmittelbar klar ist. Es liege also ein ebener Graph mit Knoten vor und für jeden ebenen Graphen mit weniger als Knoten wissen wir, dass es eine zulässige Färbung mit höchstens Farben gibt. Nach Korollar 25.6  (2) gibt es einen Knoten mit höchstens Nachbarn. Es sei der Graph, der aus entsteht, wenn man und die an anliegenden Kanten herausnimmt. Nach Induktionsvoraussetzung besitzt eine zulässige Färbung mit höchstens sechs Farben. Die Nachbarn von verwenden höchstens Farben davon und daher kann man für eine sechste Farbe wählen, was insgesamt eine zulässige Färbung von mit Farben ergibt.




Satz  

Für jeden ebenen Graphen

besteht eine zulässige Färbung mit höchstens fünf Farben.

Beweis  

Wir führen Induktion über die Anzahl der Knoten, wobei die Aussage bei höchstens Knoten unmittelbar klar ist. Es liege also ein ebener Graph mit Knoten vor und für jeden ebenen Graphen mit weniger als Knoten wissen wir, dass es eine zulässige Färbung mit höchstens Farben gibt. Nach Korollar 25.6  (2) gibt es einen Knoten mit höchstens Nachbarn. Es sei der Graph, der aus entsteht, wenn man und die an anliegenden Kanten herausnimmt. Nach Induktionsvoraussetzung besitzt eine zulässige Färbung mit höchstens fünf Farben. Wenn die Nachbarn von nur höchstens vier Farben verwenden, was insbesondere dann der Fall ist, wenn höchstens vier Nachbarn besitzt, so kann man unmittelbar eine zulässige Färbung von zu einer zulässigen Färbung von ausbauen, indem man eine Farbe gibt, die in seinen Nachbarn nicht vorkommt.

Der Punkt habe also genau Nachbarn mit verschiedenen Farben. Wir fixieren eine ebene Realisierung und wir bezeichnen die Nachbarn von mit im Uhrzeigersinn (ein kleiner Kreis um in , der keinen weiteren Knotenpunkt enthält, trifft jeden Verbindungsweg zu den Nachbarn in einem Punkt der Peripherie, dies legt die Reihenfolge fest). Es sei eine zulässige Färbung auf . Wie betrachten den induzierten Untergraphen

Wir machen nun eine Fallunterscheidung je nachdem, ob und in miteinander durch einen Weg verbunden sind oder nicht.

Fall 1. Sie sind nicht miteinander verbunden. Es sei die Zusammenhangskomponente von , die enthält. Dabei gilt . Wir legen jetzt auf eine neue Färbung fest, indem wir

festlegen. Für die Knoten aus werden also die beiden Farben und vertauscht, alle anderen Knoten behalten ihre Farben. Diese Färbung ist wieder zulässig. Dies ist klar für Kanten, die ganz außerhalb von oder ganz innerhalb von verlaufen. Bei und besitzt bei dieser Knoten eine von und verschiedene Farbe, und bei gibt es keine Kante.

Fall 2. Es gibt nun einen verbindenen Weg in von nach . Wenn es keinen verbindenden Weg von nach innerhalb des entsprechend definierten Untergraphen gibt, so sind wir aufgrund der Argumentation im ersten Fall fertig. Wir sind somit in der Situation, wo es einen Weg von nach in und einen Weg von nach in gibt. Wir ergänzen durch die Kanten und zu einem Zykel in , der in der ebenen Realisierung einem geschlossenen Weg entspricht (indem wir ohne Knotenwiederholungen wählen, können wir diesen geschlossenen Weg als überschneidungsfrei annehmen). Hierbei liegt einer der Punkte oder im Inneren des durch den Weg begrenzten Gebietes und der andere außerhalb davon. Dann gibt es aber eine Überschneidung der beiden Wege, und diese muss in einem Knotenpunkt vorliegen. Dies ist aber ein Widerspruch, da die Farben alle verschieden sind.


Es war ein lange offenes Problem der Graphentheorie, ob auch der Vier-Farben-Satz gilt, ob man also jeden planaren Graphen mit vier Farben zulässig färben kann. Dieser Satz wurde erst 1976 von Kenneth Appel und Wolfgang Haken bewiesen, der Beweis erforderte den Einsatz von Computern, um die vielen nötigen Fallunterscheidungen zu beherrschen. Bis heute gibt es keinen computerfreien Beweis.


Satz

Für jeden ebenen Graphen

besteht eine zulässige Färbung mit höchstens vier Farben.


<< | Kurs:Diskrete Mathematik (Osnabrück 2020) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)