Transcript
Neue Linearzeitalgorithmen für die Kantenfärbung von planaren Graphen Richard Cole, Lukasz Kowalik 1 Einführung
Problemstellung: Beim Problem der Kantenfärbung ist ein ungerichteter Graph gegeben und man versucht die Kanten so zu färben, dass Kanten mit einem gemeinsamen Endpunkt verschieden gefärbt sind. Setze ∆ := maximaler Knotengrad( = Anzahl der Nachbarn) Trivialerweise benötigt man mindestens ∆ Farben, um einen beliebigen Graphen zu färben. Vizing zeigte, dass ∆ +1 Farben reichen, um einen Graphen zu färben. Aber , falls ∆ < 7 ist, ist es im Allgemeinen NP-vollständig zu entscheiden, ob ein Graph ∆ oder ∆ +1-färbbar ist. Man versucht für spezielle Graphen effiziente Algorithmen zu finden. Für planare Graphen gilt: Falls ∆ ≥ 7 ist, so ist der Graph ∆ -färbbar. Falls ∆ ∈ {2,3,4,5} ist, so ist der Graph ∆ +1färbbar aber nicht unbedingt ∆ -färbbar. Der Fall ∆ =6 ist offen. Ergebnisse der Untersuchung von Cole und Kowalik: - Linearzeitalgorithmus für Kantenfärbung planarer Graphen, der max{ ∆ ,9} Farben benötigt.(Optimal für Graphen mit ∆ >=9) - Für ∆ = 4,5,6 werden Linearzeitalgorithmen gezeigt, die ∆ +2 Farben benötigen. Der Ansatz, das Problem zu lösen, besteht aus 2 Ideen: 1. Idee: Reduktionen Man bestimmt eine Menge von Konfigurationen. Das sind Teilgraphen konstanter Größe. Man zeigt, dass diese Konfigurationen reduzibel sind. Dazu entfernt man eine geeignete Kante einer Konfiguration F. Der reduzierte Graph wird dann rekursiv gefärbt. Nun versucht man die entfernte Kante wieder einzufügen und zu färben, wobei eventuell einige Kanten von F umgefärbt werden müssen. 2. Idee: Discharging Man zeigt, dass die Menge von Konfigurationen genügt. Dazu wird jedem Knoten und jeder Fläche eine charge zugeordnet, so dass die Gesamtsumme der charges negativ ist. Angenommen nun, es gibt keine Konfigurationen, dann kann man die charges so umverteilen, dass jeder Knoten und jede Fläche eine nicht negative charge erhält. Das ist ein Widerspruch. Also ist doch eine der Konfigurationen vorhanden.
2 Ein einfacher Linearzeitalgorithmus, der planare Graphen färbt mit max{ ∆ ,12} Farben: Definiere das Gewicht einer Kante e=uv durch: w(e):=deg(u)+deg(v).Wir benötigen folgendes Lemma: Theorem 2.2 Sei G ein einfacher, planarer Graph mit maximalem Grad ∆ , so dass G keine Knoten vom Grad 0 oder 1 enthält, jeder Knoten vom Grad 2 ist adjazent zu 2 Knoten vom Grad ∆ , und jeder Knoten vom Grad ∆ ist adjazent zu höchstens 1 Knoten vom Grad 2. Dann enthält G eine Kante vom Gewicht höchstens 13. Sei D:=max{ ∆ ,12} und wir möchten den Graphen G mit höchstens D Farben färben. Wenn unser Algorithmus eine Kante findet vom Gewicht höchstens D+1, so wird diese Kante entfernt und der reduzierte Graph wird rekursiv gefärbt. Da das Gewicht der Kante höchstens D+1 ist, sind höchstens D-1 Kanten adjazent und daher ist eine Farbe frei verfügbar. Füge die entfernte Kante wieder hinzu und färbe sie mit der freien Farbe. Definiere nun folgende Kanten vom Gewicht höchstens D+1 als reduzible Kanten: - Kanten vom Gewicht höchstens 13. - Kanten, die mit einem 1-Knoten inzidieren. - Kanten, die mit einem 2-Knoten und einem Knoten vom Grad höchstens ∆ -1 inzidieren. Zu zeigen bleibt nun, wie man färbt, wenn keine reduziblen Kanten vorhanden sind. Dann folgt aus Theorem 2.2, dass der Graph G einen ∆ -Knoten v enthält mit 2 adjazenten 2-Knoten.Bezeichne diese Knoten mit x und y. Bezeichne die anderen Nachbarn von x und y mit u und w. Da der Graph keine reduzible Kante enthält, gilt deg(u)=deg(w)= ∆ . Dann unterscheide 2 Fälle: u = w und u ≠ w. Im 1.Fall ist uxvy ein Kreis der Länge 4 mit Knotengraden ∆ ,2, ∆ ,2. Diesen Teilgraph bezeichnen wir mit Konfiguration A. Im 2.Fall ist uxvyw ein 4-Pfad mit Knotengraden ∆ ,2, ∆ ,2, ∆ . Diesen Teilgraph bezeichnen wir mit Konfiguration B. Wie wird bei Konfiguration A vorgegangen? Zunächst wird die Kante xv entfernt und der reduzierte Graph rekursiv gefärbt. Sei a die Farbe von ux .Falls a die für v freie Farbe ist, dann werden die Farben von ux und uy getauscht und xv mit a gefärbt. Andernfalls wird xv einfach mit der für v freien Farbe gefärbt. Man sagt: „ Die Konfiguration A ist reduzibel.“ Wie wird bei Konfiguration B vorgegangen? 1.Fall: Der Graph G enthält weder uv noch vw. Dann betrachte einen neuen Graphen G´ durch Ersetzen der Pfade uxv und vyw durch die Kanten uv bzw. vw. Nun färbe G´ .Seien a und b die Farben von uv und vw . Der ursprüngliche Graph G wird dann gefärbt, indem man ux und vy mit Farbe a färbt und xv und yw mit Farbe b. Die restlichen Farben bleiben wie die in G´.
2.Fall: Der Graph G enthält uv.(G enthält vw analog.) Dann entferne vy und färbe den reduzierten Graph rekursiv. Der ursprüngliche Graph G wird dann folgendermaßen gefärbt: Sei a die Farbe von yw. Man kann annehmen, dass a eine für v freie Farbe ist, denn andernfalls färbe vy mit der für v freien Farbe ungleich a. 2.Fall (i) ux ist nicht mit a gefärbt. Dann erhält vy die Farbe von xv und xv wird mit a gefärbt. 2.Fall (ii) ux ist mit a gefärbt. Dann erhält vy die Farbe von uv und die Farben von uv und ux werden getauscht. Also ist auch die Konfiguration B reduzibel. Diese Einsichten führen auf folgenden Algorithmus: Alle aktuell reduziblen Kanten werden in einer Schlange QE gespeichert. Alle aktuellen Konfigurationen A in einer Schlange QA und alle aktuellen Konfigurationen B in einer Schlange QB. Schritt 1 (i) Entferne eine reduzible Kante von QE, falls vorhanden, und entferne sie vom Graph G. (ii) Andernfalls entferne eine Konfiguration A von QA, falls vorhanden. Entferne die entsprechende Kante xv von G. (iii) Andernfalls entferne eine Konfiguration B von QB. (a) Prüfe, ob die entsprechenden Knoten u,v bzw. v,w adjazent sind. (b) In Abhängigkeit vom Adjazenztest , ersetze die Pfade uxv und vyw durch uv und vw, oder entferne vx oder vy.(siehe oben) Schritt 2
Aktualisiere QE; QA und QB.
Schritt 3
Der rekursive Aufruf.
Schritt 4
Die Kanten oder Pfade, die in Schritt 1 entfernt wurden, werden nun wieder eingefügt, was konstante Zeit kostet. Die wieder eingefügten Kanten werden gefärbt , wobei möglicherweise einige Kanten von Konfiguration A oder B umgefärbt werden müssen. Das wurde oben beschrieben.
Um die lineare Laufzeit des Algorithmus zu beweisen, braucht man die Planarität des Graphen.
3 Allgemeiner Ansatz Um einen Algorithmus zu finden, der mit D Farben färbt, muss man -
eine Menge von Konfigurationen bestimmen. zeigen, dass die Konfigurationen D-reduzibel sind. zeigen, dass jeder planare Graph eine Konfiguration enthält.
4 Färbung von Graphen mit ∆ = 4,5,6 Man geht nach dem allgemeinen Ansatz aus Kapitel 3 vor. Es wird eine Menge von Konfigurationen bestimmt und die D-Reduzibilität gezeigt. Ich möchte auf den 3.Punkt eingehen: „Zeigen, dass jeder planare Graph eine Konfiguration enthält.“, d.h. speziell für ∆ = 5 mit D = 7 Farben. Das wird mit Hilfe der 2. Idee aus der Einführung, dem Discharging gezeigt. Betrachte folgende Konfigurationen:(Die Labels bezeichnen obere Schranken der Knotengrade.)
Vorher haben Cole und Kowalik gezeigt, dass diese Konfigurationen 7-reduzibel sind. Lemma: Jeder planare Graph G mit ∆ = 5 enthält eine Kante uv vom Gewicht höchstens 8 oder eine der 2 obigen Konfigurationen (C2), oder (P) für D = 7. Beweis: Wir benutzen die Discharging-Technik. Jeder Knoten v von G erhält eine charge von deg(v)-4 Einheiten und jede Fläche q von G vom Umfang | q | erhält eine charge von | q |-4 Einheiten. Bezeichne mit n, m und f die Anzahl der Knoten, Kanten und Flächen und bezeichne mit V und F die Mengen der Knoten bzw. Flächen. Da der Graph G planar ist, gilt nach der Eulerformel: n+f=m+2.Weiter gilt nach dem Handschlaglemma: ∑v∈V deg(v) = 2m. Somit folgt für die Gesamtsumme der charges:
∑
v∈V
(deg(v) − 4) + ∑q∈F (| q | −4) = 2m – 4n + 2m – 4f = -8 < 0
Angenommen nun, der Graph G enthält keine Kante vom Gewicht höchstens 8 und keine der Konfigurationen (C2) oder (P) , dann verteilen wir die charges um. Jeder Knoten vom Grad 5 sendet ein Drittel einer charge-Einheit zu jedem inzidenten Dreieck. Wir können annehmen, dass es keine Dreiecke gibt mit einem Knoten vom Grad höchstens 4, denn ein solches wäre eine Konfiguration (C2).Also haben alle Dreiecke nach dieser Umverteilung eine nicht negative charge .Die anderen Flächen ändern ihre charge nicht, die nicht negativ sind. Offensichtlich gibt es keine Knoten, deren Grad kleiner als 4 wäre. Denn solch ein Knoten wäre ein Endpunkt einer Kante vom Gewicht höchstens 8. Knoten vom Grad 4 ändern ihre charge nicht, welche 0 ist. Da Konfiguration (P) nach der Annahme nicht im Graph G vorkommt, inzidiert jeder Knoten vom Grad 5 mit höchstens 2 Dreiecken. So behält ein Knoten vom Grad 5 mindestens ein Drittel einer charge-Einheit. Daher ist die Gesamtsumme der charges nicht negativ. Das ist ein Widerspruch. Mit diesen Techniken wird im Weiteren der Beweis geführt, dass es einen Linearzeitalgorithmus für planare Graphen gibt, der mit max { ∆ ,9} Farben auskommt, um den Graphen zu färben.
