5/2, Folie 1 © 2015 Prof. Steffen Lange - HDa/FbI - Graphen und Optimierung Kapitel 5: Färbungen und Cliquen Gliederung der Vorlesung 1.Grundbegriffe 2.Elementare

5/2, Folie 1 © 2015 Prof. Steffen Lange - HDa/FbI - Graphen und Optimierung

Kapitel 5: Färbungen und Cliquen Gliederung der Vorlesung

1. Grundbegriffe2. Elementare Graphalgorithmen und Anwendungen3. Kürzeste Wege4. Minimale spannende Bäume5. Färbungen und Cliquen6. Traveling Salesman Problem7. Flüsse in Netzwerken und Anwendungen8. Bipartite Graphen


Kapitel 5: Färbungen und Cliquen Gliederung des Kapitels

a) Motivationb) Grundbegriffe und Zusammenhängec) Diskussion


Kapitel 5: Färbungen und Cliquen Grundbegriffe und Zusammenhänge

Begriff Clique

• sei G = (V,E) ein (ungerichteter) Graph• sei C V

• C ist eine Clique im Graphen G, falls { u,v } E für alle u,v C mit u ≠ v gilt (d.h. der durch C induzierte Teilgraph ist vollständig)

... die Größe einer Clique C entspricht der Anzahl der Knoten von C



Zugehörige algorithmische Fragestellung

• gegeben:

• ein Graph G = (V,E)

• gesucht:

• eine maximale Clique C im Graphen G (/* d.h. |C| ist maximal */)


Kapitel 5: Färbungen und Cliquen

Begriff Clique-Cover

• sei G = (V,E) ein (ungerichteter) Graph• sei C1,C2, ..., Ck eine Zerlegung der Knotenmenge, d.h. es gilt:

• die Mengen C1,C2, ..., Ck sind paarweise disjunkt• V = C1 C2 ... Ck

• die Zerlegung C1,C2, ..., Ck ist ein Clique-Cover von G, falls jedes Ci (mit 1 ≤ i ≤ k) eine Clique in G ist

... die Größe eines Clique-Covers C1,C2, ..., Ck entspricht der Anzahl der Mengen in dieser Zerlegung von V

Grundbegriffe und Zusammenhänge



Beispiel

S1

S2

S3

S8 S4

S7 S5

S6

{ S1,S2,S6 }, { S3,S5 }, { S4,S8 }, { S7 }

ein minimales Clique-Cover:

... anhand eines minimalen Clique-Covers kann man dann in unserem einführenden Beispiel eine „geeignete“ Steuerung der Verkehrsströme bestimmen





• gegeben:


• gesucht:

• ein minimales Clique-Cover C1,C2, ..., Ck für den Graphen G (d.h. k ist minimal)




naheliegende algorithmische Idee

1) setze i = 12) bestimme eine maximale Clique C im Graphen G = (V,E), gib

Ci = C aus und gehe zu 3)

3) falls C ≠ V ist, so gehe wie folgt vor:

• streiche alle Knoten aus V, die in C vorkommen• streiche alle Kanten aus E, die mit einem Knoten aus C inzident

sind• setze G = (V,E), i = i +1 und gehe zu 2)



Bewertung

• es sollte klar sein, dass man mit dem vorgestellten Algorithmus immer ein Clique-Cover bestimmen kann

• Interessierende Frage:

• Kann man mit dem vorgestellten Algorithmus immer ein minimales Clique-Cover bestimmen?

... Was meinen Sie? Was ist die korrekte Antwort?



Glauben Sie nicht alles, was Sie im Netz finden ...



Beispiel

... minimales Clique-Cover, in dem die maximale Clique { 1,2,4 }vorkommt:

1 2

43 5

minimales Clique-Cover:

• { 1,3 }, { 2,5 }, { 4,6 }

6

• { 1,2,4 }, { 3 }, { 5 }, { 6 }



Anmerkungen

• im Beispiel ist der Unterschied zwischen dem minimalen Clique-Cover und dem minimalen Clique-Cover mit einer maximalen Clique genau 1

• dieser Unterschied kann beliebig groß werden ...

1 2

43 5

6

6 7

98 10

11

... Unterschied: 2 (/* 6 versus 8 */)



Begriff Färbung

• sei G = (V,E) ein (ungerichteter) Graph• sei f(.) eine Abbildung, die jedem Knoten von V eineindeutig eine

natürliche Zahl (Codierung einer Farbe) zuordnet

• f(.) ist eine Färbung des Graphen G, falls f(u) ≠ f(v) für alle { u,v } E gilt (d.h. adjazente Knoten sind unterschiedlich gefärbt)

... die Größe einer Färbung entspricht der Anzahl der verwendeten Farben (d.h. die Größe der Menge { f(u) | u V })



Beispiel

1 2

43 5

6

1 2

43 5

6

• f(1) = 1 • f(2) = 2• f(3) = f(5) = f(6) = 3• f(4) = 4

• f(1) = f(5) = 1 • f(2) = f(3) = f(6) = 2• f(4) = 3



Einfache Zusammenhänge

• sei G = (V,E) ein (ungerichteter) Graph

• sei k die Größe einer maximalen Clique in G• sei d der maximale Grad eines Knotens in G

• Dann gilt:

(1) Jede Färbung von G benötigt mindestens k viele Farben.

(2) Jede Färbung von G benötigt höchstens d+1 viele Farben.

... überlegen Sie sich selbst eine Begründung für diese Aussagen

... es können mehr als k und weniger als d+1 viele Farben sein




• gegeben:


• gesucht:

• eine minimale Färbung für den Graphen G (d.h. eine Färbung mit einer minimalen Anzahl von Farben)




Anmerkungen


• für dieses Problem ist kein effizienter Algorithmus bekannt (/* man geht davon aus, dass es keinen effizienten Algorithmus gibt */)

• den Hintergrund diskutieren wir später ausführlich

• man kennt auch keinen effizienten Algorithmus, der eine Färbung bestimmt, deren Güte garantiert ist, d.h. die bestimmte Färbung kann beliebig mehr Farben als eine minimale Färbung verwenden (/* man geht davon aus, dass es keinen effizienten Algorithmus mit einer garantierten Güte gibt */)

• es gibt aber einen sehr effizienten Algorithmus, mit dem man überhaupt eine Färbung bestimmen kann ...

... bevor wir den Algorithmus diskutieren, schauen wir uns an, was man mit ihm noch so anfangen kann



Hilfsbegriff Komplementärgraph


• sei G = (V,E) ein (ungerichteter Graph)

• der zu G gehörende Komplementärgraph GC = (VC,EC) ist wie folgt definiert:

• VC = V• EC = { { u,v } | u V, v V, { u,v } E }

... offenbar kann man den Komplementärgraph GC sehr effizient anhand von G bestimmen



Beispiel


1 2

43 5

1 2

43 5



Ein zentraler Zusammenhang

• sei G = (V,E) ein (ungerichteter) Graph• sei f(.) eine Färbung des Graphen G, die k Farben verwendet

• Dann gilt:

Man kann anhand der gegebenen Färbung effizient ein Clique-Cover des Komplementärgraphen GC bestimmen, das ebenfalls die Größe k hat.

... die Umkehrung dieser Aussage gilt übrigens auch



Beispiel


1 2

43 5

1 2

43 5

• { 1 }, { 2 }, { 3,5 }, { 4 }

zugehöriges Clique-Cover:



Beispiel


1 2

43 5

1 2

43 5

• { 1,5 }, { 2,3 }, { 4 }

zugehöriges Clique-Cover:



Beweisidee


• sei G = (V,E) ein (ungerichteter) Graph• sei GC = (VC,EC) der Komplementärgraph• sei f(.) eine Färbung des Graphen G, die die Farben 1, 2, ..., k verwendet

• für alle i mit 1 ≤ i ≤ k setze: Ci = { u V | f(u) = i }

• da f(.) eine Färbung von G mit k Farben ist, ist C1, C2, ..., Ck eine Zerlegung von VC in k Mengen

• offenbar gilt für alle Knoten u,v VC und alle i mit 1 ≤ i ≤ k:

• u,v Ci gdw. f(u) = f(v) gdw. { u,v } E• also gilt: u,v Ci gdw. { u,v } EC

• also ist C1, C2, ..., Ck ein Clique-Cover des Komplementärgraphen GC



Konsequenzen

• jeder Algorithmus, mit dem man eine minimale Färbung für einem gegebenen Graphen G bestimmen kann, kann man verwenden, um ein minimales Clique-Cover in G zu bestimmen (/* der Overhead an Rechenzeiten ist nicht bemerkenswert groß */)

• zugrunde liegende Idee:

• bestimme den Komplementärgraphen GC

• bestimme eine minimale Färbung f(.) von GC

• bestimme das zu f(.) gehörende Clique-Cover im Komplementärgraphen von GC, d.h. im gegebenen Graphen G

... Hintergrund: der Komplementärgraph des Komplementärgraphen GC eines Graphen G ist wieder der Graph G



Konsequenzen (cont.)

• man kennt keine effizienten Algorithmen, um ein minimales Clique-Cover zu bestimmen (man vermutet, dass ...)

• man kennt auch keinen effizienten Algorithmus, der ein Clique-Cover bestimmt, dessen Güte garantiert ist, d.h. das bestimmte Clique-Cover kann beliebig mehr Cliquen als in ein minimales Clique-Cover besitzen (man vermutet, dass ...)

... Hintergrund: die vorgeführte „Problemreduktion“ ist effizient möglich (d.h. anhand von G den Komplementärgraphen GC und anhand derbestimmten Färbung das zugehörige Clique-Cover zu bestimmen)



Algorithmus zum Bestimmen einer Färbung

• bestimme eine Anordnung v1,v2, ...,vn der Knoten in V

• setze f(v1) = 1 • for i = 2 to n:

• setze z = max { f(vj) | j < i, { vi,vj } E }

• setze f(vi) = z+1

... zugrunde liegende Vereinbarung: max = 0

• sei G = (V,E) ein (ungerichteter) Graph mit |V| = n



Beispiel

... die folgende nicht optimale Färbung wird gefunden, wenn in 1) die Knoten in der Reihenfolge 1,4,2,5,3 angeordnet werden:

1 2

43 5

• f(v1) = f(1) = 1• f(v2) = f(4) = 2• f(v3) = f(2) = 3• f(v4) = f(5) = 4• f(v5) = f(3) = 2



Beispiel

... die folgende optimale Färbung wird gefunden, wenn in 1) die Knoten lexikographisch angeordnet werden:

1 2

43 5

• f(v1) = f(1) = 1• f(v2) = f(2) = 2• f(v3) = f(3) = 2• f(v4) = f(4) = 3• f(v5) = f(5) = 3



Anmerkungen

• der vorgestellte Algorithmus liefert nicht immer die minimale Färbung

• das ist nicht verwunderlich, da er in der Zeit O(n+m) eine Färbung bestimmt

• es gibt aber jeweils eine Anordnung der Knoten, so dass der vorgestellte Algorithmus eine minimale Färbung liefert

... finden Sie selbst eine Begründung



Anmerkungen (cont.)

• der vorgestellte Algorithmus kann beliebig schlechte Färbungen liefern, wie das folgende Beispiel zeigt (/* allgemein gilt: Anzahl der Knoten versus 2 *)

1 2

43

5 6



Ergänzungen

• es gibt einige Varianten des vorgestellten Algorithmus, die ebenfalls effizient sind und in der Regel bessere Färbungen liefern, wobei wiederum gilt:

• die Güte der von diesen Algorithmen bestimmten Färbungen ist nicht garantiert, d.h. die bestimmte Färbung kann beliebig mehr Farben als eine minimale Färbung verwenden

... diese Varianten des vorgestellten Algorithmus benutzen einfach zu überprüfende Kriterien, um eine „geeignete“ Anordnung der Knoten zu finden



Der Färbungsalgorithmus von Johnson (Grundidee)

• die Farben 1, 2, ... werden nacheinander verwendet

• die Verwendung einer Farbe geschieht in zwei Schritten:

1) streiche aus G alle gerade gefärbten Knoten und alle mit diesen Knoten inzidenten Kanten (/* falls G leer ist, höre auf */)

2) setze G‘ = G und färbe in G‘ ausgewählte Knoten wie folgt:

a) färbe den Knoten u mit dem minimalen Grad in G‘b) streiche aus G‘ den Knoten u und alle mit u adjazenten Knotenc) streiche aus G‘ alle Kanten, mit denen die in b) gestrichenen

Knoten inzident sindd) falls G‘ nicht leer ist, gehe zu a); sonst gehe zu 1) (/* wobei die

nächste Farbe verwendet wird */)



Beispiel

... wir betrachten den folgenden Graphen G als Eingabe

1 2

43

5 6



Beispiel

1 2

43

5 6

3

5 5

... beim Färben mit Farbe 1 werden folgende Graphen G‘ betrachtet



Beispiel

2

4

6

4

6 6

... beim Färben mit Farbe 2 werden folgende Graphen G‘ betrachtet



Beispiel

... Ergebnis der Anwendung des Algorithmus von Johnson

1 2

43

5 6



Bezeichnungen

• sei G = (V,E) ein (ungerichteter) Graph• sei V‘ V eine Teilmenge der Knotenmenge von V

• dann bezeichnen wir mit G|V‘ den wie folgt definierten Teilgraphen von G:

• G|V‘ = (V‘,E‘), wobei E‘ = { {u,v} E | u,v V‘ }

... G|V‘ enthält nur die Kanten von G, die mit Knoten in V‘ adjazent sind



Algorithmus von Johnson (/* Details */)

1) bestimme eine Anordnung v1,v2, ...,vn der Knoten in V und setze i = 1

2) falls V ≠ gilt

a) setze V‘ = Vb) falls V‘ ≠ gilt

• bestimme das minimale j ≤ n, so dass vj ein Knoten mit

einem minimalen Grad im Graphen G|V‘ ist

• setze f(vj) = i und streiche vj aus V

• streiche vj und alle mit vj adjazenten Knoten aus V‘ und

gehe zu b)

c) setze i = i +1 und gehe zu 2)

• sei G = (V,E) ein (ungerichteter) Graph mit |V| = n



Anmerkungen

• der Algorithmus von Johnson hat folgende Eigenschaften:

• er liefert immer eine Färbung• er ist effizient• er liefert in der Regel „bessere“ Färbungen als der zuvor vorgestellte

Algorithmus

... die bestimmte Färbung kann wiederum beliebig mehr Farben als eine minimale Färbung verwenden (siehe nächste Folie)



Anmerkungen (cont.)

• der Algorithmus von Johnson kann beliebig schlechte Färbungen liefern, wie das folgende Beispiel zeigt (/* allgemein gilt: Logarithmus der Anzahl der Knoten plus 1 versus 2 *)

4

2

1

3

4

2

1

3

5

6

7

8

4

2

1

3

5

6

7

8

9

10

11

12

13

14

15

16

...die in 1) verwendete Anordnung der Knoten benutzt den Knoten 1 als letzten Knoten, den Knoten 2 als vorletzten, ...

Documents

5/2, Folie 1 © 2015 Prof. Steffen Lange - HDa/FbI - Graphen und Optimierung Kapitel 5: Färbungen und Cliquen Gliederung der Vorlesung 1.Grundbegriffe 2.Elementare