Proseminar Grundlagen der Färbbarkeitstheorie

Proseminar Grundlagen der Färbbarkeitstheorie
1. Grundbegriffe:
Eine Eckenfärbung eines Graphen G=(V , E) ist eine Abbildung c :V ⟶ S mit
c ( v ) ≠ c ( w) für je zwei benachbarte Ecken v , w . Die Elemente der Menge S
nennt man die zur Verfügung stehenden Farben. Das kleinste k ∈ N , für das eine
Eckenfärbung c : V ⟶ {1, … , k } existiert, nennt man die (ecken-)chromatische
Zahl. Man bezeichnet sie mit χ ( G ) . Einen Graphen G mit
man k-chromatisch. Ist χ ( G ) ≤ k , so heißt G k-färbbar.
Eine Kantenfärbung von
χ ( G )=k
nennt
G=(V , E) ist eine Abbildung c : E ⟶ S mit c ( e ) ≠ c (f )
e , f . Das kleinste k ∈ N , für das eine Kantenfärbung
für benachbarte Kanten
c : E ⟶ {1, … , k } existiert, nennt man die kanten-chromatische Zahl oder den
chromatischen Index von
G . Man bezeichnet dieses
k
mit
χ ' (G)
2. Greedy-Algorithmus:
Bei komplizierteren Graphen ist es oft nicht sehr einfach eine Färbung mit möglichst
kleiner chromatischer Zahl zu finden. Hierzu gibt es aber verschiedene Algorithmen.
Einer davon ist der Greedy-Algorithmus. Hier färbt man ausgehend von einer festen
v1 , … , vn
v
Eckenaufzählung
von G die Ecken i nacheinander jeweils mit der
kleinstmöglichen Farbe c ( vi )∈ N , also mit der kleinsten Farbe, die kein Nachbar
vj
von
vi
mit
j <i
bereits trägt.
3. Fünffarbensatz
Jeder ebene Graph ist 5-färbbar.
Beweis:
Für einen Graphen mit weniger als sechs Ecken ist die Aussage klar. Es sei
ebener Graph mit n ≥3 Ecken und m Kanten.
G
ein
Induktionsannahme: jeder ebene Graph mit weniger als n Ecken ist 5-färbbar.
Wir wissen bereits, dass:
d ( G )=2 m/n≤ 2 ( 3 n−6 ) /n<6 .
Das heißt es gibt mindestens eine Ecke einem Grad kleiner gleich fünf. Es sei
v ∈G so eine Ecke. Nach Induktionsannahme hat H ≔G−v eine Eckenfärbung
c : V ( H ) ⟶ {1, … ,5 } . Nun kann man zwei Fälle unterscheiden:
1. Fall:
in G sind mit höchstens 4 Farben gefärbt.
In diesem Fall können wir c zu einer 5-Färbung von G fortsetzen.
Die Nachbarn von
v
2. Fall:
v hat genau fünf Nachbarn und diese sind verschieden gefärbt.
In diesem Fall bleibt für v keine Farbe mehr übrig. Deshalb müssen wir den Graph
H
so umfärben, dass wir wieder im 1. Fall sind und
G
fortsetzen können.
c
zu einer 5-Färbung von
Wir betrachten jetzt eine offene Kreisscheibe D um v , die so klein ist, dass sie
nur die fünf geraden Kantensegmente von G trifft, die v enthalten. Diese
Segmente seien entsprechend ihrer Lage in D in zyklischer Ordnung als
s 1 ,… , s1
c ( v i )=i
vi
nummeriert. Ist
der Nachbar von
v
i<¿
mit s i ⊆ v v ¿ , so sei oBdA
.
v1
v3
Betrachten wir zuerst die Ecken
und
. Betrachten wir dann alle Ecken, die
v
wir von von 1 aus erreichen können, indem wir nur die Farben 1 und 3 benutzen,
dann gibt es wieder zwei Fälle.
2.1. Fall:
Es existiert kein Weg von
v1
In diesen Fall können wir von
zu
v1
v3
, der nur die Farben 1 und 3 enthält.
ausgehend alle Ecken mit Farbe 1 zu 3 und mit
v1
v3
Farbe 3 zu 1 umfärben. Dann haben
und
beide die Farbe 3 und wir
können c zu einer 5-Färbung von G fortsetzen indem wir v mit der Farbe 1
färben.
2.2. Fall: Es existiert ein Weg
enthält.
P von
v1
zu
v3
, in der nur die Farben 1 und 3
In diesem Fall würde ein Umfärben wie im letzten Fall nichts nützen, denn dann würde auch
v 3 umgefärbt und es wäre immer noch keine Farbe für
deshalb
nun die Ecken
v2
und
v4
. Wenn kein Weg von
v2
v
zu
frei. Betrachten wir
v4
existiert, der nur
die Farben 2
und 4 enthält, können wir wie im Fall 2.1. den Graph wieder umfärben. Dieses Mal
v2
nur von
ausgehend mit den Farben 2 und 4.
v2
v4
Würde ein Weg von
zu
existieren, der nur die Farben 2 und 4 enthält,
könnten wir wieder nicht umfärben. So ein Weg kann jedoch nicht existieren, denn
jeder
v 1−v 3 -Weg trennt die Ecken v 2 und v 4 bereits. Dies ist genau dann der Fall,
C ≔ v v1 P v3 v
v
v4
die Ecken 2 und
in G trennt. Hierzu
v2
v4
wiederum reicht es zu zeigen, dass
und
in verschiedenen Gebieten von
C liegen. Betrachten wir zunächst die beiden Gebiete D ' , D ' ' von D(s 1 ∪ s3 ¿ .
wenn der Kreis
s
s
x 2 ∈ D ' ∩ s2
Das eine dieser Gebiete trifft 2 , das andere 4 ; es sei etwa
und
x 4 ∈ D ' ' ∩s 4
C ∩ D ⊆s 1 ∪ s3
. Wegen
sind D' und D' ' jeweils ganz in
einem Gebiet von C enthalten. Diese Gebiete sind verschieden: sonst träfe ganz D
nur ein Gebiet von C, im Widerspruch dazu, dass v auf dem Rand der beiden
Gebiete von C liegt. Mit
x2
und
x4
liegen aber auch
v2
und
v4
in
verschiedenen Gebieten von C, wie behauptet.
v2
v4
Da also der Weg P die Ecken
und
voneinander trennt und dieser nur
v2
v4
die Farben 1 und 3 enthält kannkein Weg von
zu
der nur die Farben 2 und
4 enthält existieren.
4. Vierfarbensatz
Der stärkere Vierfarbensatz sagt sogar aus, dass jeder ebene Graph mit 4
verschiedenen Farben färbbar ist. Der Beweis vom Vierfarbensatz ist jedoch
wesentlich aufwändiger und wird deshalb hier nicht weiter ausgeführt
5. Anwendung des Vierfarbensatzes am Beispiel von Landkarten
Kann man die Länder einer beliebigen Landkarte mit vier verschiedenen Farben so
färben, dass zwei Länder die eine Grenze teilen nie dieselbe Farbe bekommen?
Die Antwort ist ja. Dieses Problem lässt sich mit der Färbbarkeitstheorie von Graphen
beschreiben. Stellt man die Länder als Ecken da und verbindet dann jeweils die Ecken
miteinander durch eine Kante, welche auf der Landkarte eine Grenze teilen, bekommt man
einen ebenen Graphen. Die Fragestellung ist dann gleich zum Vierfarbensatz. Auf der
Deutschlandkarte könnte das zum Beispiel so aussehen:

Download Report