Färben der Knoten Färben der Knoten von Graphenvon Graphen

Speziell: 4-FarbenproblemSpeziell: 4-Farbenproblem

GliederungGliederungDefinition Knotenfärbung und 4-FarbensatzDefinition Knotenfärbung und 4-Farbensatz

Historie des 4-FarbenproblemsHistorie des 4-Farbenproblems UrsprungUrsprung BeweisfindungBeweisfindung

LösungsstrategienLösungsstrategien Erschöpfende SucheErschöpfende Suche BacktrackingBacktracking mögliche Implementierungmögliche Implementierung

KomplexitätKomplexitätAnwendungsbeispieleAnwendungsbeispieleZusammenfassungZusammenfassungLiteraturhinweiseLiteraturhinweise

DefinitionDefinitionist G(V,E) ein ungerichteter Graph ohne Mehrfachkanten ist G(V,E) ein ungerichteter Graph ohne Mehrfachkanten und und eine Abbildung von V nach N, so nennt man eine Abbildung von V nach N, so nennt man eine eine Knotenfärbung von GKnotenfärbung von GFärbung ist gültig/zulässig, falls für 2 beliebige benach-Färbung ist gültig/zulässig, falls für 2 beliebige benach-barte Knoten gilt:barte Knoten gilt:

(v(v11) ) (v(v22))

G ist k-knotenfärbbar, falls es eine gültige Färbung gibt, G ist k-knotenfärbbar, falls es eine gültige Färbung gibt, so dass:so dass:

v v V : V : (v) < k(v) < k

für das kleinste k für das G k-knotenfärbbar ist, ist k die für das kleinste k für das G k-knotenfärbbar ist, ist k die chromatische zahl chromatische zahl אא(G)(G)4-Farben-Satz:4-Farben-Satz: für einen planaren Graphen G ist die für einen planaren Graphen G ist die chromatische Zahlchromatische Zahl

4(G) = 4 = (G)אא

HistorieHistorie

1852 aufgestellte Vermutung durch Francis Guthrie beim 1852 aufgestellte Vermutung durch Francis Guthrie beim Färben der Karte der Ländereien von England:Färben der Karte der Ländereien von England:

4 Farben genügen um die Länder einer Karte so zu färben, dass 4 Farben genügen um die Länder einer Karte so zu färben, dass alle benachbarten Länder unterschiedliche Farben tragenalle benachbarten Länder unterschiedliche Farben tragen

Veröffentlichung des Problems durch Brief des Veröffentlichung des Problems durch Brief des Mathematik-Professors Mathematik-Professors De MorganDe Morgan an an HamiltonHamilton

UrsprunUrsprungg

HistorieHistorie

Beweise durch Beweise durch Kempe (1878)Kempe (1878) und und TaitTait (1880) wurden (1880) wurden 1890 bzw. 1891 widerlegt1890 bzw. 1891 widerlegt1890 Formulierung des 5-Farben-Satzes durch 1890 Formulierung des 5-Farben-Satzes durch HeawoodHeawood

→→ Existenz einer oberen Schranke bewiesenExistenz einer oberen Schranke bewiesen

60-er und 70-er Jahren Verfahren von 60-er und 70-er Jahren Verfahren von HeeschHeesch zum zum Suchen eines Beweises per Computer - führte 1977 zum Suchen eines Beweises per Computer - führte 1977 zum Beweis durch Beweis durch Ken AppelKen Appel und und Wolfgang HakenWolfgang Haken

Beweis reduziert die problematischen Fälle von unendlich auf Beweis reduziert die problematischen Fälle von unendlich auf 1.936, später weniger, welche vom Computer geprüft wurden1.936, später weniger, welche vom Computer geprüft wurden

2004 - Entwicklung eines formalen Beweises mittels 2004 - Entwicklung eines formalen Beweises mittels Beweis-Assistenten COQ durch Beweis-Assistenten COQ durch WernerWerner und und GonthierGonthier

BeweisfinduBeweisfindungng

LösungsstrategienLösungsstrategien

Knoten werden nacheinander nummeriertKnoten werden nacheinander nummeriertZählmethode Tachostand:Zählmethode Tachostand:

Anzahl der Stellen = Anzahl der Knoten im GraphAnzahl der Stellen = Anzahl der Knoten im Graph Wert = Farbe(0,1,2,3) des KnotenWert = Farbe(0,1,2,3) des Knoten

jeder Färbungszustand wird unmittelbar auf Gültigkeit jeder Färbungszustand wird unmittelbar auf Gültigkeit geprüftgeprüft

Erschöpfende Erschöpfende SucheSuche

Erschöpfende SucheErschöpfende Suche

1 2 3 4 5 6 7 81 2 3 4 5 6 7 8

Erschöpfende SucheErschöpfende Suche

1 2 3 4 5 6 7 81 2 3 4 5 6 7 8

Erschöpfende SucheErschöpfende Suche

1 2 3 4 5 6 7 81 2 3 4 5 6 7 8

Erschöpfende SucheErschöpfende Suche

1 2 3 4 5 6 7 81 2 3 4 5 6 7 8

Erschöpfende SucheErschöpfende Suche

1 2 3 4 5 6 7 81 2 3 4 5 6 7 8

Erschöpfende SucheErschöpfende Suche

1 2 3 4 5 6 7 81 2 3 4 5 6 7 8

Erschöpfende SucheErschöpfende Suche

1 2 3 4 5 6 7 81 2 3 4 5 6 7 8

Erschöpfende SucheErschöpfende Suche

im ungünstigsten Fall müssen fast alle Kombinationen im ungünstigsten Fall müssen fast alle Kombinationen durchprobiert werdendurchprobiert werdenAlgorithmus zählt weiter obwohl klar ist, dass einige Algorithmus zählt weiter obwohl klar ist, dass einige Kombinationen übersprungen werden könnenKombinationen übersprungen werden können

Nachteil: sehr hoher ZeitaufwandNachteil: sehr hoher Zeitaufwand

BacktrackingBacktrackingKnoten werden nummeriertKnoten werden nummeriertein Land färben und dann versuchen das nächste zu ein Land färben und dann versuchen das nächste zu färben, so dass folgende Bedingungen erfüllt sind:färben, so dass folgende Bedingungen erfüllt sind:

die benachbarten bereits gefärbten Länder haben die benachbarten bereits gefärbten Länder haben unterschiedliche Farbenunterschiedliche Farben

keines der benachbarten noch ungefärbten Länder wird keines der benachbarten noch ungefärbten Länder wird unfärbbarunfärbbar

Bedingungen können erfüllt sein, aber dennoch zu keiner Bedingungen können erfüllt sein, aber dennoch zu keiner Lösung führen (Sackgasse)Lösung führen (Sackgasse)Rückverfolgung des Pfades und setzen der nächst-Rückverfolgung des Pfades und setzen der nächst-möglichen Farbe – rekursiver Aufrufmöglichen Farbe – rekursiver Aufruf

BacktrackingBacktracking

BacktrackingBacktracking

BacktrackingBacktracking

BacktrackingBacktracking

BacktrackingBacktracking

BacktrackingBacktracking

BacktrackingBacktracking

BacktrackingBacktracking

Vorteil: wesentlich effizienter als erschöpfende SucheVorteil: wesentlich effizienter als erschöpfende Suche

Nachteil: abhängig von der Nummerierung, d.h. bei Nachteil: abhängig von der Nummerierung, d.h. bei ungünstiger Nummerierung ist der Aufwand ebenfallsungünstiger Nummerierung ist der Aufwand ebenfallsenorm hochenorm hoch

ImplementierungImplementierung

Länder sind Knoten in einem GraphenLänder sind Knoten in einem GraphenKnoten werden mit Kante verbunden, falls Knoten werden mit Kante verbunden, falls korrespondierende Länder benachbart sindkorrespondierende Länder benachbart sindKnoten sind Container, die neben den Referenzen der Knoten sind Container, die neben den Referenzen der Nachbarknoten ein Array der Länge 4 enthält:Nachbarknoten ein Array der Länge 4 enthält:

Wert 1 an der Stelle i, signalisiert die Färbung des Knotens in Wert 1 an der Stelle i, signalisiert die Färbung des Knotens in der Farbe ider Farbe i

Wert -1 signalisiert, dass die Knoten mit i gefärbt werden kannWert -1 signalisiert, dass die Knoten mit i gefärbt werden kann 0 signalisiert, dass der Knoten nicht mit i gefärbt werden kann0 signalisiert, dass der Knoten nicht mit i gefärbt werden kann

Realisierung der Pfadrückverfolgung durch RekursionRealisierung der Pfadrückverfolgung durch Rekursion

KomplexitätKomplexitätFällt in Klasse NP-schwerFällt in Klasse NP-schwerExponentieller Aufwand:Exponentieller Aufwand:

Anzahl der Kombinationen steigt exponentiellAnzahl der Kombinationen steigt exponentiell Anzahl der möglichen Sackgassen steigt ebenfalls exponentiell,Anzahl der möglichen Sackgassen steigt ebenfalls exponentiell,

allerdings abhängig von der Nummerierung, daher ist allerdings abhängig von der Nummerierung, daher ist Backtracking oftmals deutlich schnellerBacktracking oftmals deutlich schneller

Gibt wahrscheinlich keinen effizienten AlgorithmusGibt wahrscheinlich keinen effizienten Algorithmus

AnwendungenAnwendungenStundenplanproblemStundenplanproblem

Veranstaltungen = KnotenVeranstaltungen = Knoten Veranst. die nicht gleichzeitig ablaufen können sind verbundenVeranst. die nicht gleichzeitig ablaufen können sind verbunden Anzahl der Farben = Anzahl der verschiedenen ZeitfensterAnzahl der Farben = Anzahl der verschiedenen Zeitfenster

Registerzuweisungs-ProblemeRegisterzuweisungs-ProblemeBandbreitenzuweisungs-ProblemeBandbreitenzuweisungs-ProblemeSuche nach Wegen durch ein LabyrinthSuche nach Wegen durch ein Labyrinth

ZusammenfassungZusammenfassung4-Farben-Satz konnte lange Zeit nicht korrekt bewiesen 4-Farben-Satz konnte lange Zeit nicht korrekt bewiesen werdenwerdenerstes Problem das mittels Computer bewiesen wurdeerstes Problem das mittels Computer bewiesen wurdees gibt keinen zuverlässig effizienten Lösungs-es gibt keinen zuverlässig effizienten Lösungs-AlgorithmusAlgorithmusviele mathematische Probleme lassen sich als viele mathematische Probleme lassen sich als Knotenfärbe-Problem formulierenKnotenfärbe-Problem formulierenAlgorithmen lassen sich sehr einfach implementierenAlgorithmen lassen sich sehr einfach implementieren

LiteraturhinweiseLiteraturhinweiseReinhard Diestel: Reinhard Diestel: GraphentheorieGraphentheorie. Springer-Verlag, . Springer-Verlag, Heidelberg, Deutschland, 2000. ISBN-3-540-67656-2Heidelberg, Deutschland, 2000. ISBN-3-540-67656-2

http://http://www.math.uni-hamburg.dewww.math.uni-hamburg.de//homehome//diesteldiestel//booksbooks//graphentheoriegraphentheorie//

Anuj Mehrotra, Michael A. Trick: Anuj Mehrotra, Michael A. Trick: A column generation A column generation approach for graph coloringapproach for graph coloring. INFORMS Journal on . INFORMS Journal on Computing Vol. 8, No. 4 (1996), Seiten 344-354Computing Vol. 8, No. 4 (1996), Seiten 344-354

http://http://mat.gsia.cmu.edumat.gsia.cmu.edu//tricktrick//color.pscolor.ps

Alessandro Tomazic: Alessandro Tomazic: Graphenfärbung mit Hilfe linearer Graphenfärbung mit Hilfe linearer ProgrammierungProgrammierung, Diplomarbeit, Universität Augsburg, , Diplomarbeit, Universität Augsburg, Deutschland, 2005Deutschland, 2005

http://http://de.geocities.comde.geocities.com/omarsharif_2000//omarsharif_2000/Diplomarbeit.pdfDiplomarbeit.pdf