Zufaellige diskrete Strukturen 001

Zufa¨llige diskrete Strukturen Vorlesung von Anusch Taraz im Wintersemester 2004/2005 Zentrum f¨ ur Mathematik Technisch...

40 downloads 695 Views 796KB Size Report

This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!

Report copyright / DMCA form

DOWNLOAD PDF

Zufa¨llige diskrete Strukturen Vorlesung von Anusch Taraz im Wintersemester 2004/2005 Zentrum f¨ ur Mathematik Technische Universit¨at M¨ unchen 14. Februar 2005

Inhaltsverzeichnis 1 Graphentheorie

3

1.1

Elementare Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.2

F¨arbungen von Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

2 Zuf¨ allige Graphen

14

2.1

Eigenschaften fast aller Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

2.2

Evolution zuf¨ alliger Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

2.3

Im Phasen¨ ubergang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

2.4

Chromatische Zahl zuf¨ alliger Graphen . . . . . . . . . . . . . . . . . . . . . . . . .

26

3 Probabilistische Analyse

31

3.1

F¨arbungsalgorithmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

3.2

Das Travelling Salesman Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

3.3

Hamilton-Kreise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40

3.4

Perfekte Matchings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

3.5

Knapsack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46

4 Probabilistische Existenzbeweise

51

4.1

Einfarbige Cliquen, arithmetische Progressionen und Hyperkanten . . . . . . . . .

51

4.2

Das Lovasz Local Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

54

4.3

Graphen mit hoher chromatischer Zahl aber ohne kurze Kreise . . . . . . . . . . .

57

4.4

Listenf¨ arbungszahl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

57

4.5

Kleine Dreiecke in der Ebene: Heilbronn’s Problem . . . . . . . . . . . . . . . . . .

60

4.6

Nachtr¨ age zur Evolutionsgeschichte von Gn,p . . . . . . . . . . . . . . . . . . . . .

60

1

5 Randomisierte Algorithmen

63

5.1

Min-Cut . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

63

5.2

Fingerabdr¨ ucke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

67

5.2.1

Bitw¨ orter-Vergleiche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

67

5.2.2

Polynomvergleich . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

69

5.3

Primzahltests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

70

5.4

Markov-Ketten und Random Walks . . . . . . . . . . . . . . . . . . . . . . . . . . .

76

5.4.1

Motivation und Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . .

76

5.4.2

Grundlegende Begriffe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

77

5.4.3

Irreduzibilit¨ at . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

78

5.4.4

Periodizit¨ at . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

79

5.4.5

Konvergenzgeschwindigkeit von Markovketten – Kanonische Pfade . . . . .

80

5.4.6

Z¨ ahlen mit Markov-Ketten . . . . . . . . . . . . . . . . . . . . . . . . . . .

81

SAT-Algorithmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

85

5.5.1

2-SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

85

5.5.2

3-SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

86

5.6

Ausblick: Randomisiertes Runden (Max-Cut) . . . . . . . . . . . . . . . . . . . . .

89

5.7

Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

91

5.7.1

Bit-Fixing-Strategie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

91

5.7.2

Randomisiertes Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

91

5.5

2

1

Graphentheorie

Literaturhinweise: Informationen u ¨ ber das Material in Kapitel 1 findet sich in [4] und [5]. Die Resultate und Methoden aus Kapiteln 2 und 3 sind vielen verschiedenen Arbeiten entnommen, Einiges kann man in [1, 2] nachlesen. Fast alle Themen von Kapitel 4 sind [1] entnommen, w¨ahrend [6] die Grundlage f¨ ur Kapitel 5 bildet.

1.1

Elementare Grundlagen

Notation. Wir bezeichnen mit N := {0, 1, 2, . . . } die Menge der nat¨ urlichen Zahlen und setzen N+ := N \ {0}. F¨ ur i, j ∈ N mit i ≤ j sei [i, j] := {i, . . . , j} und [i] := [1, i]. Sei V eine Menge und k ∈ N. Dann bezeichne mit V := {W ⊆ V : |W | = k}, (1) k V k := V × · · · × V = {(v1 , . . . , vk ) : vi ∈ V },

(2)

die Menge aller k-elementigen Teilmengen von V bzw das k-fache kartesische Produkt von V . Offensichtlich gilt, dass V k |V | V = |V |k , und k = k wenn V endlich ist. Mit log bzw ln wird der Logarithmus zur Basis 2 bzw e bezeichnet.

Graphen. Ein (endlicher) Graph ist ein Tupel G = (V, E), wobei V eine endliche Menge (o.B.d.A. einfach {1, . . . , n}) und E ⊆ V2 eine Teilmenge der zweielementigen Teilmengen von V ist.1 Die Elemente v ∈ V heißen die Knoten (auch Ecken, engl. vertices oder nodes), die Elemente aus e ∈ E die Kanten (engl. edges) von G. Die Anzahl der Knoten eines Graphen G wird als die Ordnung (order) von G bezeichnet, die wir durchweg mit n := |G| := |V | notieren. Die Anzahl seiner Kanten, in Zeichen m := kGk := |E|, heißt auch die Gr¨oße (size) von G. F¨ ur eine Kante {u, v} ∈ E werden die Knoten u und v ihre Endpunkte genannt. Das Komplement (V, V2 \ E) eines Graphen notieren Sein Komplement, der Graph wir mit G. Ein Graph (V, ∅) ohne Kanten heißt auch leer oder ntrivial. Kn := (V, V2 ), heißt vollst¨ andig; bei n Knoten hat er m = 2 Kanten. Beispiel.

n Bemerkung. Offenbar gibt es 2( 2 ) viele verschiedene Graphen auf n (numerierten oder markierten, d.h. unterschiedenen) Knoten.

Viele dieser Graphen unterscheiden sich jedoch lediglich in der Numerierung ihrer Knotenmenge: Zwei Graphen G1 = (V1 , E1 ) und G2 = (V2 , E2 ) heißen isomorph, in Zeichen G1 ∼ = G2 , falls es eine Bijektion f : V1 → V2 gibt, so daß gilt: {u, v} ∈ E1 ⇔ {f (u), f (v)} ∈ E2 . Beispiel. Gerichtete Graphen unterscheiden sich von ungerichteten dadurch, daß ihre Kanten eine Orientierung (Richtung) tragen. Formal bedeutet das, daß die Kantenmenge E eine Teilmenge der geordneten Paare V × V ist, die Kante (u, w) ∈ E ist also nicht identisch mit der Kante (w, u). Beispiel. Zwei Knoten u, v ∈ V eines Graphen G = (V, E) heißen adjazent, verbunden oder benachbart, falls {u, v} ∈ E. Eine Kante e ∈ E inzidiert mit einem Knoten v ∈ V , wenn v ∈ e. Die Nachbarschaft eines Knotens v ∈ V ist die Menge Γ(v) := {u ∈ V | {u, v} ∈ E} der Nachbarn von v. Der Grad d(v) := |Γ(v)| eines Knotens v ∈ V z¨ahlt die Kanten, die in dem Graphen mit v inzidieren. (Manchmal schreibt man auch ΓG und dG , um zu betonen, um welchen Graphen 1 Es werden hier fast ausschließlich nur sogenannte einfache Graphen betrachtet, d.h. Graphen ohne Schlingen (Kanten, deren Endpunkte zusammenfallen) und ohne mehrfache (parallele) Kanten zwischen zwei Knoten.

3

es sich handelt.) Mit ∆(G) und δ(G) werden der gr¨oßte und der kleinste in G auftretende Grad bezeichnet. Ist ∆(G) = δ(G), dann spricht man von einem ∆-regul¨aren Graphen. Sei v ∈ V . Mit G − v bezeichnet man den Graphen, den man erh¨alt, wenn man v aus V und alle Kanten aus E, die mit v inzidieren, entfernt. Proposition 1.1. F¨ ur jeden Graphen G = (V, E) gilt, dass X d(v) = 2m, v∈V

und dass G eine gerade Anzahl von Knoten ungeraden Grades hat. Subgraphen. Ein Graph H = (VH , EH ) heißt (schwacher) Subgraph eines Graphen G = (VG , EG ), in Zeichen H ⊆ G, falls VH ⊆ VG und falls gilt {u, v} ∈ EH ⇒ {f (u), f (v)} ∈ EG . Ein Graph H = (VH , EH ) heißt induzierter Subgraph eines Graphen G = (VG , EG ), falls VH ⊆ VG und falls gilt {u, v} ∈ EH ⇔{f (u), f (v)} ∈ EG ; das heißt, wenn EH = V2H ∩ EG . Den von einer Knotenmenge S ⊆ V in einem Graphen G induzierten Subgraphen bezeichnen wir mit G[S]. Ein Subgraph H eines Graphen G heißt spannend, falls V (H) = V (G). Eine Knotenmenge C ⊆ V heißt Clique in einem Graphen G, falls der von C induzierte Subgraph G[C] vollst¨andig ist. Eine Knotenmenge S ⊆ V heißt unabh¨ angig oder stabil, falls keine zwei Knoten aus S benachbart sind, d.h. falls der von S in G induzierte Graph G[S] leer ist. Die Gr¨oße einer kardinalit¨atsmaximalen Clique in einem Graphen G heißt die Cliquenzahl ω(G), die Gr¨oße einer kardinalit¨atsmaximalen unabh¨angigen Knotenmenge die Stabilit¨ ats- oder Unabh¨angigkeitszahl α(G). Offensichtlich gelten: • ω(Kn ) = n und α(Kn ) = 1, • ω(G) = α(G). ¨ Ubung 1.2. Sei G ein Graph. Zeige, dass • 1 ≤ ω(G) ≤ ∆(G) + 1, •

n ∆(G)+1

≤ α(G) ≤ n.

Gleichheit gilt jeweils beispielsweise beim leeren bzw. beim vollst¨andigen Graphen. Wege, Pfade, Zusammenhang, Kreise. Ein Weg W (auch Kantenzug genannt, engl. walk) ist eine Folge v0 , v1 , . . . , vℓ von (nicht notwendig verschiedenen) Knoten vi ∈ V , 0 ≤ i ≤ ℓ, so daß f¨ ur i = 0, . . . , ℓ − 1 gilt: {vi , vi+1 } ∈ E. Seine L¨ange ist die Anzahl ℓ der Kanten, die er enth¨alt. Ein Weg W = (v0 , v1 , . . . , vℓ ), bei dem (falls ℓ ≥ 1) alle Knoten vi , 0 ≤ i ≤ ℓ, paarweise verschieden sind, heißt Pfad (engl. path). Ein Pfad auf n ∈ N Knoten wird mit Pn notiert – beachte: er hat die L¨ange n−1 . Der Knoten v0 heißt der Anfangsknoten des Pfades, vℓ ist der Endknoten; alle anderen Knoten heißen die inneren Knoten des Pfades P . Ein u − v−Pfad ist ein Pfad mit Anfangsknoten u und Endknoten v ¨ Ubung 1.3. Zeige: Jeder u − v−Weg (u 6= v) enth¨alt einen u − v−Pfad. Und: Ein k¨ urzester u − v−Weg ist ein u − v−Pfad. Wir definieren den Abstand zwischen zwei Knoten u, v wie folgt: min{ℓ(P ) : P ist u − v−Pfad} : falls es einen u − v−Pfad gibt, dist(u, v) := ∞ : sonst. G heißt zusammenh¨ angend, falls es zwischen je zwei Knoten u, v ∈ V einen u − v−Pfad gibt. Die inklusionsmaximalen zusammenh¨ angenden Subgraphen eines Graphen heißen Komponenten. Mit c(G) bezeichnet man die Anzahl der Komponenten von G. 4

Ein Pfad P = v0 , . . . , vℓ−1 in G heißt Kreis, falls {v0 , vℓ−1 } ∈ E. Der Kreis auf n ∈ N Knoten wird mit Cn notiert, offensichtlich ist C3 = K3 . Ein Graph G heißt kreisfrei, wenn er keinen Subgraphen enth¨ alt, der ein Kreis ist. B¨ aume. Ein Graph G heißt Baum, falls G zusammenh¨angend und kreisfrei ist. Ein Knoten v in einem Graphen G heißt Blatt, falls d(v) = 1. Beispiel. Lemma 1.4. Jeder Baum auf mindestens zwei Knoten hat mindestens zwei Bl¨atter. Beweis: - Beginne in einem beliebigen Startknoten v0 eines Baumes T . - Konstruiere einen Weg W = v0 , v1 , . . . , vℓ , indem in jedem Knoten vi ∈ W eine beliebige, aber bisher noch nicht abgeschrittene Kante {vi , vi+1 } gew¨ahlt wird. - Da T kreisfrei ist, trifft man nie auf einen bereits besuchten Knoten. - Da T andererseits nur endlich viele Knoten hat, bricht der Prozeß irgendwann in einem Knoten vℓ ab. Da der Weg W in vℓ nicht fortgesetzt werden kann, ist vℓ ein Blatt. - Wiederholt man dieses Verfahren vom Startknoten vℓ aus, findet man ein weiteres Blatt. 2 B¨aume lassen sich auf mannigfaltige Weise charakterisieren. Satz 1.5. F¨ ur einen Graphen G = (V, E) auf |V | = n Knoten sind ¨aquivalent: (1) G ist ein Baum; (2) G ist zusammenh¨angend und hat n − 1 viele Kanten; (3) G ist kreisfrei und hat n − 1 viele Kanten; (4) G ist (Kanten-) maximal kreisfrei; (5) G ist (Kanten-) minimal zusammenh¨angend; (6) Je zwei Knoten aus V sind durch genau einen Pfad verbunden. Beweis: (1) ⇒ (2): durch Induktion nach n = |V |. F¨ ur n = 1, 2 ist die Aussage offensichtlich. Sei G nun ein Baum auf n ≥ 3 Knoten. Nach Lemma 1.4 besitzt G ein Blatt b ∈ V . Sei e ∈ E die mit b inzidierende Kante. Dann ist auch der Graph T := G − b zusammenh¨angend und kreisfrei, also ein Baum, und hat nach Induktionsvoraussetzung mT = nT − 1 viele Kanten. Also hat G genau m = mT + 1 = nT = n − 1 viele Kanten. (2) ⇒ (3): Angenommen, es gibt einen Kreis C in G. Da G zusammenh¨angt, gibt es zu jedem der n − |C| Knoten v, die nicht auf dem Kreis liegen, einen k¨ urzesten v − C−Pfad. Sei ev die jeweils erste Kante auf dem v − C−Pfad. Dann sind alle ev , v ∈ V \ V (C), verschieden, und G hat mindestens |C| + |V \ V (C)| = n Kanten, Widerspruch. (3) ⇒ (1): Da G kreisfrei ist, ist jede Komponente von G ein Baum. Seien Hi , i = 1, . . . , c(G), die Komponenten von G mit ni Knoten und mi Kanten. Nach (2) hat G also c(G)

c(G)

m =

X i=1

mi =

X i=1

(ni − 1) = n − c(G)

(3)

viele Kanten. Nach Voraussetzung ist also c(G) = 1, d.h. G ist zusammenh¨angend. (1) ⇒ (6): In einem Baum ist jeder Weg ein Pfad, da Selbst¨ uberkreuzungen zu Kreisen f¨ uhren w¨ urden. Da G zusammenh¨ angt, gibt es also zu je zwei Knoten x und y in G einen x − y−Pfad P1 . Angenommen nun, es g¨ abe einen weiteren, von P1 verschiedenen x − y−Pfad P2 in G. Der 5

Teilweg von x bis zu einem Knoten a sei das maximale gemeinsame Anfangsst¨ uck beider Wege und der Knoten b der erste, beiden Pfaden wieder gemeinsame Knoten hinter a. Dann bildet der a − b−Teilpfad auf P1 zusammen mit dem in umgekehrter Richtung durchlaufenen a − b−Teilpfad von P2 einen Kreis in G. (6) ⇒ (5): Nach Voraussetzung ist G zusammenh¨angend. Angenommen G − e w¨are noch zusammenh¨angend f¨ ur eine Kante e = {x, y} ∈ E. Dann g¨abe es neben e noch einen weiteren x − y−Pfad in G, Widerspruch. (5) ⇒ (4): Sei G minimal zusammenh¨ angend. Angenommen, G bes¨aße einen Kreis. Dann ließe sich eine beliebige Kreiskante aus G entfernen, ohne den Zusammenhang zu zerst¨oren. Es bleibt zu zeigen, daß durch Hinzuf¨ ugen einer Kante {x, y} zwischen zwei nicht benachbarten Knoten x und y in G ein Kreis entsteht. Dies folgt daraus, daß G zusammenh¨angend ist und folglich einen x − y−Pfad enth¨ alt, den die Kante {x, y} zu einem Kreis schließt. (4) ⇒ (1): Angenommen, G w¨ are nicht zusammenh¨angend. Dann k¨onnte man zwischen zwei beliebigen Knoten aus zwei verschiedenen Komponenten von G eine Kante einf¨ ugen, ohne einen Kreis zu erzeugen. 2 Ein kreisfreier Graph heißt Wald. Jede Komponente eines Waldes ist also ein Baum. In Gleichung (3) haben wir also gezeigt: Korollar 1.6. Ein Wald W mit c(W ) Komponenten hat m = n − c(W ) viele Kanten. Ein Graph G enth¨alt einen Kreis genau dann, wenn m > n − c(G). Wir erinnern daran, daß ein Baum T ⊆ G (auf)spannend heißt, falls V (T ) = V (G). Korollar 1.7 (Kirchhoff 1847). Ein Graph G ist zusammenh¨angend genau dann, wenn er einen aufspannenden Baum T (als Subgraphen) besitzt. Beweis: ⇐ ist offensichtlich. Zu ⇒: Ist G selbst kein Baum, so enth¨alt er einen Kreis. Entferne eine Kante e aus diesem Kreis. Dann ist der verbleibende Graph G − e noch immer zusammenh¨angend. Wiederhole diese Prozedur, bis nach Satz 1.5 (5.) ein Baum T u 2 ¨ brigbleibt. Satz 1.8 (Cayley 1889). Die Anzahl der B¨aume auf n markierten Knoten betr¨agt nn−2 .

Bipartite Graphen. Ein Graph G heißt bipartit genau dann, wenn sich seine Knotenmenge so in zwei Teile U und W partitionieren l¨aßt, daß Kanten nur zwischen U und W verlaufen, oder ¨aquivalent, daß U und W stabile Mengen in G induzieren: U W E∩ = ∅ und E ∩ = ∅. 2 2 Setzt man u = |U | und w = |W | und betrachtet den Fall, wo jeder Knoten in U mit jedem Knoten in W verbunden ist (und U und W stabile Mengen sind), dann erh¨alt man den vollst¨andigen bipartiten Graphen Ku,w . Beispiel. B¨aume sind offensichtlich bipartit. Ein Kreis ist genau dann bipartit, wenn er eine gerade Anzahl von Knoten besitzt. Dar¨ uber hinaus gilt jedoch auch: Satz 1.9 (K¨ onig 1936). Ein Graph ist bipartit genau dann, wenn er keine ungeraden Kreise enth¨alt. F¨ ur den Beweis ben¨ otigen wir die einfache Definition der Sph¨are: Sei u ∈ V ein Knoten. F¨ ur 0 ≤ i ≤ n − 1 heißt dann die Knotenmenge Si (u) := {v ∈ V : dist(u, v) = i} die i-te Sph¨are um u. Offensichtlich gilt S0 (u) = {u} und S1 (u) = Γ(u). Beweis von Satz 1.9. Die Notwendigkeit der Bedingung sahen wir bereits ein. Besitze G also keine ungeraden Kreise. Da es gen¨ ugt, nachzuweisen, daß jede Komponente von G bipartit ist, sei G o.B.d.A. zusammenh¨ angend. - W¨ahle beliebigen Knoten u ∈ V aus. F¨ ur alle v ∈ V ist die Gr¨oße dist(u, v) wohldefiniert. 6

- Definiere die Knotenmengen U0 := S0 (u) ∪ S2 (u) ∪ ... und U1 := S1 (u) ∪ S3 (u) ∪ .... ˙ 1 . Es bleibt zu zeigen, daß Ui f¨ - Da G zusammenh¨ angt, folgt V = U0 ∪U ur i ∈ {0, 1} stabil ist. - Widerspruchsannahme: a) v1 , v2 ∈ Ui f¨ ur ein i ∈ {0, 1} und b) {v1 , v2 } ∈ E. - Wegen a) sind dist(u, v1 ) und dist(u, v2 ) entweder gleich oder unterscheiden sich um mindestens 2. Wegen b) k¨ onnen sie aber h¨ochstens um 1 voneinander abweichen. Daher folgt: dist(u, v1 ) = dist(u, v2 ). - Sei v der erste gemeinsame Knoten zweier k¨ urzester v1 − u− bzw. v2 − u−Pfade. - Dann bilden die in ihnen enthaltenen Teilpfade von v1 bzw. v2 nach v gemeinsam mit der Kante {v1 , v2 } einen ungeraden Kreis, Widerspruch. Vorlesung 26.10. Korollar 1.10. Sei G ein zusammenh¨angender Graph und u ein beliebiger Knoten. Dann ist G bipartit genau dann, wenn U0 := S0 (u) ∪ S2 (u) ∪ ... und U1 := S1 (u) ∪ S3 (u) ∪ ... stabile Mengen bilden. Wir zeigen nun noch kurz, wie man die Sph¨aren eines Knotens schnell mit Hilfe einer sogenannten Breitensuche berechnet. Betrachte dazu die folgende elementare Routine, die ausgehend von einem beliebigen Startknoten s die Abst¨ ande dist(u, v) f¨ ur alle weiteren Knoten berechnet. Dazu ben¨otigen wir eine Warteschlange Q (FIFO-Speicher, engl. queue) als Datenstruktur. Abst¨ ande(G, u) (1) Q := (u) (2) besucht:= {u} (3) dist[u] := 0 (4) while Q 6= ∅ (5) v := head(Q) (6) foreach w ∈ Γ(v)\besucht (7) add(Q, w) (8) besucht:=besucht ∪{w} (9) dist[w] := dist[v]+1 Proposition 1.11. Der Algorithmus Abst¨ ande(G, u) berechnet in O(n + m) f¨ ur einen zusammenh¨angenden Graphen G die Abst¨ande von einem Knoten u zu allen weiteren Knoten. Beweis: Es sind drei Dinge zu u ufen: a) jeder Knoten erh¨alt einen Abstand, b) dieser Abstand ¨ berpr¨ ist auch wirklich der Abstand, c) die Laufzeit ist korrekt. 2 ¨ Ubung 1.12. Jeder Graph G = (V, E) enth¨alt einen (spannenden) bipartiten Subgraphen B mit kBk ≥ 21 kGk. Laundau–Notation. Wir benutzen die Symbole O und o (und ihre Verwandten) um das asymptotische Verhalten von Funktionen zu beschreiben. Definition 1.13. Es seien f, g : N → R+ zwei Funktionen. Wir schreiben f (n) = O (g(n)) , wenn es Konstanten c ∈ R+ und n0 ∈ N gibt, so daß f (n) ≤ c g(n)

∀n ≥ n0 .

Wir schreiben f (n) = Ω (g(n)) , 7

wenn es Konstanten c ∈ R+ und n0 ∈ N gibt, so daß f (n) ≥ c g(n)

∀n ≥ n0 .

Die O-Notation entspricht intuitiv einem asymptotischen ≤, die Ω-Notation einem asymptotischen ≥. Beispiel. • n = O(n2 ), 7n2 = O(n2 ), 7n2 = O(n3 ), • •

23 2 12 n

Pn

− 721n + 1001 = O(n2 ),

k=1

k = O(n2 ),

• log n = O(nα ) f¨ ur jedes α > 0, •

1 log n

= O(1),

Definition 1.14. Es seien f, g : N → R+ zwei Funktionen. Wir schreiben f (n) = Θ (g(n)) , wenn es Konstanten c1 , c2 ∈ R+ und n0 ∈ N gibt, so daß c1 g(n) ≤ f (n) ≤ c2 g(n)

∀n ≥ n0 .

Wir schreiben f (n) = o (g(n)) , wenn es f¨ ur jede Konstante c ∈ R

+

eine Konstante n0 ∈ N gibt, so daß

f (n) ≤ c g(n)

∀n ≥ n0 .

Analog dazu schreiben wir f (n) = ω (g(n)) , wenn es f¨ ur jede Konstante c ∈ R+ eine Konstante n0 ∈ N gibt, so daß f (n) ≥ c g(n)

∀n ≥ n0 ;

Die Θ-Notation entspricht intuitiv einem asymptotischen =, die o-Notation einem asymptotischen <, die ω-Notation einem asymptotischen >. Beispiel. Wir zeigen, daß 7n = o(n log n). Sei dazu eine beliebige Konstante c ∈ R+ gegeben. W¨ahle n0 ∈ N so, daß 7c ≤ log n0 . Damit gilt auch ∀n ≥ n0 , daß 7c ≤ log n, und daher 7n = c 7c n ≤ cn log n. Weitere Beispiele: • n 6= Θ(n2 ), 7n2 = Θ(n2 ), 7n2 6= Θ(n3 ), Pn 2 • k=1 k = Θ(n ),

• 7n = o(n2 ), 7n = o(n log n), 7n 6= o(n), 7n 6= o(8n), • log n = o(nα ) f¨ ur jedes α > 0, •

1 log n

= o(1).

H¨aufig ist die folgende Proposition hilfreich. 8

Proposition 1.15. a) limn→∞ b) limn→∞

f (n) g(n)

⇔

=0

f (n) g(n)

<∞

⇒

f (n) = O(g(n))

f (n) = o(g(n))

¨ Ubung 1.16. Zeige die folgenden Aussagen: • Finde ein Beispiel daf¨ ur, daß in Proposition 1.15 a) nicht ⇔“ gilt. ” f (n) g(n)

• f (n) = Θ(g(n))

⇐

• f (n) = O(g(n))

⇔

g(n) = Ω(f (n)),

• f (n) = Θ(g(n))

⇔

f (n) = O(g(n)) und f (n) = Ω(g(n)),

• f (n) = o(g(n))

⇔

f (n) = O(g(n)) und f (n) 6= Θ(g(n)),

• f (n) = ω(g(n))

⇔

g(n) = o(f (n)).

0 < limn→∞

< ∞,

Repr¨ asentationen von Graphen. Es sei G = (V, E) ein Graph. Wir wollen im Folgenden zwei M¨oglichkeiten der Repr¨ asentation und Speicherung von Graphen betrachten. (1) Adjazenzliste Feld von |V | Listen, eine f¨ ur jeden Knoten in V

F¨ ur v ∈ V enth¨ alt die Liste Adj[v] Verweise auf alle Knoten, die zu v benachbart sind.

Beispiel.

Vorteil: Kompakte Darstellung (O(n + m) Speicher) Nachteil: Test, ob {v, w} Kante ist, kostet in schlechtestem Fall O(n) Zeit (2) Adjazenzmatrix |V | × |V | Matrix A = (aij ) mit 1 , falls {i, j} ∈ E aij = 0 sonst Beispiel.

1 2 3 4 5

 1 0  1   0   0 1

2 1 0 1 1 1

3 0 1 0 1 0

4 5  0 1 1 1   1 0   0 1  1 0

Vorteil: Test, ob {v, w} Kante ist, kostet O(1) Zeit

Nachteil: Adjazenzmatrix erfordert Θ(n2 ) Speicher. F¨ ur m = const n2 ist das nat¨ urlich bestm¨ oglich, falls jedoch der Graph nicht so dicht mit Kanten besetzt ist (z.B. m = O(n)), nicht mehr optimal. Eine allgemeine wichtige Beobachtung: ein Verfahren mit Platz- oder Zeitkomplexit¨at O(m+n) ist aus den genannten Gr¨ unden einem Verfahren mit Komplexit¨at O(n2 ) immer vorzuziehen. Wir werden einige Beispiele f¨ ur Graphenklassen sehen, f¨ ur die m = O(n) gilt.

9

1.2

F¨ arbungen von Graphen

Wir haben bereits bipartite Graphen kennengelernt. Stellt man sich die Knoten der Bipartitionsklassen als mit zwei unterschiedlichen Farben gef¨arbt vor, dann zeichnet sich ein bipartiter Graph dadurch aus, daß keine Kante zwei Endpunkte gleicher Farbe hat, oder anders betrachtet, daß kein Knoten zu einem Knoten der gleichen Farbe benachbart ist. Es gibt keinen Grund, diese Sichtweise nur auf zwei Farben zu beschr¨ anken. Sei k ≥ 2 eine nat¨ urliche Zahl. Unter einer zul¨assigen k-F¨arbung der Knoten eines Graphen G = (V, E) versteht man eine Abbildung c : V → {1, . . . , k}, so daß gilt: {u, v} ∈ E ⇒ c(u) 6= c(v), d.h. benachbarte Knoten sind verschieden gef¨arbt. Wir meinen im folgenden immer zul¨assige (Knoten-)F¨arbungen, wenn wir von F¨ arbungen eines Graphen sprechen. Ein Graph heißt k-f¨arbbar, wenn er eine k-F¨ arbung besitzt. Jeder Graph ist also n-f¨arbbar, und ein Graph ist 1-f¨arbbar genau dann, wenn er leer ist. Die chromatische Zahl χ(G) eines Graphen G ist definiert als das minimale k ∈ N, so daß G k-f¨ arbbar ist. Ein Graph G heißt k-chromatisch, falls χ(G) = k. Wir haben in Satz 1.9 ein einfaches Kriterium daf¨ ur kennengelernt, ob ein Graph bipartit, also 2-f¨arbbar ist oder nicht. Mit Hilfe von Korollar 1.10 und Proposition 1.11 l¨asst sich dar¨ uberhinaus auch effizient pr¨ ufen ob ein Graph G 2-f¨ arbbar ist oder nicht. F¨ ur k > 2 gilt das aller Voraussicht nach nicht. Satz 1.17. Sei k ≥ 3 eine nat¨ urliche Zahl. Das Problem, zu einem gegebenen Graph G zu entscheiden, ob G k-f¨arbbar ist, ist NP–vollst¨andig. Beispiele und untere Schranken. Wir erinnern daran, daß die Kardinalit¨at der gr¨oßten Clique bzw. der gr¨oßten stabilen Menge in einem Graphen G mit ω(G) bzw. α(G) bezeichnet werden. Offenbar m¨ ussen die Knoten einer Clique in jeder zul¨assigen F¨arbung paarweise verschiedene Farben tragen. Es gilt also χ(Kn ) = n und χ(G) ≥ ω(G). (4) I.A. gilt hier keine Gleichheit; so haben die ungeraden Kreise beispielsweise chromatische Zahl 3. Allgemein gilt: Satz 1.18. Zu jedem k ∈ N gibt es Graphen mit Cliquenzahl 2 (sie enthalten also kein Dreieck) und chromatischer Zahl mindestens k. Der Beweis entf¨ allt – wir werden sp¨ ater (siehe Kapitel 4) eine st¨arkere Aussage kennenlernen und beweisen. arbung von G ist eine Menge von Knoten, die dieselbe Farbe tragen. Eine Farbklasse in einer F¨ Offenbar induziert jede Farbklasse einer F¨ arbung von G eine stabile Menge in G. Da jede Farbklasse Si in einer χ(G)-F¨ arbung eines Graphen G h¨ochstens α(G) viele Knoten enthalten kann, gilt Pχ(G) n = i=1 |Si | ≤ χ(G)α(G), und wir erhalten die untere Schranke Proposition 1.19.

χ(G) ≥

n , α(G)

(5)

die f¨ ur den Kn oder den Kn,n beispielsweise scharf ist. Auch diese Schranke kann im allgemeinen beliebig schlecht werden: ¨ Ubung 1.20. Konstruiere eine unendliche Familie von Graphen {Gk }k∈N , so daß χ(Gk ) = k + 1 n und α(G = 2. k) Anwendungen. F¨ arbungsprobleme treten in vielen Situationen auf, z.B. bei der Terminplanung von Examenspr¨ ufungen, die man unter der Bedingung, daß jeder Student an den Pr¨ ufungen zu allen F¨achern teilnehmen kann, die er belegt hat, auf m¨oglichst wenige Zeitintervalle verteilen m¨ochte. 10

Oder bei der Terminplanung von Ausschußsitzungen des Bundestages, die man auf m¨oglichst wenige Zeitintervalle so verteilen m¨ ochte, daß jeder Abgeordnete die Sitzungen aller Aussch¨ usse besuchen kann, denen er angeh¨ ort. Im graphentheoretischen Modell G entspricht die Knotenmenge den F¨achern (rsp. Aussch¨ ussen), und zwei Knoten sind benachbart genau dann, wenn es Studenten gibt, die beide F¨acher gleichzeitig belegt haben (bzw. Abgeordnete, die beiden Aussch¨ ussen angeh¨oren). Eine stabile Menge von F¨ achern (rsp. Aussch¨ ussen) kann dann ohne Konflikte auf denselben Termin gelegt werden, und das Problem, einen Terminplan mit minimal vielen Zeitintervallen zu finden, ist ¨aquivalent dazu, eine χ(G)-F¨ arbung in G zu konstruieren. In der Praxis sind jedoch die ben¨ otigten Ressourcen, wie Beaufsichtigungspersonal oder Raumkapazit¨aten in obigem Beispiel, beschr¨ ankt, und man m¨ochte sie m¨oglichst gleichm¨aßig auslasten. Das f¨ uhrt auf das Problem, F¨ arbungen von Graphen zu finden, in denen die Farbklassen m¨oglichst gleich groß sind. Graphf¨arbungsalgorithmen finden auch Anwendung beim Registerbelegungsproblem im Compilerbau, wo m¨ oglichst viele Variablen gleichzeitig in Registern gehalten werden sollen. ¨ Ubung 1.21. a) m(G) ≥ χ(G) . 2 b) χ(G) · χ(G) ≥ n;

c) χ(G) + χ(G) ≤ n + 1. [Hinweis: Induktion u ¨ber n] Greedy-F¨ arbung und der Satz von Brooks. Obwohl eins der meist-studierten Probleme der Graphentheorie, gibt es im Allgemeinen keine Formel oder polynomiell u ufbare Charakteri¨ berpr¨ sierung f¨ ur die chromatische Zahl. Wir haben zwar gesehen, daß χ(G) ≥ 3 dann und nur dann, wenn G einen ungeraden Kreis enth¨ alt (Satz 1.9 von K¨ onig), und daß 2-chromatische Graphen in linearer Zeit erkennbar und (optimal) f¨ arbbar sind. F¨ ur Graphen mit h¨ oherer chromatischer Zahl existieren solche Ergebnisse aber nicht. Deshalb gewinnen Schranken f¨ ur χ(G) an Bedeutung. Doch auch an Schranken f¨ ur die chromatische Zahl heranzukommen ist schwierig. Beachte, daß die beiden unteren Schranken f¨ ur χ(G) aus (4) und (5) vom algorithmischen Standpunkt aus nicht sehr hilfreich sind: F¨ ur die Berechnung der Parameter ω(G) oder α(G) existieren ebenfalls keine polynomiellen Verfahren. Angenommen, ein Algorithmus A konstruiert auf jedem Eingabegraphen eine zul¨assige F¨arbung. Dann ist die Anzahl der verwendeten Farben offenbar eine obere Schranke f¨ ur χ(G). Wir untersuchen in diesem Abschnitt einige einfache F¨arbungsheuristiken und leiten daraus obere Schranken f¨ ur die chromatische Zahl ab. Unter einem Greedy-Verfahren (greedy = engl. f¨ ur habgierig, gefr¨aßig) versteht man ein Verfahren, das sich bei jedem Schritt f¨ ur das lokale Optimum entscheidet und dadurch versucht, den Gewinn in jedem Schritt zu maximieren – deswegen aber u.U. das globale Optimum verfehlt. Wir untersuchen hier eine Greedy-Heuristik f¨ ur das Graphen-F¨arbungsproblem. Sei G = (V, E) ein Graph und eine beliebige Anordnung σ : {1, . . . , n} → V seiner Knoten gegeben. Der K¨ urze halber schreiben wir einfach σ = (v1 , . . . , vn ), um auszudr¨ ucken, daß der Greedy-F¨arbungsalgorithmus die Knoten von G in der durch σ vorgegebenen Reihenfolge v1 , . . . , vn durchgeht und jeden Knoten mit der niedrigsten zul¨ assigen Zahl f¨arbt. F¨ ur i ∈ {1, . . . , n} setze Vi := {v1 , . . . , vi } und Gi := G[Vi ]. arbung (G, σ) PROCEDURE Greedy F¨

: INTEGER;

BEGIN c(v1 ) := 1; FOR i := 2 TO n DO c(vi ) := min {k ∈ N| k 6= c(u) f¨ ur alle u ∈ Γ(vi ) ∩ Vi−1 }; RETURN |{c(v) : v ∈ V }|; END; Nach Konstruktion produziert dieser einfache Algorithmus eine zul¨assige Knotenf¨arbung c und liefert die Anzahl der dabei verwendeten Farben zur¨ uck.

11

Proposition 1.22. F¨ ur jede Anordnung σ der Knoten eines Graphen G gilt (i)

(ii)

χ(G) ≤ Greedy F¨ arbung (G, σ) ≤ ∆(G) + 1.

(6)

arbung kann mit Laufzeit O(n + m) implementiert werden. Der Algorithmus Greedy F¨ Beweis: Die Absch¨ atzung (i) folgt aus der Tatsache, daß der Algorithmus sicherlich eine zul¨assige F¨arbung konstruiert. Zu (ii): In jedem F¨ arbungsschritt k¨ onnen h¨ochstens |Γ(vi ) ∩ Vi−1 | ≤ d(vi ) ≤ ∆(G) viele Farben arbung unabh¨angig von σ stets mit den f¨ ur den Knoten vi verboten sein. Also kommt Greedy F¨ Farben {1, . . . , ∆(G) + 1} aus. Was die Laufzeit der Implementierung angeht, so ist die einzige H¨ urde wohl die Bestimmung von c(vi ). Hier ist zu vermeiden, daß f¨ ur jeden Knoten Ω(∆) viele Schritte ausgef¨ uhrt werden m¨ ussen. Benutze hierzu ein Feld zul¨ assig : {1, ..., ∆(G) + 1} → {0, 1}, wobei zul¨ assig[f ] = 1 bedeuten soll, daß der jeweils aktuelle Knoten vi mit der Farbe f zul¨assig gef¨arbt werden darf. Initialisierung (in O(n)): FOR j := 1 TO ∆ + 1 DO zul¨ assig[j] := TRUE; Zur Bestimmung von c(vi ): FOR v ∈ (Γ(vi ) ∩ Vi−1 ) DO zul¨ assig[c(v)] := 0; j := 0; REPEAT j := j + 1 UNTIL zul¨ assig[j] = 1; c(vi ) := j; FOR v ∈ (Γ(vi ) ∩ Vi−1 ) DO zul¨ assig[c(v)] := 1; Nach dem letzten Schritt ist das Feld zul¨ assig wieder auf 1 initialisiert. Damit ist der Aufwand insgesamt beschr¨ ankt durch n X d(vi ) = 2m. i=1

2

F¨ ur ungerade Kreise und vollst¨ andige Graphen gilt Gleichheit in der Ungleichungskette (6). Wie der K1,∆ zeigt, kann (unabh¨ angig von σ) die Absch¨atzung (ii) beliebig schlecht werden. F¨ ur die folgende Familie {Bn } bipartiter Graphen gibt es andererseits eine Anordnung σ der Knoten, bei der die Schranke (i) beliebig schlecht wird. Bn habe n = 2k viele Knoten (k ≥ 2) und entsteht aus dem vollst¨ andig bipartiten Graphen Kk,k = (U, V, E) durch Herausnahme des perfekten Matchings Mk := {{ui , vi } : i = 1, . . . , k}: Obwohl Bn zweif¨ arbbar ist, ben¨ otigt der Greedy-Algorithmus bei jeder Anordnung der Knoten, bei der auf ui stets vi folgt f¨ ur i = 1, . . . , k immer k = ∆(Bn ) + 1 = Ω(n) viele Farben. Der Greedy-Algorithmus liefert also i.a. beliebig schlechte F¨arbungen. ¨ Ubung 1.23. Man gebe eine Familie {Tn }n∈N von B¨aumen an, so daß Tn n Knoten hat und der Greedy-Algorithmus auf Tn bei entsprechender Anordnung der Knoten Ω(log n) viele Farben ben¨otigt. Es gilt aber: Lemma 1.24. F¨ ur jeden Graphen G gibt es eine Anordnung σ ∗ seiner Knoten, auf der der GreedyAlgorithmus eine optimale F¨arbung konstruiert, d.h. es gilt χ(G) = min Greedy F¨ arbung (G, σ). σ∈Sn

Beweis: Seien S1 , . . . , Sχ(G) die Farbklassen von G in einer χ(G)-F¨arbung. Enthalte σ ∗ = (v1 , . . . , vn ) zun¨achst die Knoten von S1 in beliebiger Reihenfolge, dann die von S2 u.s.w. Es folgt Greearbung (G, σ ∗ ) = χ(G). 2 dy F¨ 12

Leider kennen wir jedoch die Anordnung σ ∗ im Voraus nicht. Wir werden jedoch beweisen, daß Greedy F¨ arbung in aller Regel recht gute“ Resultate liefert – siehe Kapitel 3. ” Eine naheliegende Idee, um an bessere F¨arbungen mit weniger Farben zu kommen, ist, zun¨achst arbung eine g¨ unstige“ Anordnung σ = (v1 , . . . , vn ) der Knoten zu bestimmen und Greedy F¨ ” dann auf diese Anordnung anzuwenden. Die folgende sogenannte smallest-last Anordnung ist ein Beispiel f¨ ur einen derartigen Ansatz: FOR i := n DOWNTO 1 DO BEGIN w¨ ahle einen Knoten minimalen Grades in G als vi ; G := G − vi ; END; ¨ Es gilt die folgende Proposition, die wir in der Ubung beweisen werden. Proposition 1.25. (Szekeres, Wilf 1968) Sei G ein Graph und σSL eine smallest-last Anordnung seiner Knotenmenge. Dann gilt arbung (G, σSL ) ≤ 1 + max δ(H), χ(G) ≤ Greedy F¨ H

(7)

wobei das Maximum ¨ uber alle Subgraphen H von G genommen wird. Wir kehren zu der Schranke χ(G) ≤ ∆(G)+1 aus Proposition 1.22 zur¨ uck. Wie bereits der K1,∆ (und die Familie Bk von oben) zeigte, kann diese Schranke beliebig schlecht werden. W¨ahrend sie f¨ ur ungerade Kreise und vollst¨ andige Graphen scharf ist, kann sie f¨ ur alle anderen Graphen immerhin um eins verbessert werden. Korollar 1.26. Falls ein Graph G zusammenh¨angend, aber nicht ∆(G)-regul¨ar ist, so gilt χ(G) ≤ ∆(G). Beweis: Sei v1 ein Knoten in G mit d(v1 ) < ∆(G). Numeriere die Knoten von G in einer Reihenfolge v1 , . . . , vn , in der eine Breitensuche auf G mit Startknoten v1 die Knoten besucht hat. Greedy-f¨arbe nun G in der Reihenfolge σ = (vn , . . . , v1 ). Da jeder Knoten v 6= v1 einen Nachbarn mit kleinerer Nummer hat, hat v, wenn er an der Reihe ist, gef¨arbt zu werden, h¨ochstens ∆(G) − 1 bereits gef¨arbte Nachbarn. Also gilt Greedy F¨ arbung (G, σ) ≤ ∆(G). 2 Den regul¨ aren Fall behandelt der folgende Satz, auf dessen Beweis wir hier verzichten. Satz 1.27. (Brooks 1941) Sei G ein zusammenh¨angender Graph auf mindestens drei Knoten. Wenn G nicht vollst¨andig und kein ungerader Kreis ist, dann gilt: χ(G) ≤ ∆(G).

13

Vorlesung 27.10.

2

Zuf¨ allige Graphen

2.1

Eigenschaften fast aller Graphen

Wir bezeichnen mit G n die Menge aller Graphen mit Knotenmenge [n]. Proposition 2.1. n

|G n | = 2( 2 ) .

Proposition 2.2. Bezeichne mit I n die Menge aller Graphen in G n , die wenigstens einen isolierten Knoten haben. Dann gilt: |I n | = 0. lim n→∞ |G n | n−1 Beweis: Zu jedem festen Knoten x gibt es 2( 2 ) Graphen G, so dass x isolierter Knoten in G ist. Da wir x auf n verschiedene Weisen ausw¨ ahlen k¨onnen, gilt: n−1 2

|I n | ≤ n2(

),

und somit n−1 (n−1)(n−2) n−1 n2( 2 ) |I n | − (n)(n−1) 2 2 = n2 2 (n−2−n) = n2−(n−1) → 0, ≤ = n2 n ) ( |G n | 2 2 wenn n → ∞. 2 S∞ Eine Menge A ⊆ n=0 G n wird Grapheneigenschaft. Wir schreiben An := A ∩ G n und sagen, dass fast alle Graphen die Eigenschaft A haben, wenn f¨ ur n → ∞

|An | → 1. |G n | Falls der Quotient gegen 0 konvergiert, sagen wir dass fast kein Graph die Eigenschaft A hat. Proposition 2.3. Fast alle Graphen sind zusammenh¨angend. Beweis: Bezeichne mit U n die Menge aller Graphen aus G n , die nicht zusammenh¨angend sind. Wenn G ∈ U n , dann hat G eine Knotenteilmenge de Gr¨oße i mit 1 ≤ i ≤ ⌊ n2 ⌋, aus der keine Kante herausf¨ uhrt. i n−i F¨ ur eine solche festgew¨ ahlte Menge S gibt es 2(2) 2( 2 ) viele Graphen. Es gilt i i2 − i + n2 − 2in + i2 − n + i n−i n + = = + i(i − n), 2 2 2 2

also gilt |U n | ≤ |G n |

P⌊ n2 ⌋ i=1

( i ) (n−i) ⌊n ⌊n ⌊n 2⌋ 2⌋ 2⌋ X X 22 2 2 n i(i−n) X n i i i(i−n) . = n 2 ≤ 2 ≤ n n−i 2 i 2( 2 )

n i

i=1

i=1

i=1

Nun ist f¨ ur 1 ≤ i ≤ ⌊ n2 ⌋ nat¨ urlich 2n−i ≥ 2n/2 und, f¨ ur n ≥ 4 auch n ≤ 2n/2 . Damit k¨onnen wir die obige Summe weiter wie folgt absch¨ atzen: n

n

⌊2⌋ ⌊2⌋ X n i X n n2 ≤ → 0, ≤ ≤ 2n/2 2n/2 2n/2 i=1 i=1

14

f¨ ur n → ∞.

2

Unser n¨achstes Ziel ist es, die beiden bisherigen Aussagen noch zu steigern. Dazu ¨andern wir aber zun¨achst die Sichtweise etwas, und ben¨otigen die entsprechenden Definitionen. Es sei Ω ein endlicher Wahrscheinlichkeitsraum, also eine endliche Menge, zusammen mit einer Funktion p : P ullt. Ein Ereignis ist eine Menge A ⊆ Ω, die Wahrscheinlichkeit Ω → [0, 1] die ω∈Ω p(ω) = 1 erf¨ von A wird bezeichnet mit X P [A] := p(ω). ω∈Ω

Eine Zufallsvariable ist eine Funktion X : Ω → R, ihr Erwartungswert ist definiert als X E [X] := X(ω)p(ω). ω∈Ω

In unserer Standardsituation ist Ω = G n und wir stellen uns das folgende Zufallsexperiment vor: jede aller m¨oglichen Kanten existiere mit Wahrscheinlichkeit 1/2. Das Ergebnis dieses Experiments bezeichnen wir mit Gn, 12 . F¨ ur einen beliebigen Graphen G ∈ G n setzen wir i h p(G) := P Gn, 21 = G =

1 n , ( 2 2)

wir haben also die Gleichverteilung auf der Menge G n . Mit anderen Worten: f¨ ur ein Ereignis An ⊆ G n gilt nun X 1 |An | , p(G) = |An | n = P [An ] = ) ( |G n | 2 2 G∈An das heißt: P [An ] → 1 genau dann, wenn fast alle Graphen Eigenschaft A haben.

Im Folgenden werden wir nun sehen, wie in dem neuen Modell viele Rechnungen einfacher werden. Dazu zun¨ achst einige elementare Aussagen u ¨ber den Erwartungswert einer Zufallsvariable. Proposition 2.4. Pk a) Seien X1 , . . . , XP k Zufallsvariablen und λ1 , . . . , λk ∈ R. Setze X := i=1 λi Xi . Dann gilt E [X] = i λi E [Xi ]. b) Sei X eine Zufallsvariable mit X ∈ {0, 1}. Dann ist X X p(ω) = P [X = 1]. E [X] = X(ω)p(ω) = ω∈Ω

ω∈Ω:X(ω)=1

c) Sei X eine Zufallsvariable mit X ≥ 0, und sei t > 0. Dann ist P [X ≥ t] ≤

E [X] . t

d) Insbesondere gilt P [X ≥ 1] ≤ E [X].

Ausgestattet mit diesem Werkzeug wollen wir jetzt noch einmal Proposition 2.2 beweisen. Sei dazu Y : G n → N die Anzahl isolierter Knoten eines Graphen. Wir m¨ ussen zeigen, dass P [Y ≥ 1] → 0. F¨ uhre dazu die folgende 0-1-Zufallsvariablen ein: ( 0 sonst Yi := 1 Knoten i ist isoliert. P Dann ist Y = i Yi und es gilt P [Yi = 1] = (1/2)n−1 , weil ja alle von i ausgehenden Kanten nicht existieren d¨ urfen. Somit folgt: (2.4)

(2.4)

P [Y ≥ 1] ≤ E [Y ] =

X

(2.4)

E [Yi ] =

X i

i

15

P [Yi = 1] = n(1/2)n−1 → 0,

was zu zeigen war. Nachdem wir nun bereits wissen, dass fast alle Graphen keine isolierten Knoten beitzen, ja sogar zusammenh¨angend sind, interessiert uns nun, wie weit es ein Knoten maximal zu einem anderen hat. Der Durchmesser eines Graphen G ist defininert als diam(G) := max{dist(x, y) : x, y ∈ V }. Proposition 2.5. Fast alle Graphen haben Durchmesser 2. Beweis: Sei Z die Anzahl Paare von Knoten x, y, die keinen gemeinsamen Nachbarn haben. Wenn der Graph G nicht vollst¨ andig ist und Z = 0, dann hat G Durchmesser 2. Setze ( 0 sonst Zi,j := 1 i, j haben keinen gemeinsamen Nachbarn. Dann gilt Z=

X

Zi,j

und

P [Zi,j = 1] = (3/4)n−2 ,

i<j

und es folgt (2.4)

(2.4)

P [Z ≥ 1] ≤ E [Z] =

X

(2.4)

E [Zi,j ] =

X i<j

i<j

P [Zi,j = 1] ≤ n2 (3/4)n−2 → 0.

Damit ist h i h i P Gn, 21 hat nicht Durchmesser 2 = P Gn, 21 ist vollst¨andig + P [Z ≥ 1] → 0.

2

Vorlesung 2.11. Wir notieren hier zun¨ achst einige Aussagen und Definitionen aus der elementaren Wahrscheinlichkeitstheorie. Es seien A, B ⊆ Ω Ereignisse, deren Wahrscheinlichkeit wir (wie bisher auch) mit P P [A] := ω∈A p(ω) bezeichnen. Proposition 2.6. (i) P [∅] = 0. (ii) P A¯ = 1 − P [A], wobei A¯ = Ω \ A. (iii) Wenn A ⊆ B, dann P [A] ≤ P [B].

(iv) P [A ∪ B] = P [A] + P [B] − P [A ∩ B]. P S ur alle i 6= j. (v) P [ i Ai ] ≤ i P [Ai ] und Gleichheit gilt, wenn Ai ∩ Aj = ∅ f¨

(vi) Definition: A und B heißen unabh¨angig, wenn P [A ∩ B] = P [A] · P [B].

(vii) Definition: P [A|B] := P [A ∩ B]/P [B] ist die Wahrscheinlichkeit f¨ ur das Ereignis A unter der Bedingung, dass B bereits eingetreten ist. S (viii) Wenn Bi ∩ Bj = ∅ f¨ ur alle i 6= j und A ⊆ i Bi , dann X X P [A|Bi ]P [Bi ] P [A ∩ Bi ] = P [A] = i

i

.

(ix) Insbesondere gilt

.

¯ P B ¯ ≤ P [A|B] + P B ¯ P [A] = P [A|B]P [B] + P A|B 16

Wir hatten bereits gesehen, dass fast alle Graphen zusammenh¨angend sind und Durchmesser 2 haben. Diese Aussage wollen wir im Folgenden noch steigern. Zun¨achst noch eine weitere Definition. Es seien Es seien s, t ∈ N. Ein Graph G heißt (s, t)-erweiterbar wenn es zu je zwei disjunkten Teilmengen S bzw. T der Kardinalit¨ at s bzw. t einen Knoten x außerhalb von S und T gibt, der zu allen Knoten in S und zu keinem Knoten in T verbunden ist. Satz 2.7. Seien s, t ∈ N fest. Dann sind fast alle Graphen (s, t)-erweiterbar. Beweis: Es sei X die Anzahl der nicht erweiterbaren Paare S, T mit |S| = s und |T | = t und S ∩ T = ∅. Sei XS,T die kanonische Indikatorvariable. Dann gilt P [XS,T = 1] = (1 − 2−(s+t) )n−(s+t) , denn f¨ ur einen Knoten x aus V \ (S ∪ T ) betr¨agt die Wahrscheinlichkeit, dass er mit allen Knoten aus S und mit keinem aus T verbunden ist 2−(s+t) . Da es insgesamt n − (s + t) Kandidaten f¨ ur ein solches x gibt, betr¨ agt die Wahrscheinlichkeit, dass es keinen Knoten gibt, der die Bedingung f¨ ur dieses Mengenpaar erf¨ ullt, (1 − 2−(s+t) )n−(s+t) . Daraus folgt: n n−s n→∞ P [X ≥ 1] ≤ E [X] ≤ (1 − 2−(s+t) )n−(s+t) −−−−→ 0, s t denn s und t sind ja fest gew¨ ahlt und wachsen nicht mit n.

2

Korollar 2.8. Sei H ein belieber, fester Graph. Dann gilt: Fast alle Graphen haben enthalten eine induzierte Kopie von H, also einen induzierten Subgraphen, der isomorph ist zu H. Wir schreiben: h i P H 6⊂ Gn, 21 → 0. Beweis: Induktion u alle s = 0 oder s = 1 sind klar. Entferne einen beliebigen ¨ber s := |H|. Die F¨ Knoten v aus H und erhalte somit den Graph H ′ := H \ v. Nun gilt: h i 2.6(ix) h i h i P H 6⊂ Gn, 21 ≤ P H 6⊂ Gn, 21 |H ′ ⊂ Gn, 12 + P H ′ 6⊂ Gn, 21 .

Letztere Wahrscheinlichkeit geht nach Induktion gegen 0. Betrachte erstere und sei s := |ΓH (v)| und t := |H ′ | − |ΓH (v)|. Dann ist i h i h P H 6⊂ Gn, 12 |H ′ ⊂ Gn, 12 ≤ P Gn, 12 ist nicht (s, t)-erweiterbar ,

denn sonst k¨ onnten wir ja einen Knoten v in Gn, 12 finden, der die Kopie von H ′ zu einer Kopie von H fortsetzt. Nach Satz 2.7 konvergiert aber die zuletzt genannte Wahrscheinlichkeit gegen 0. 2

¨ Ubung 2.9. Sei k ∈ N fest. Folgere aus Satz 2.7: (i) Fast alle Graphen sind k-zusammenh¨angend. (ii) Fast alle Graphen haben Durchmesser 2. (iii) Fast alle Graphen haben Minimalgrad ≥ k. (iv) Fast alle Graphen haben keine trennende Clique. Wir haben bislang benutzt, dass dank Proposition 2.4d) E [X] → 0 impliziert, dass P [X] → 0. Nun stellt sich die Frage, um umgekehrt ein hoher Erwartungswert auch garantiert, dass P [X] → 1. ¨ Das gilt nicht immer (siehe Ubung 2.17), wohl aber unter st¨arkeren Voraussetzungen. Um die zu pr¨ azisieren brauchen wir den Begriff der Varianz. Sei Y eine Zufallsvariable und µ := E [Y ]. Dann beschreibt die Varianz von Y die erwartete Abweichung von E [Y ] und ist definiert als Var [Y ] := E (Y − µ)2 = E Y 2 − 2µE [Y ] + µ2 = E Y 2 − µ2 . 17

Satz 2.10. (Chebychev-Ungleichung) F¨ ur jede nicht negative Zufalls variable Y und jedes t > 0 gilt: Var [Y ] P [|Y − µ| ≥ s] ≤ . s2 Beweis: Wende Proposition 2.4c) auf die Variable (Y − µ)2 mit t := s2 an.

2

Korollar 2.11. Sei α(n) eine beliebig langsam wachsende Funktion. Die Kantenanzahl fast aller Graphen liegt zwischen 21 n2 − α(n)n und 21 n2 + α(n)n.

Beweis: Es sei Y die Kantenanzahl, Yi,j die kanonische Indikatorzufallsvariable zu jedem Paar von Knoten i, j. Offensichtlich gilt X 1 n P [Yi,j = 1] = µ := E [Y ] = . 2 2 i<j Zur Bestimmung der Varianz berechnen wir  2   X X 2   2 Yi,j + Yi,j   = E  = E  E Y i<j

i<j

=

X 2 P Yi,j =1 + i<j

=

n 1 + 2 2

X

X

(i<j),(k
P [Yi,j Yk,l = 1]

(i<j),(k


Yi,j Yk,l 

2 ! n n + , 2 2

2 ! 1 n n 1 = − 4 4 2 2

und daraus folgt 2 2 2 1 n 1 n 1 n 1 n 2 Var [Y ] = E Y − µ = − . + = 4 2 4 2 4 2 4 2

Wende nun Satz 2.10 mit s := α(n)n an und erhalte

P [|Y − µ| ≥ α(n)n] ≤

1 n 4 2 α(n)2 n2

→ 0. 2

Aus der Absch¨ atzung der Wahrscheinlichkeit f¨ ur die Abweichung vom Erwartungswert ergibt sich insbesondere eine Absch¨ atzung f¨ ur die Wahrscheinlichkeit daf¨ ur, dass Y = 0 ist: setze s = µ in Satz 2.10 und erhalte E Y2 Var [Y ] = − 1. (8) P [Y = 0] ≤ P [|Y − µ| ≥ µ] ≤ µ2 µ2 Das verpacken wir in dem folgenden Lemma. P ur i 6= j schreiben wir i ∼ j, wenn Lemma 2.12. Sei Y = i∈I Xi , Xi ∈ {0, 1} und µ = E [Y ]. F¨ die Ereignisse Xi = 1 und Xj = 1 voneinander abh¨angig sind und definieren: X X P [Xi = 1 ∧ Xj = 1]. ∆ := P [Xi = 1 ∧ Xj = 1], ∆1 := i∼j

i6=j

Dann gilt: P [Y = 0] ≤ P [Y = 0] ≤ 18

∆ 1 + − 1, µ µ2 ∆1 1 + 2. µ µ

(9) (10)

Beweis: X X X X E [Xi ] + P [Xi = 1 ∧ Xj = 1] = µ + ∆, E (Xi )2 + E [Xi Xj ] = E Y2 = i

i

i6=j

E Y2 µ+∆ 1 ∆ P [Y = 0] ≤ −1= − 1 = + 2 − 1, 2 2 µ µ µ µ

i6=j

(8)

und das beweist (9). Um (10) einzusehen, betrachte man X X P [Xi = 1 ∧ Xj = 1] ∆= P [Xi = 1 ∧ Xj = 1] + i6∼j

=

X i6∼j

i∼j

X P [Xi = 1] · P [Xj = 1] + ∆1 ≤ ( P [Xi = 1])2 + ∆1 =

µ2 + ∆1 ,

i∈I

und somit

(9)

P [Y = 0] ≤

1 1 ∆ µ2 + ∆1 ∆1 1 −1= + 2 . + 2 −1≤ + 2 µ µ µ µ µ µ 2

Vorlesung 3.11.

2.2

Evolution zuf¨ alliger Graphen

Im letzten Abschnitt haben wir u ¨ berraschend starke Eigenschaften kennengelernt, die von fast allen Graphen geteilt werden. Man k¨ onnte auch sagen, dass der durch das Gn, 21 –Modell oder durch die Gleichverteilung propagierte Blickwinkel eine sehr enge Sichtweise erzwingt – und zwar einfach dadurch, dass hier fast ausschließlich Graphen betrachtet werden, die eine sehr hohe Kantenanzahl haben: Eine Grapheneigenschaft ist genau dann typisch, wenn sie f¨ ur Graphen mit ungef¨ahr 21 n2 Kanten typisch ist. Eine naheliegende Verallgemeinerung ist daher die folgende: jede der n2 Kanten existiere mit Wahrscheinlichkeit p = p(n). Das Ergebnis dieses Zufallsexperiments bezeichnen wir mit Gn,p . Damit gilt f¨ ur eine beliebige Grapheneigenschaft A, dass X X n pkGk (1 − p)( 2 )−kGk . P [Gn,p = G] = P [Gn,p ∈ A] := G∈An G∈An Unser Hauptaugenmerk wird sich nun auf die Frage richten, f¨ ur welche Dichte p = p(n) die Wahrscheinlichkeit P [Gn,p ∈ A] gegen 0 bzw. gegen 1 konvergiert. Bevor wir dazu kommen, noch ein paar technische Details. F¨ ur zwei Funktionen f = f (n) und g = g(n) schreiben wir f →0 g g f f ≫ g :⇔ g = o(f ) ⇔ → 0 ⇔ → ∞ f g f f ∼ g :⇔ f = (1 + o(1))g ⇔ → 1. g f ≪ g :⇔ f = o(g) ⇔

Ein weiteres, technisches Werkzeug ist die folgende kleine, n¨ uztliche Rechenhilfe: Proposition 2.13. 2

(i) ∀x ∈ (0, 21 ) : e−x−x ≤ 1 − x ≤ e−x 19

(11) (12) (13)

(ii) f¨ ur x → 0 : 1 − x ∼ e−x Beweis: (i) via Kurvendiskussion oder Mathematica. x→0

2

(i)

(ii) 1 ←− e−x ≤

1−x e−x

(i)

≤1 2

Die zentrale Definition dieses Abschnitts ist nun die folgende: Eine Funktion t(n) heißt Schwellenwertfunktion f¨ ur die Grapheneigenschaft A, wenn n→∞

p(n) ≪ t(n) ⇒ P [Gn,p ∈ A] −−−−→ 0

( 0-Aussage“) ” ( 1-Aussage“) ”

n→∞

p(n) ≫ t(n) ⇒ P [Gn,p ∈ A] −−−−→ 1

Satz 2.14. F¨ ur A := {G δ(G) ≥ 1} ist die Schwellenwertfunktion t(n) = (A = G hat keine isolierten Knoten“) ”

(14) (15)

ln(n) n .

Beweis: Sei X := #Knoten vom Grad 0 =

X

Yv ,

v∈V

Es gilt µ := E [x] = p t

0-Aussage: n→∞ pn = ln(n) −−−−→ 0,

P

also pn ≤ (1 − ε) ln(n) µ=

E [Yv ] =

v∈V

Def

v∈V

1 0

d(v) = 0 sonst.

P [d(v) = 0] = n(1 − p)n−1 .

n→∞

∀0 < ε < 1 und große n. Insbesondere gilt p −−−−→ 0.

n (1 − p)n 1−p ∆ =

P

mit Yv :=

(

X

u6=w

2.13(ii)

∼

n −pn n −(1−ε)ln(n) nε n→∞ −−−−→ ∞ e ≥ e = 1−p 1−p 1−p

P [Yu = 1 ∧ Yv = 1] =

=

X

u6=w

X

u6=w

P [Yu = 1] P Yu = 1 Yv = 1

(1 − p)n−1 (1 − p)n−2 ≤ n2 (1 − p)2n−3

∆ ⇒ 2 ≤ µ

2 n (1 − p)2n−3 1 n→∞ −−−−→ 1 = n2 (1 − p)2n−2 1−p (9)

⇒ P [δ ≥ 1] = P [X = 0] ≤

1 ∆ n→∞ − 1 −−−−→ 0. + µ µ2

1-Aussage: n→∞ pn = ln(n) −−−−→ ∞, also pn ≥ (1 + ε) ln(n) ∀ε > 0 und große n. Ferner k¨onnen und wollen wir annehmen, dass ur Gn, 12 bereits bewiesen haben. p < 21 , da wir die Aussage f¨ p t

µ = n(1 − p)n−1 =

1 n→∞ n −pn n −(1+ε) ln(n) 1 n −−−−→ 0. (1 − p)n ≤ e ≤ e = 1−p 1−p 1−p 1 − p nε n→∞

Also P [δ < 1] = P [X ≥ 1] ≤ E [X] −−−−→ 0. 2

20

Bemerkung 2.15. Satz 2.14 besagt, dass p pn = t ln(n)

(

−→ 0 −→ ∞

⇒ Gn,p ∈ 6 A ⇒ Gn,p ∈ A

Der Beweis zeigt aber ein st¨arkeres Resultat, n¨amlich: ( ≤ (1 − ε) ⇒ Gn,p ∈ 6 A pn p = t ln(n) ≥ (1 + ε) ⇒ Gn,p ∈ A Man spricht in so einem Fall von einem scharfen Phasen¨ ubergang. Satz 2.16. F¨ ur A = {G G ist zusammenh¨angend} ist die Schwellenwertfunktion t(n) =

ln(n) n .

Beweis:

0-Aussage: n→∞ F¨ ur pt −−−−→ 0 gilt fast sicher δ(Gn,p ) = 0 nach Satz 2.14, deshalb ist Gn,p nicht zusammenh¨angend: n→∞

P [Gn,p ist zusammenh¨angend] ≤ P [δ ≥ 1] −−−−→ 0. 1-Aussage: n→∞ pn = ln(n) −−−−→ ∞ Sei also p ≥ 6ln(n) n , Xl :=#Komponenten der Gr¨ oße exakt l in Gn,p , p t

Dann ist

1≤l≤

n 2.

E [Xl ] ≤ |{z} nl

(1 − p)l(n−l) {z } | m¨ogliche keine Kanten Komponenten nach außen

Wenn eine l-Menge Kanten nach außen (zu Knoten, die nicht in der Menge liegen) hat, ist sie keine Komponente mit Gr¨ oße exakt l. Vielleicht ist die Menge jedoch nicht zusammenh¨angend, deshalb ist (1 − p)l(n−l) nur eine obere Schranke. E [Xl ] ≤ nl (1 − p)l(n−l) ≤ nl e−p l(n−l)

= el ln(n)−p l(n−l) ≤ el ln(n)−

6 ln(n) n

l (n− n 2) 6 n

= el ln(n)−l ln(n)( n 2 )

= e−2l ln(n) = n−2l 1 ≤ 2 n Also

n

2 X

l=1

und P [Gn,p

E [Xl ] ≤

n 1 1 n→∞ −−−−→ 0 = 2 n2 2n

   n  n n 2 2 2 X X X n→∞ Xl ≥ 1  ≤ E  Xl  = E [Xl ] −−−−→ 0 nicht zusammenh¨ angend] = P  l=1

(Es gen¨ ugt, Komponenten der Gr¨ oße ≤ bedingt.)

n 2

l=1

l=1

zu z¨ahlen, da jede gr¨oßere Komponente eine kleinere 2

Vorlesung 9.11. 21

Im folgenden nun noch ein Beispiel f¨ ur eine Zufallsvariable, deren Erwartungswert gegen unendlich geht, bei der die Wahrscheinlichkeit, dass ihr Wert gr¨oßer als 0 ist, jedoch trotzdem gegen 0 konvergiert. ¨ Ubung 2.17. Sei p =

2 n

und X die Anzahl der spannenden B¨aume in Gn,p . Dann gilt:

n→∞

(i) E [X] −−−−→ ∞, aber n→∞

(ii) P [X ≥ 1] −−−−→ 0 Beweis: (i) Sei T ein spannender Baum des Kn , ( 1 T ⊆ Gn,p X= YT , YT := 0 sonst T P E [X] = PT E [YT ] = T P [T ⊆ Gn,p ] X

Cayley

nn−2 pn−1 n−1 nn−2 n2 2n−1 n→∞ −−−→ ∞ n −

= = =

(ii) Gn,p zusammenh¨ angend ⇔ es gibt spannenden Baum 2.16

⇒ P [X ≥ 1] = P [G ist zusammenh¨angend] −→ 0 2 ¨ Ubung 2.18. Sei H ein fest gew¨ahlter Graph. Definiere die Dichte ρ(H)

:=

ρ′ (H)

:=

|E(H)| ||H|| = , |H| |V (H)| max {ρ(H ′ )}. ′

H ⊆H

Es gilt also beispielsweise, dass ρ′ (K4 ) = ρ(K4 ) = 6/4. Zeige: ′ t(n) = n−1/ρ (H) ist eine Schwellenwertfunktion f¨ ur die Eigenschaft, eine Kopie von H (also einen Subgraphen, der isomorph zu H ist) zu enthalten. e0 v0

Beweis: Sei H0 ⊆ H so, dass ρ′ (H) = ρ(H0 ) =

mit

e0 = ||H0 ||; v0 = |H0 |; e = ||H||; v = |H|; e′ = ||H ′ ||; v ′ = |H ′ |

f¨ ur einen beliebigen Subgraphen H ′ ⊆ H. Dann gilt ∀H ′ ⊆ H : ′

e0 e′ v′ v0 ≥ ′ , also ′ ≥ , v0 v e e0

(16)

v0

Wir haben also t = n−1/ρ (H) = n− e0 und zeigen nun: n→∞

(i) 0-Aussage: p(n) ≪ t(n) ⇒ P [H ⊂ Gn,p ] −−−−→ 0. n→∞

(ii) 1-Aussage: p(n) ≫ t(n) ⇒ P [H ⊂ Gn,p ] −−−−→ 1. Zu (i): p(n) ≪ t(n) ⇔ Es gilt

p(n) n→∞ −−−→ t(n) −

v0

n→∞

0 ⇔ p(n) · n e0 −−−−→ 0 P [H ⊂ Gn,p ] ≤ P [H0 ⊂ Gn,p ].

Z¨ahle nun die Zufallsvariable Y0 die Anzahl der Kopien von H0 in Gn,p . Dann gilt 2.4d)

v0

P [H0 ⊂ Gn,p ] = P [Y0 ≥ 1] ≤ E [Y0 ] = Θ(nv0 pe0 ) = Θ([n e0 p]e0 ) → 0 22

v0

n→∞

n→∞

−−−→ ∞ ⇔ p(n) · n e0 −−−−→ ∞ Zu (ii): p(n) ≫ t(n) ⇔ p(n) t(n) − Sei S ⊂ [n] eine Menge der Gr¨ oße v in Gn,p bezeichne AS das Ereignis ,,S enth¨alt eine feste Kopie von H”. (Prinzipiell kann eine Menge S mehrere Kopien von H enthalten, wir betrachten aber nur eine feste.) Sei ( 1 AS XS := 0 sonst die Indikatorvariable von AS . Dann gilt X XS ≤ Anzahl der Kopien von H in Gn,p . Y := S ⊆V :|S|=v

Die Linearit¨ at des Erwartungswertes liefert µ = E [Y ] =

X

(16)

v

S:|S|=v

v0

E [XS ] = Θ(nv pe ) = Θ([n e p]e ) ≥ Θ([n e0 p]e0 ) → ∞.

F¨ ur abh¨ angige Ereignisse AS und AT gilt X ∆1 /µ2 = P [XS = 1 ∧ XT = 1]/µ2 S∼T

=

v−1 X

v ′ =2

X

|S∩T |=v ′

P [AS ∩ AT ]/µ2 .

Es bleibt die Aufgabe P [AS ∩ AT ] zu berechnen. Bezeichne dazu mit H ′ den eindeutigen Subgraphen von H, der sich aus dem Schnitt der festgelegten Kopie von H auf S bzw. T ergibt. Offensichtlich ist |H ′ | = v ′ und sei ||H ′ || = e′ . Dann erfordert AS ∩AT einen speziellen Subgraphen auf 2v − v ′ Knoten und 2e − e′ Kanten. Also (16)

′

P [AS ∩ AT ] = p2e−e ≤ p2e−v

′ e0 v0

.

Damit ist

1

2

∆ /µ

≤ = =

v−1 X

P

v ′ =2 v−1 X

O

v−1 X

O O

µ2

n v

v v′

e

2e−v ′ · v0 n−v 0 v−v ′ p 2v 2e n p ′ e0

nv nv−v p2e−v · v0 n2v p2e ! 1 v′ ·

!

!

e0

n v ′ p v0 " #v′ · ve0  v−1 0 X 1  → 0. O  v0 n e0 p v ′ =2

v ′ =2

=

0

′

v ′ =2

=

2e−v ′ · v0

|S∩T |=v ′

v ′ =2 v−1 X

e

p

Nun wenden wir die Gleichung (10) an und erhalten: P [H 6⊂ Gn,p ] ≤ P [Y = 0] ≤

1 ∆1 + 2 → 0. µ µ 2

¨ Als Folgerung erh¨ alt man das folgende Korollar, dessen Beweis wir dem Leser als Ubung u ¨ berlassen. 23

2

¨ Ubung 2.19. Die Schwellenwertfunktion f¨ ur ω(G) ≥ l“ ist n− l−1 f¨ ur konstante l. ” − l+1 l f¨ ur konstante l. Die Schwellenwertfunktion f¨ ur Maximalgrad ≥ l“ ist n ” Nat¨ urlich hat nicht jede Grapheneigenschaft eine Schwellenwertfunktion – man betrachte beispielsweise “G hat eine ungerade Anzahl von Kanten”. Aber es gilt der Satz 2.20. Sei A eine Grapheneigenschaft, die unter Isomorphie und Kanten-Addition abgeschlossen ist. Dann hat A eine Schwellenwertfunktion. Beweis: ohne 2

2.3

Im Phasenu ¨bergang

Im Folgenden wollen wir die Kantenwahrscheinlichkeit so w¨ahlen, dass sie sich genau auf dem Schwellenwert einer Eigenschaft befindet, und dort die Wahrscheinlichkeit f¨ ur das Eintreten der Eigenschaft ermitteln. Dazu ben¨ otigen wir das folgende Hilfsmittel: Satz 2.21 (Jansonsche Ungleichung). Gegeben seien P wie in Lemma 2.12 Indikatorzufallsvaur i 6= j schreiben wir riablen Xi ∈ {0, 1} f¨ ur eine Indizes i ∈ I, es sei Y = i∈I und µ = E [Y ]. F¨ wieder i ∼ j, wenn die Ereignisse Xi = 1 und Xj = 1 voneinander abh¨angig sind und definieren: X P [Xi = 1 ∧ Xj = 1]. ∆1 := i∼j

Unter den Voraussetzungen, dass P [Xi = 1] → 0 und (i) ∀J ⊂ I, ∀i 6∈ J:

 ^ P Xi = 1 (Xj = 0)  ≤ P [Xi = 1] j∈J 

(ii) ∀J ⊂ I, ∀i, k 6∈ J:  Dann gilt

 ^ P (Xi = 1) ∧ (Xk = 1) (Xj = 0)  ≤ P [(Xi = 1) ∧ (Xk = 1)] j∈J e

−µ

≤ P [Y = 0] ≤

(

e−µ+∆ 2

e

µ − 2∆ 1

1

immer wenn ∆1 ≥ µ.

(17)

P aren die Xi alle Dazu einige Erl¨ auterungen. Setze pi := P [Xi = 1]. Dann ist i pi = µ. W¨ paarweise unabh¨ angig, dann h¨ atten wir Y Y Y (1 − pi ) ∼ e−pi = e−µ , P [Xi = 0] = P [Y = 0] = i

i

das heißt, die Varianz (inder Form von ∆1 ) misst auch hier wieder die Abweichung von der Unabh¨angigkeit. Vorlesung 10.11.

24

Bemerkung 2.22. Man vergleiche die beiden Absch¨atzungen: (1 ∆1 nach (10) µ + µ2 2 P [Y = 0] ≤ µ nach (17), e− ∆ 1 das heißt: wenn

∆1 µ2

→ ∞, dann ist die zweite Schranke im Vergleich zur ersten exponentiell klein.

Satz 2.23. Es sei t = t(n) =

1 n.

P [Gn,p

Dann ist   0 n→∞ c3 hat Dreieck] −−−−→ 1 − e− 6   1

p t p t p t

→0

=c →∞

¨ Beweis: Die 0- und die 1-Aussage folgen aus Ubung 2.18, wir wenden uns also dem Fall p = c/n zu. F¨ ur S ⊂ [n], |S| = 3 setze ( 1 AS = b Gn,p [S] = K3 Ys = b sonst 0 AS =

Damit ist X =

P

n→∞

S

YS die Anzahl der Dreiecke, und es gilt P [AS ] = p3 −−−−→ 0. Ferner ist c3 n 3 3 n 3 c3 n 3 = p = µ= p ∼ 3 6 6 n 6 3

sowie ∆1 =

X

S∼T

c5 n→∞ P [AS ∧ AT ] ≤ Θ n4 p5 = Θ n4 5 −−−−→ 0. n

Die Voraussetzungen (i) und (ii) im Satz 2.21 gelten, denn die Abwesenheit von Dreiecken f¨ordert nicht die Anwesenheit von Dreiecken an anderer Stelle. Somit folgt (17)

⇒ ⇒

e−µ ≤ 1 ≤

P [X = 0] ≤ P[X=0] ≤ e−µ n→∞

e−µ+∆ 1 n→∞ e∆ −−−−→ 1

⇒ P [X = 0] −−−−→ e−µ ∼ e−

c3 6

. 2

Wir hatten bereits gesehen, dass die Eigenschaft “enth¨alt isolierte Knoten” in der N¨ahe des Schwellenwerts wesentlich sensibler auf Ver¨anderungen in der Kantenwahrscheinlichkeit reagiert siehe Bemerkung 2.15. Wie vollzieht sich nun bei einem solchen Phasen¨ ubergang der Wechsel von 0 bis 1? Satz 2.24. Es sei t =

P [Gn,p

ln(n) n .

Dann ist

  0 −c n→∞ hat keine isolierten Knoten] −−−−→ 1 − e−e   1

p t p t p t

≤1−ε c = 1 + ln(n) ≥1+ε

Beweis: Auch hier hatten wir die 0- und die 1-Aussage bereits im Beweis von Satz 2.14 gezeigt. F¨ ur den Fall p n = ln(n) + c skizzieren wir hier nur den Beweis. Es sei die X die Anzahl isolierter Knoten, µ = E [X]. Es l¨asst sich dann wieder zeigen (diesmal mit mehr Arbeit), dass P [X = 0] ∼ e−µ . Wegen µ

Beweis 2.14

= ∼ = = n→∞ −−−−→

n n 1−p (1 − p) n −p n 1−p e n −ln(n) −c e 1−p e 1 −c e 1−p −c

e 25

,

folgt dann die Behauptung.

2

Welche Eigenschaften haben scharfe Phasen¨ uberg¨ange, welche nicht? Hier eine kleine Beispielsammlung: Beispiel. scharf: δ ≥ 1“ ln(n) n ” zusammenh¨ angend“ ln(n) n ” planar“ n1 ” X > 3“ θ n1 ” unscharf: hat Dreieck“ n1 ” v0 hat Kopie von H“ n− e0 ” l+1 ∆ ≥ l“ n− l ” 2 ω ≥ l“ n− l−1 ” und es gibt auch Mischformen: nur eine Seite scharf: X > 2“ n1 ” Satz 2.25. c n→∞ p = nc , 0 < c < 1 : P [X (Gn,p ) > 2] −−−−→ 1 − e 2 n→∞ p = n1 : P [X (Gn,p ) > 2] −−−−→ 1

1−c 1+c

41

Beweis: ohne 2 Bemerkung 2.26. unscharf ⇔ lokal“ ” scharf ⇔ global“ ” Bemerkung 2.27. hat Dreieck und ≥ log(n)Kanten “ hat gleiche Schwellenwertfunktion wie hat Dreieck“. ” ” ¨ Ubung 2.28. Zeigen Sie: t(n) = 1/n ist Schwellenwertfunktion f¨ ur die Eigenschaft “G hat mindestens einen Kreis”. ¨ Ubung 2.29. Wo liegt die/eine Schwellenwertfunktion f¨ ur die Eigenschaft “G hat Durchmesser ≤ 2”? Beweisskizze gen¨ ugt.

2.4

Chromatische Zahl zuf¨ alliger Graphen

Zun¨achst einige hilfreiche Absch¨ atzungen. ¨ Ubung 2.30. (a) Seien xi ∈ R≥0 mit

(b) Stirlings Formel:

Pl

xi = n gegeben. Dann ist n l l n 2 X X xi ≥l l . , x2i ≥ l 2 l 2 i=1 i=1 i=1

m! ∼

(c)

m m e

√ 2πm

n k k

(d) log

≤

n n e k ≤ k k

n = k log n − k log k + O(k) k 26

Wir untersuchen erst die chromatische Zahl d¨ unner zuf¨alliger Graphen, also im Bereich der Kantenwahrscheinlichkeit p = Θ( n1 ). Proposition 2.31. ∀l, l ≥ 3, l konstant ∃ konstantes cl , so dass p≥

cl ⇒ P [χ(Gn,p ) ≤ l] → 0 n

Beweis: W¨ahle Konstante cl so groß, dass cl

le− 3l < 1. Sei X Anzahl l-F¨ arbungen. Sei Π eine Partition der Knotenmenge [n] = V1 ∪ · · · ∪ Vl . Wenn Π eine F¨arbung sein soll, dann d¨ urfen in Gn,p l X |Vi | 2.30(a) ≥ l· f (Π) := 2 i=1

n n l(l

− 1) 2

f¨ ur n ≥ 3l

≥

l·

n 2n l ( 3l )

2

=

n2 3l

Paare keine Kanten haben. Daher P [Π ist F¨arbung] = (1 − p)f (Π) , also P [χ(Gn,p ) ≤ l] = P [X ≥ 1] ≤ E [X] =

X Π

n2

cl

n2

cl

(1 − p)f (Π) ≤ ln e−p 3l ≤ ln e− n · 3l = [le− 3l ]n .

Nach Wahl von cl konvergiert dieser Ausdruck gegen 0.

2

Bemerkung 2.32. 3.8 < c3 < 5 Wir wenden uns nun der chromatischer Zahl dichter zuf¨alliger Graphen zu. Unser erstes Zwischenziel ist der folgende Satz: Satz 2.33. Es gibt eine Funktion l0 = l0 (n) ∼ 2 log n mit i h (a) P l0 − 1 ≤ ω Gn, 12 ≤ l0 → 1

h i 2−o(1) (b) P ω Gn, 12 < l0 − 4 ≤ e−n Vorlesung 16.11.

Beweis: Sei Yl die Zufallsvariable, die die Anzahl Cliquen der Gr¨oße l in Gn, 21 z¨ahlt. Es gen¨ ugt zu zeigen, dass eine Funktion l0 ∼ 2 log n mit den Eigenschaften • limn→∞ P [Yl0 +1 ≥ 1] → 0 und • limn→∞ P [Yl0 −1 = 0] → 0 n existiert. Es gilt E [Y1 ] = n und E [Yn ] = 2−( 2 ) , und deswegen existiert ein gr¨oßtes l0 , f¨ ur das E [Yl0 ] ≥ √1n . Daraus folgt, dass E [Yl0 +1 ] < √1n und das impliziert sofort den ersten der obigen Grenzwerte: (2.4) 1 P [Yl0 +1 ≥ 1] ≤ E [Yl0 +1 ] < √ → 0. n

Als n¨achstes pr¨ ufen wir, ob f¨ ur das so definierte l0 wirklich (wie gefordert) von der Gr¨oßenordnung 2 log n ist. Es gilt: 2 n −(2l ) (2.30) l log n−l log l+O(l)− l2 + l l2 2 2 = 2l log n− 2 +o(l ) . E [Yl ] = = 2 2 (18) l 27

Setzt man nun l ∼ c log n dann folgt E [Yl ] = 2c log

2

2

n− c2 log2 n+o(log2 n) 1 n

F¨ ur l > (2 + ǫ) log n gilt dann E [Yl ] < E [Yl0 +1 ] ≤ √1n ≤ E [Yl0 ] folgt l0 ∼ 2 log n.

c

= nc log n(1− 2 )+o(log n) .

und f¨ ur l < (2 − ǫ) log n gilt E [Yl ] > n. Wegen

Weiterhin gilt: E [Yl+1 ] E [Yl ]

n −(l+1 2 ) l+1 2 l n −(2) l 2

=

F¨ ur l ∼ 2 log2 n gilt somit

=

n − l −l 2 < n · 2−l . l+1

1 E [Yl+1 ] < n · 2−l = n · 2−(2+o(1)) log2 n = n · n−2−o(1) = 1+o(1) . E [Yl ] n

(19)

Wenden wir uns nun der unteren Schranke in Aussage a) zu. Es ist zu zeigen, dass P [Yl0 −1 = 0] → 0. Wir betrachten zun¨ achst ein beliebiges l ∼ 2 log n und setzen µ = E [Yl ], S ⊆ [n], |S| = l, ( 1 S ist Clique in Gn, 21 XS := 0 sonst X XS Yl = S⊆[n],|S|=l

1

∆

=

X

S∼T

=

P [(XS = 1) ∧ (XT = 1)]

l−1 X

X

k

l

2−(2( 2 )−( 2 ))

k=2 S∼T,|S∩T |=k

= ∆1 µ2

=

l−1 X l k n l n−l · · · 2−2( 2 )+( 2 ) r k l−k k=2 k l n−l (2) l−1 l−1 X X k l−k 2 =: g(k). n l {z

k=1 |

}

g(k)

k=2

Mit einer etwas m¨ uhsamen Rechnung l¨ asst sich zeigen, dass

Pl−1

k=2

g(k) ∼ g(2). Somit folgt

[n − l]l−2 l!l(l − 1)2 l4 ∆1 ∼ g(2) = → 0. ≤ 2 µ (l − 2)![n]l 2 (n − l)2 Betrachten wir nun l = l0 − 1. Dann ist (19)

µ = E [Yl0 − 1] > n1+o(1) E [Yl0 ] ≥

1 n1+o(1) √ = n 2 +o(1) → ∞. n

Also folgt (2.12)

P [Yl0 −1 = 0] ≤

∆1 1 + 2 → 0, µ µ

und damit ist a) bewiesen. Um b) einzusehen setzen wir l := l0 − 4. Diesmal ist (19)

µ = E [Yl0 − 4] > n4+o(1) E [Yl0 ] ≥ n3+o(1) → ∞ und

∆1 n3 ∆1 = 2 µ ≥ g(2)n3 ≥ 2 ≥ 1, µ µ n 28

also ∆1 ≥ µ. Ferner ist

µ2 (n − l)2 ≥ ≥ n2−o(1) . 1 ∆ 2l4

Somit ist

(17)

µ2

2−o(1)

P [Yl0 −1 = 0] ≤ e− ∆1 ≤ e−n

,

und damit ist b) bewiesen.

2

Der obige Satz erlaubt uns nun die Bestimmung der chromatischen Zahl. Wir schreiben zur Abk¨ urzung “fast sicher” f¨ ur ein Ereignis, dessen Eintreffenswahrscheinlichkeit gegen 1 konvergiert. Satz 2.34. Fast sicher gilt: χ(Gn, 21 ) ∼

n 2 log(n) .

Beweis: Nach Satz 2.33 haben wir fast sicher ω(Gn, 12 ) ∼ 2 log(n). Aufgrund der Symmetrie k¨onnen n wir folgern, dass auch fast sicher α(Gn, 21 ) ∼ 2 log(n) gilt, woraus sich χ(Gn, 21 ) ≥ α(Gn 1 ) ∼ 2 log(n) n,

ergibt.

Es bleibt also noch χ(Gn, 21 ) ≥

n 2 log n

2

zu zeigen. Dazu beweisen wir die folgenden Aussagen:

• Fast sicher gilt: Jede Menge S ⊂ Gn, 21 der Gr¨oße m := Gr¨oße r := l0 (m) − 4 (d.h. r ∼ 2 log m).

n log2 n

hat eine stabile Menge der

n • Hat ein Graph G die oben genannte Eigenschaft, so ist χG ≤ (1 + o(1)) 2 log n.

Um die erste Behauptung einzusehen, stellen wir zun¨achst fest, dass ein Teilgraph S ⊂ Gn, 12 der Gr¨oße m dem zuf¨ alligen Graphen Gm, 12 gleichkommt, d.h. Gn, 21 [S] = Gm, 12 . Nach Satz 2.33 (b) gilt nun: h i h i 2−O(1) P α(Gn, 12 [S]) < r = P ω(Gm, 21 ) < r < e−m . Zudem betr¨ agt die Anzahl der Teilmengen S der Gr¨oße m gerade n 1+o(1) ≤ 2n = 2m . m Bei der Gleichung haben wir m = n = m1+o(1) .

n log2 n

ausgenutzt. Daraus folgt n¨amlich m = n1−o(1) und folglich

Die Wahrscheinlichkeit daf¨ ur, dass ein zuf¨ alliger Graph Gn, 12 die genannte Eigenschaft nicht besitzt, betr¨agt nun: h i 1+o(1) 2−o(1) 1+o(1) −m2−o(1) P ∃S ⊂ [n] , |S| = m mit α(Gn, 21 ) > r ≤ 2m · e−m ≤ em −→ 0. Damit ist die erste Behauptung bewiesen.

Zum Beweis der zweiten Behauptung nehmen wir also an, dass der Graph G die obige Eigenschaft besitzt und konstruieren nun eine F¨ arbung f¨ ur G. Hierzu w¨ahlen wir eine beliebige Menge S der Gr¨oße m. Darin finden wir eine stabile Menge der Gr¨oße r, die wir mit einer noch nicht vergebenen Farbe f¨arben um sie anschliessend zu entfernen. Wir wiederholen dies, solange noch mindestens m Knoten u ¨ brig bleiben. Ist dies nicht mehr der Fall, so geben wir jedem verbliebenen Knoten eine eigene Farbe. Die Anzahl ben¨ otigter Farben betr¨ agt insgesamt h¨ochstens: n n n +m∼ + r 2 log(m) log2 (m) 29

VL 14.1.

n n ) + o( log(n) 2 log(n1−o(1) ) n n = + o( 2(1 − o(1)) log(n) log(n) n = (1 + o(1)) 2 log(n) ∼

Damit ist auch die zweite Behauptung bewiesen.

30

2

3 3.1

Probabilistische Analyse F¨ arbungsalgorithmen

F¨arben ist ein hartn¨ ackiges Problem, das seit vielen Jahren intensiv untersucht wird. Es ist nicht nur NP-vollst¨ andig zu entscheiden, ob χ(G) ≤ k gilt. Unter der Annahme coRP 6= N P l¨aßt sich χ(G) nicht einmal auf Faktor n1−ε approximieren. Angesichts dieser schlechten Nachrichten im worst-case wenden wir uns der probabilistischen Analyse zu, um den average-case besser zu verstehen. Wir werden im Folgenden die chromatische Zahl zuf¨alliger Graphen studieren und zwei Ergebnisse kennenlernen, die das schlechte Abschneiden des worst-case relativieren. Wir betrachten nun den einfachen Greedy-Algorithmus, der aus dem Eingabegraphen sukzessiv inklusionsmaximale Farklassen entfernt: Greedy-Col (G) (1) k:=0 (2) repeat (3) S := ∅ (4) H := G (5) while H 6= ∅ do (6) S := S + x, x bel. Knoten aus H (7) H := H − x − N (x) (8) k := k + 1 (9) f¨ arbe Knoten in S mit Farbe k (10) G := G − S (11) until G = ∅ i h Satz 3.1. P Greedy-Col braucht weniger als (1+o(1))n log(n) Farben −→ 1. Beweis: Der Algorithmus greift sich einen beliebigen Knoten v, sortiert ihn in eine Farbklasse und demarkiert alle seine Nachbarn. Die Method of deferred decisions besagt, dass man den so verbleibenden Restgraphen (auf m Knoten) als Gm, 12 ansehen kann, da bislang lediglich die Paare Knotenpaare {v, x} ausgew¨ urfelt wurden. Behauptung: Fast sicher gilt: Der Algorithmus findet in jedem Durchlauf der ¨außeren repeatSchleife ein S := Si mit |S| ≥ (1 − o(1)) log n. Also: angenommen, wir befinden uns zu Beginn des i-ten Durchlaufs der ¨außeren repeat-Schleife, der verbleibende Restgraph G = (V, E) habe noch m ≥ n/ log2 n Knoten. Beachte, dass log m ≥ log(n/ log2 n) = log n − 2 log log n = (1 − o(1)) log n.

(20)

Der Algorithmus findet eine stabile Menge S, so dass alle Knoten in T := V \ S wenigstens einen Nachbarn in S haben. Seien s = |S|, t = |T |. P [x kennt keinen Knoten in S] = 2−s

P [x kennt mindestens einen Knoten in S] = 1 − 2−s

−s

P [alle x kennen mindestens einen in S] = (1 − 2−s )t ≤ e−2 t −s −s m −2−s t P [∃S : alle x in T kennen mind. einen in S] ≤ e ≤ ms e−2 t = e(ln m)s e−2 t s Annahme: s ≤ (1 − ǫ) log m ⇒ t = m − s = m − o(m) = m(1 − o(1)) −(1−ǫ) log m

⇒ P [∃S...] ≤ e(ln m)(log m)−2

= e(ln m)(log m)−m

−(1−ǫ)

= e(ln m)(log m)−m

ǫ−1+1

m(1−o(1))

(1−o(1)) ǫ

= e(ln m)(log m)−(1−o(1))m . 31

m(1−o(1))

Also ist die Wahrscheinlichkeit, daß in mindestens einem Schleifendurchlauf ein solches S gefunden wird, h¨ochstens ǫ ǫ ne(ln m)(log m)−(1−o(1))m = eln n+(ln m)(log m)−(1−o(1))m , und das konvergiert (siehe auch (20)) gegen Null. Fast sicher werden also in allen Durchl¨aufen Farbklassen der Gr¨ oße (20) (1 − o(1)) log m = (1 − o(1)) log n gefunden. Aus der Behauptung folgt nun, dass die Anzahl der verwendeten Farben insgsamt h¨ochstens n n n = (1 + o(1)) + (1 − o(1)) log n log2 n log n betr¨agt.

2

Korollar 3.2. Der Greedy-Algorithmus hat fast sicher eine Approximationsg¨ ute von 2. Tats¨achlich ist kein Verfahren bekannt, dass fast sicher eine bessere Approximationsg¨ ute erreicht. ¨ Ubung 3.3. Wir haben bereits Wahrscheinlichkeitsschranken f¨ ur die Abweichung einer Zufallsvariable von ihrem Erwartungswert kennengelernt (siehe z.B. 2.10). Die folgende geht auf Chernoff zur¨ uck und behandelt den Spezialfall einer Summe von unabh¨angigen 0-1-Zufallsvariablen. Pn Seien X1 , . . . , Xn unabh¨angige 0-1-Zufallsvariablen, X = i=1 Xi sowie µ := E [X]. Dann ist P [X > (1 + δ)µ] ≤

P [X < (1 − δ)µ] ≤

e

P [X > (1 + δ)µ] ≤ P [X > t] ≤ P [|X − µ| > t] ≤

eδ (1 + δ)(1+δ)

−µδ2 ) 2

µ

,

f¨ ur beliebiges δ > 0,

f¨ ur beliebiges 1 ≥ δ > 0,

,

2−(1+δ)·µ , wenn δ > 2e − 1, −t 2 , wenn t > 2e · µ, t2

2e− 3µ .

(21) (22) (23) (24) (25)

Beweis: Hier ist eine Skizze f¨ ur (21). Bitte f¨ ullen Sie die L¨ ucken. Es sei pi := P [Xi = 1]. Definiere die Zufallsvariable Y := etX mit einem zun¨achst beliebigen t ∈ R+ an. Nach einigen wenigen Umformungen erh¨ alt man n Y 1 + pi (et − 1) . E [Y ] = i=1

Nach weiteren Absch¨ atzungen (Tipp: 1 + x ≤ ex ) f¨ uhrt das zu t

E [Y ] ≤ e(e

−1)µ

.

Wende nun die Markov-Ungleichung (2.4) auf Y an, benutze Absch¨atzung f¨ ur E [Y ] und setze t := ln(1 + δ). (21) ist fertig. 2 ¨ Ubung 3.4. Ein perfektes Matching in einem Graphen ist eine Menge M von Kanten, so dass jeder Knoten des Graphen in genau einer Kante aus M enthalten ist. Entwerfen (und analysieren) Sie einen einfachen Greedy-Algorithmus, der mit Wahrscheinlichkeit mindestens 1/3 in einem zuf¨alligen Graphen Gn, 12 ein perfektes Matching findet (wenn n gerade ist). ¨ Ubung 3.5. Wir entwerfen einen einfachen, exponentiellen Algorithmus, der die chromatische Zahl eines Graphen bestimmt. a) Zeigen Sie: χ(G) = 1 + min{χ(G − S) : S ist stabile Menge in G }. b) Berechnen Sie mit Hilfe von a) und dynamischer Programmierung χ(G): also sukzessive χ(G[U ]) f¨ ur wachsende Teilmengen U . c) Zeigen Sie, dass der Aufwand durch 3n beschr¨ankt werden kann.

32

Vorlesung 23.11.04 Wir haben mit dem Algorithmus Greedy-Col in Satz 3.1 einen Algorithmus kennengelernt, der immer in kurzer Zeit eine fast sicher gute Antwort liefert. Nun wollen wir auch ein Verfahren angeben, das in erwartet kurzer Zeit eine Antwort findet, die immer gut ist. Der naheliegende Ansatz besteht darin, einen simplen Algorithmus laufen zu lassen, und in den seltenen F¨allen, in denen er zu schlecht abschneidet, durch einen teuren, exakten Algorithmus nachzubessern. Das w¨are im Durchschnitt immer noch eine gute Laufzeit. Es ist also noch die Frage zu kl¨aren, wie wir ein schlechtes Abgeschneiden unseres Algorithmus erkennt. Dabei k¨onnen zwei F¨alle eintreten: (a) Eventuell braucht Greedy viel mehr als

n 2 log(n)

Farben.

(b) Eventuell braucht der Eingabegraph viel weniger als

n 2 log(n)

Farben.

Offensichtlich k¨ onnen wir durch einfaches Nachz¨ahlen entscheiden, ob (a) eingetreten ist oder nicht. Wie aber entscheiden wir, ob (b) eingetreten ist, wenn wir doch die chromatische Zahl des Graphens gar nicht kennen? Bevor wir uns diesem Problem widmen, zun¨achst eine Definition. Definition 3.6. Der maximale Subgraph H ⊆ G mit δ(H) ≥ k heißt k-core von G und wird mit corek (G) bezeichnet. ¨ Ubung 3.7. Zeige: Der k-core eines Graphen ist eindeutig definiert. Algorithm 1: Core-Col Input: Ein Graph G = (V, E) und p ∈ R. Output: Eine F¨ arbung von G. Core-ColG,p (1) k := 10np. (2) G′ := G. (3) Setze Stack S := ∅. (4) while ∃v ∈ G′ mit dG′ (v) < k (5) S ← v. (6) G′ := G′ − v. (7) F¨ arbe G′ optimal mit Hilfe von Exact-Col (G′ ). (8) Erweitere diese F¨ arbung zu einer F¨arbung von G: (9) while S 6= ∅ (10) v := oberster Knoten von S. (11) F¨ arbe v mit kleinstm¨ oglicher Farbe.

Offenbar braucht Schritt (7) χ(G′ ) ≤ χ(G) und Schritt (8) h¨ochstens k = 10np Farben. Wir erhalten die Proposition 3.8. F¨ ur jeden Graphen G und p ≥ 1/n findet Core-Col eine F¨arbung von G mit h¨ochstens max{χ(G), 10np}. Da der Rechenaufwand mit Exact-Col im Schritt (7) groß ist, wir aber nur erwartet polynomieller verschwenden d¨ urfen, m¨ ussen wir zeigen, dass die Wahrscheinlichkeit f¨ ur einen großen corek (Gn,p ) gering ist. Proposition 3.9. Sei p ≥ 1/n and k = 10np. Dann ist P [ |corek (Gn,p )| = α ] ≤ 3−α . Beweis: Die Wahrscheinlichkeit f¨ ur die Existenz eines k-core auf α Knoten ist offenbar beschr¨ankt durch die Wahrscheinlichkeit f¨ ur die Existenz eines schwachen Subgraphen auf α Knoten und 33

β = kα/2 Kanten. Die erwartete Anzahl solcher Graphen ist gegeben durch α n 2 pβ β α

≤

en α eα2 p β α

2β

en eαp k/2 = α k

α

≤

α k2 −1 en

α

≤ (1/3)α ,

wobei wir bei dieser Absch¨ atzung α ≤ n and k ≥ e2 np ≥ e2 n n1 ≥ 7 und damit (1/e)k/2−1 ≤ 1/3 benutzt haben. 2 Wir k¨onnen nun den folgenden Satz zeigen. Satz 3.10. Es sei p ≥ 1/n. Dann hat Core-Col eine G¨ ute von h¨ochsten 10np und erwartet polynomielle Laufzeit. Beweis: F¨ ur die G¨ ute gilt: G¨ ute =

# Farben 3.8 max{χ(G), 10np} ≤ 10np. ≤ χ(G) χ(G)

(26)

Die erwartete Laufzeit eines Algorithmus (bei Eingabe Gn,p ) ist definiert durch X T (G)P [G = Gn,p ], G

wobei T (G) die Laufzeit des Algorithmus bei Eingabe G bezeichnet und die Summe u ¨ ber alle Graphen mit Knotenmenge [n] l¨ auft. Mit Ausnahme von Zeile (7) haben alle Teilschritte des Algorithmus immer polynomiale Laufzeit. Die erwartete Laufzeit von Zeile (7) betr¨agt X

T (G)P [G = Gn,p ] =

n X

X

T (G)P [G = Gn,p ]

α=1 G:|corek (G)=α|

G

=

n X

X

3α P [G = Gn,p ] =

α=1 G:|corek (G)=α|

n X

3α 3−α = 1.

α=1

2 √ Wir wollen nun die Approximationsg¨ ute von O(np) auf O( np) verbessern. Hauptschwachpunkt unserer obigen Analyse war es, dass wir in (26) die chromatische Zahl χ(G) lediglich durch 1 nach unten abgesch¨ atzt haben. Um eine nicht-triviale, effizient berechenbare untere Schranke f¨ ur χ(G) zu erhalten, ben¨ otigen wir die Lov´asz’ ϑ-Funktion, die wir nun kurz einf¨ uhren. Definition 3.11. • Eine Matrix A heißt realisierbar f¨ ur einen Graphen G, wenn a) A = (aij ) ∈ Rn×n und A symmetrisch

b) aij = 1 wenn i = j oder {i, j} ∈ / E(G)

• Sei λ1 (A) den gr¨oßten Eigenwert von A. Dann ist die Lov´ asz ϑ-Funktion definiert durch: ϑ(G) := min{λ1 (A) : A realisierbar f¨ ur G} A

Lemma 3.12. λ1 (A) = maxn x∈R

xT Ax xT x

Der Beweis des Lemmas findet sich in Standardwerken der Linearen Algebra bzw. der Numerischen Mathematik. Mit Hilfe des Lemmas folgt schnell: Proposition 3.13. F¨ ur jeden Graphen G gilt: α(G) ≤ ϑ(G).

34

 1  ..   .     1   Beweis: Sei k := α(G) und sei x =   0 .    .   ..  0 

         

k

n−k

OBdA bilden die ersten k Knoten von G eine stabile Menge der Gr¨oße k. Dann gilt aij = 1 f¨ ur 1 ≤ i, j ≤ k. F¨ ur jede Matrix A, die realisierbar f¨ ur G ist, folgt also:    T  1 · · · 1 ? ··· ? 1 1 .. .. .. ..   .   ..     . · · · .   ..   .   . ··· .      ? ··· ?    1   1 ··· 1      1   ..  0    0      ? ··· ··· ··· ··· .    .   .  ..   ...    ..   . . ··· ··· ··· ··· .  0 0 ? ··· ··· ··· ··· ? xT Ax λ1 (A) ≥ T =  T   x x 1 1  ..   ..   .   .       1   1       0   0       .   .   ..   ..  0 0   T  k 1  ..   ..   .   .       1   k       0   ?       .   .   ..   ..  =

?

0

k

= k.

Das impliziert, dass ϑ(G) = min{λ1 (A) : A realisierbar f¨ ur G} ≥ k = α(G). A

2 Den folgenden Satz geben wir ohne Beweis an. Satz 3.14. F¨ ur die Lov´ asz’ ϑ-Funktion gilt: (a) ϑ(G) kann in polynomielle Zeit berechnet werden. (b) Sei p ≫ ln6 (n)/n und a ≥ 10(n/p)1/2 . Dann ist P [ϑ(Gn,p ) ≥ a] ≤ exp(−a/30). und schauen nun, wie wir diesen verwenden k¨onnen, um die Approximationsg¨ ute von Core-Col zu verbessern. Vorlesung 24.11.

35

Algorithm 2: Approx-Col Input: Ein Graph G und p ∈ R. Output: Eine F¨ arbung von G. Approx-Col(G,p)p (1) Sei a := 12 n/p und b := 25 ln(np)/p. (2) Berechne die F¨ arbung f :=Core-Col(G, p). (3) Berechne ϑ(G). (4) if ϑ(G) < a (5) return f . (6) if ∄S ⊂ V, |S| = b mit |V \ N (S)| ≥ a − b (7) return f . (8) if ∄ stabile Menge der Gr¨ oße a (9) return f . (10) Berechne mit Exact-Col eine optimale L¨osung.

Satz 3.15. Sei p ≫ ln6 (n)/n. Dann hat Approx-Col eine Approximationsg¨ ute von h¨ochstens √ O( np) und eine erwartet polynomielle Laufzeit. Beweis: Wir weisen zuerst die G¨ ute nach und stellen fest, dass die von Approx-Col berechnete F¨arbung optimal ist, falls dies im letzten Schritt geschah. Terminiert der Algorithmus in den Schritten (4), (6) oder (8), so kann man behaupten, dass α(G) ≤ a gilt. Daraus w¨ urde G¨ ute =

Beh. 10np # Farben in f 3.8 max{χ(G), 10np} √ ≤ = 10pα(G) ≤ 10pa = O( np), ≤ χ(G) χ(G) n/α(G)

und damit das zu Zeigende folgen. Um die Behauptung zu rechtfertigen, muss lediglich die Terminierung im Schritt (6) betrachtet werden. F¨ ur einen Widerspruch nehmen wir also an, es g¨abe eine stabile Menge W der Gr¨oße a. F¨ ur eine beliebige Teilmenge S ⊂ W der Gr¨oße b gilt dann |W \ S| = a − b. Wegen der Stabilit¨at von W gilt auch W \ S ⊂ V \ N (S). Das st¨ unde nicht im Einklang mit der Zeile (6). Wir k¨onnen uns nun also der Laufzeit zuwenden. Wie zuvor gezeigt, haben die Schritte (1) − (3) erwartet polynomielle Laufzeit. Bevor wir die Laufzeit der restlichen Schritte berechen, stellen wir erst einige technische Tatsachen fest. Lassen Sie sich von den Rechnungen nicht entmutigen und machen Sie sich vor allem jeden Rechnungschritt klar. Wegen p ≫ ln6 (n)/n ist zu sehen, dass

√ np ≫ ln3 (np). Wendet man die Definition von a und b an, so ist leicht

√ √ 12 np/C − 25 ln2 (np) 11 np/C a 11 a a −b≥ − ln(np) b = ≥ = . C C p p 12 C

(27)

f¨ ur eine Konstante C und f¨ ur gen¨ ugend großes n gilt. Ferner ist:

n en a ≤ ≤ (np)a/2 = exp (ln(np)a/2) , a a b enp n en b = ≤ (np)b = exp (ln(np)b) . ≤ b 25 ln(np) b

(28) (29)

Unsere Aufmerksamkeit gilt nun der erwarteten Laufzeit des Schritts (6). Nach Satz 3.14 (b) betr¨agt diese h¨ochstens n O(1) (29) O(1) (27) exp (−a/30) n ≤ n exp (−a/30 + ln(np)b) = nO(1) b 36

¨ Ubung 3.16. Zeigen Sie unter Benutzung von (27), (28) und (29), dass die Schritte (8) und (10) polynomiale erwartete Laufzeit haben. Schritt (8): n n b(a−b) n (1 − p) nO(1) a b a−b

(28,29)

≤

(27)

≤

(27)

≤

Schritt (10): a n exp(n) (1 − p)(2 ) a

(28)

≤

=

nO(1) exp ln(np)a/2 − pb(a − b) + 2 ln(np)b nO(1) exp ln(np)a/2 − 25 ln(np) nO(1) .

exp(n) exp ln(np)a/2 − pa2 /3

11 a + 2 ln(np)b 12

√ exp(n) exp n (−48 + 6 ln(np)/ np) ≤ exp(n) exp(−n) = 1,

Damit hat Approx-Col insgesamt erwartet polynomielle Laufzeit.

2 Wir fassen hier noch einmal die Situation zusammen: Algo Greedy-Col offene Frage offene Frage Core-Col Approx-Col

3.2

Laufzeit poly. poly. erwartet poly. erwartet poly. erwartet poly.

G¨ ute fast sicher 2 fast sicher 2 − ε optimal O(np) √ O( np)

Das Travelling Salesman Problem

Beim Travelling Salesman Problem (T SP ) geht es darum, in einem vollst¨andigen gewichteten Graphen G eine k¨ urzeste Tour durch alle Knoten zu finden. Satz 3.17. Es gibt einen Algorithmus exact TSP, der in einem gegebenen Netzwerk eine optimale TSP-Tour in Laufzeit O(n2 2n ) findet.

F¨ ur die probalbilistische Analyse schr¨ anken wir das Problem ein und betrachten das T SP f¨ ur den euklidischen Fall. Unser Modell f¨ ur eine zuf¨allige TSP-Eingabe hat also die folgende Gestalt: Bezeichne mit C := {(x, y) ∈ R2 : 0 < x, y < 1} das Einheitsquadrat in der Euklidischen Ebene. Gegeben sind n Punkte x1 , . . . , xn , die unabh¨angig gleichverteilt in C liegen, wobei der Punktabstand durch die euklidische Distanz gegeben ist. Gesucht ist wie bisher eine TSP-Tour durch diese Punktmenge. F¨ ur unser Vorgehen ist das folgende Ergebnis entscheidend. Dieses wollen wir zun¨achst ohne Beweis vorstellen. Satz 3.18 (Beardwood, Halton, Hammersley). Sei ℓ∗ = ℓ∗ (x1 , . . . , xn ) die L¨ange einer optimalen Tour. Dann existiert ein β > 0 so dass √ √ ∀ǫ > 0 : P |ℓ∗ − β n| > ǫ n → 0 √ also fast sicher ℓ∗ ∼ β n. 37

Damit kommen wir nun zum Algorithm 3: Patching-Algorithmus von Karp Input: Ein Netzwerk N gegeben durch n Punkte im Einheitsquadrat wie oben, eine positive Konstante ǫ Output: TSP-Tour Tˆ TSP–Karp(N, √ǫ) (1) m := ǫ n; 1 1 (2) Teile C in M = m2 Quadrate C1 , . . . , CM der Gr¨oße m ×m ; (3) Ai := {xj : xj ∈ Ci }; (4) Finde optimale Tour Ti f¨ ur Punkte aus Ai in Ci mittels exact TSP; (5) Verklebe“ Touren Ti zu Tour Tˆ (siehe Abbildung 1); ”

Abbildung 1: Verkleben

Satz 3.19. Fast sicher weicht der Patching-Algorithmus von dem Optimum um h¨ochstens einen 10ǫ Faktor 1 + β−ǫ ab. Die erwartete Laufzeit betr¨agt O(n). ¨ ¨ Ubung 3.20. Eine optimale TSP-Tour in C hat keine Uberkreuzungen. ¨ Ubung 3.21. Jede T SP -Eingabe (d.h. n Punkte im Einheitsquadrat mit euklidischen Abst¨anden √ zwischen diesen) hat eine Tour der L¨ange h¨ochstens (2 n + 17)

Vorlesung 30.11. Beweis: Wir berechnen zun¨ achst die G¨ ute der Tour Tˆ. Sei T ∗ eine optimale Tour der L¨ange ℓ∗ , ∗ ¨ und bezeichne mit ℓi die L¨ ange der Anteile von T ∗ im Quadrat Ci . Da (siehe Ubung 3.20) die ∗ ¨ optimale Tour T keine Uberkreuzungen hat, kann man ihre Anteile in Ci durch Wegstrecken auf dem Rand des Quadrats mit abschließender Querverbindung so verbinden, dass man eine Tour von Ai erh¨alt (siehe Abbildung 2). Die L¨ange dieser Tour ist eine obere Schranke f¨ ur die vom Patching-Algorithmus gefundene Tour Ti . Die entstehenden Extrakosten, die zus¨atzlich zu ℓ∗i aufgebracht wurden, sind sicher kleiner als der Umfang plus eine Diagonale. Also ist ℓ(Ti ) ≤ ℓ∗i +

4 2 + . m m

Bei den in Schritt (4) vorgenommenen Verklebungen k¨onnen in jedem Schritt h¨ochstens √ entstehen, im letzten h¨ ochstens 2 ≤ m. Wir erhalten ℓ(Tˆ) ≤

M X

M

X √ 3 (ℓ(Ti ) + ) + 2 ≤ ℓ(Ti ) + 4m. m i=1 i=1

38

3 m

Kosten

Abbildung 2: Tour von Ai

Insgesamt ergibt sich dadurch ℓ∗ ≤ ℓ(Tˆ) ≤

M X i=1

ℓ(Ti ) + 4m ≤

M X

(ℓ∗i +

i=1

√ 6 ) + 4m = ℓ∗ + 10m = ℓ∗ + 10ǫ n. m

√ Da nach Satz 3.18 fast sicher (β − ǫ) n < ℓ∗ , folgt somit ℓ∗ 10ǫ ℓ∗ ≤ ℓ(Tˆ) < ℓ∗ + 10ǫ ℓ∗ , = 1+ β−ǫ β−ǫ womit die behauptete G¨ ute nachgewiesen ist.

Nun zur Laufzeit. Sie wird offensichtlich durch das Ausrechnen der optimalen Touren in jedem der M = ǫ2 n Quadrate dominiert, da das Verkleben sicher h¨ochstens linear in n ist. Der vorliegende Algorithmus f¨ ur exaktes TSP hat nach Satz 3.17 eine Laufzeit von Cn2 2n f¨ ur eine beliebig (große) Konstante C (das spart die O-Notation). Dann gilt f¨ ur die erwartete Laufzeit T : # "M X 2 |Ai | |Ai | · 2 T ≤ CE i=1

=C

M X i=1

=C

i h 2 E |Ai | · 2|Ai |

M X n X

i=1 k=0 n X

= CM

k=0

k 2 2k P [|Ai | = k]

k n−k n 1 1 k 2 1− . k M M 2 k

Wir verfolgen nun zwei Ziele. Erstens versuchen wir zu zeigen, dass der gr¨oßte Teil der Summe durch den ersten Summanden (k = 1) beigetragen wird. Zweitens sieht der Summand fast so aus, wie der, den man aus dem binomischen Lehrsatz kennt, wenn wir den Vorfaktor k 2 2k loswerden w¨ urden. Versuchen wir es: Wegen k ≥ 2 ist 2k(k − 1) ≥ k 2 . Wenden wir dies an und spalten die ersten beiden Summanden ab, so erhalten wir: n−1 n−k k n X 1 1 n 2 1 1− 1− + 2CM k(k − 1) . T ≤ CM 2n M M M M k k=2 Nun versuchen wir den Ausdruck k(k − 1) nk zu vereinfachen: n! k(k − 1)n! n k(k − 1) = = k!(n − k)! (k − 2)!(n − k)! k (n − 2)! n−2 = n(n − 1) . = n(n − 1) (k − 2)!(n − 2 − (k − 2))! k−2 39

Eingesetzt in die Ungleichung bedeutet dies: k n−k n X n−2 2 1 1− k−2 M M k=2 n−2−k n−2 X n − 2 2 k+2 1 1− = 2Cn + 2CM n(n − 1) M M k k=0 2 n−2 n−2−k k X n−2 2 1 2 = 2Cn + 2CM n(n − 1) 1− . M M M k

T ≤ 2Cn + 2CM n(n − 1)

k=0

Wir k¨onnen nun den binomischen Lehrsatzes f¨ ur die Summe anwenden und erhalten: n−2 2 2 1 2 T ≤ 2Cn + 2CM n(n − 1) +1− M M M n−2 1 8Cn(n − 1) 1+ = 2Cn + M M 8Cn(n − 1) n−2 ≤ 2Cn + e ǫ2 n ǫ2 n n −2 ≤ 2Cn + O( 2 eǫ ) = O(n). ǫ 2

3.3

Hamilton-Kreise

Wir beginnen mit drei einfachen, aber starken Aussagen u ¨ ber die Gr¨oße von Nachbarschaften in Gn, 21 . Proposition 3.22. Gn, 12 erf¨ ullt fast sicher die folgenden 3 Eigenschaften: (1) ∀v ∈ V :

n n n n − ≤ deg(v) ≤ + 2 50 2 50

(2) ∀v, w ∈ V : (3) ∀v, w, u ∈ V :

n 3n n 3n − ≤ |Γ(v) ∪ Γ(w)| ≤ + 4 50 4 50 n 7n n 7n − ≤ |Γ(v) ∪ Γ(w) ∪ Γ(u)| ≤ + 8 50 8 50

¨ Beweis: Wir wenden die Chernoff–Konzentrationsaussage (21) aus Ubung 3.3 an. (1) Sei v ∈ V. X = deg(v) =

n−1 X i=1

Yi ,

Yi =

P [¬ (1) f¨ ur v]

1, vi ∈ Γ(v) , 0, sonst

= ≤ 2.1

≤

≤

µ = E [X] =

h ni n Pr X − > 2 50 n 1 Pr |X − µ| > − 50 2 2 −( n − 1 ) 50 2 3· n−1 2 2·e

2 · e−c·n 40

n−1 n 1 = − 2 2 2

X

P[A∪B]≤P[A]+P[B]

P [∃v : ¬ (1) f¨ ur v]

≤

P [¬ (1) f¨ ur v]

v

n→∞

n · 2 · e−c·n −−−−→ 0

≤ (2) Seien v, w fest. X = |Γ(v) ∪ Γ(w)| = P [Yi = 0] =

n−2 X

Yi , wo Yi =

i=1

1, vi ∈ Γ(v) ∪ Γ(w) 0, sonst

1 3 3 , P [Yi = 1] = ⇒ µ = E [X] = (n − 2) · 4 4 4

Rest analog zu (1) (3) analog. ¨ ¨ Ubung 3.23. Uberpr¨ ufen Sie die Rechnungen zu (2) und (3). 2 Wir werden im Folgenden nun annehmen, dass ein Graph G gegeben sei, der die Eigenschaften (1),(2),(3) erf¨ ullt. Ferner sei n groß genug. Unser Algorithmus wird sich aus drei Phasen zusammensetzen, die wir anschließend angeben. Algorithm 4: Hamiltonkreis Ham(G) (1) do Phase 1 so lange wie m¨oglich (2) do Phase 2 (3) do Phase 3 so lange wie m¨oglich

Ziel ist es, zu zeigen, dass Ham in G immer einen Hamiltonkreis findet. Phase 1: Pfad Erweiterung“, siehe Abbildung 3. ” x

i) P

w

v

z ii)

z

v

y

x

y

P

Abbildung 3: Phase 1 Proposition 3.24. Pfad P hat nach Phase 1 mind. Beweis: Aufwand: i) O(n) ii) O(n2 ) ⇒ O(n3 ) insgesamt. L¨ange: 41

7n 8

−

n 50

Knoten und Aufwand O(n3 )

i) geht nicht mehr: ⇒ Γ(v) ∪ Γ(w) ⊂ P,

3n n − ≤ |Γ(v) ∪ Γ(w)| ≤ |P | 4 50

ii) geht nicht mehr: Es sei z ∈ Γ(v) ∩ P und y Vorg¨anger von z. ⇒ Γ(v) ∪ Γ(w) ∪ Γ(y) ⊂ P,

n 7n − ≤ |Γ(v) ∪ Γ(w) ∪ Γ(y)| ≤ |P | 8 50 2

Vorlesung * Phase 2: Kreis schließen“, siehe Abbildung 4. ” y v x

u

u

w

w

u w

Abbildung 4: Phase 2 Proposition 3.25. Phase 2 klappt immer, kostet O(n) und f¨ uhrt zu einem Kreis der L¨ange mind. 7n n − − 1. 8 50 Beweis: Γ(v) ∩ P ≥

n 2

−

n 50 ,

denn nach Phase 1 liegen alle Nachbarn von v auf P . Sei y ∈ Γ(v) ∩ P und x ∈ Γ(v) ∪ Γ(w).

Jedes y macht einen Pfadplatz f¨ ur x unm¨oglich. Bleiben also noch n n 7n n n n 3n |P | − ≥ − − − + = Pl¨atze f¨ ur x. 2 50 8 50 2 50 8 n 3n n n n Es gibt aber |(Γ(u) ∪ Γ(w)) ∩ P | ≥ 3n 4 − 50 − |V \ P | ≥ 4 − 50 − 8 + 50 = Widerspruch.

5n 8

Aufwand: Pr¨ ufe f¨ ur jede Kante x, y auf Pfad ob Kanten zu v, u, w da ⇒ O(n).

−

24 50

viele x.

2

n Phase 3: Sei C ein Kreis mit 7n 8 − 50 − 1 ≤ |C| ≤ n − 1. Ferner sei eine (beliebige, aber feste) Orientierung auf C gegeben – es gibt also Nachfolger und Vorg¨anger.

i) Wenn es einen Knoten x ∈ V \ C und eine Kante {y, z} von C gibt, so dass x zu y und z verbunden ist, dann erweitere C durch C := C − {y, z} + {y, x} + {x, z}. ii) Wenn es einen Knoten x ∈ V \ C mit zwei Nachbarn a, y ∈ C gibt, so dass der Nachfolger b von a mit dem Nachfolger z von y verbunden sind, dann erweitere C durch C := C − {a, b} − {y, z} + {a, x} + {x, y} + {b, z}. Siehe auch Abbildung 5. 42

y z

z x x

y

b a

Abbildung 5: Phase 3

Proposition 3.26. Sei x ∈ V \ C. Dann funktioniert Schritt i) oder ii) von Phase 3. Phase 3 erzeugt also einen Hamilton-Kreis und kostet O(n3 ). Beweis: Angenommen, Regel i) funktioniert nicht. Knoten x hat n/2 − n/50 Nachbarn, von denen h¨ochstens |V \ C| ≤ n/8 + n/50 + 1 nicht auf C liegen, also hat x mindestens 3n/8 − 2n/50 − 1 Nachbarn auf C. F¨ arbe diese Knoten rot. Da Regel i) nicht funktioniert, haben rote Knoten auf dem Kreis mindestens Abstand 2. F¨arbe jeden Nachfolger eines roten Knoten gr¨ un. Es gibt also mindestens 3n/8 − 2n/50 − 1 gr¨ une Knoten. Seien u, v, w drei gr¨ une Knoten. Wieder gilt: |(Γ(u) ∪ Γ(v) ∪ Γ(w)) ∩ C| ≥

n 7n n n n 6n 2n 7n − − |V \ C| ≥ − −( + + 1) ≥ − − 1, 8 50 8 50 8 50 8 50

also muss einer der drei gr¨ unen Knoten (nennen wir ihn b) zu einem weiteren gr¨ unen Knoten von C (nennen wir ihn z) verbunden sein. Sei a Vorg¨anger von b (also b Nachfolger von a, also ist a rot), und sei y Vorg¨ anger von z (also z Nachfolger von y, also ist y rot). Dann funktioniert Regel ii). Aufwand: Sei x ∈ V \ C fest. Die Durchf¨ uhrung von Regel i) kostet O(n) Operationen: man teste alle Kanten {y, z} des Kreise. Regel ii) kostet O(n2 ): teste alle Paare a, y von Nachbarn von x auf dem Kreis, ob ihre jeweiligen Nachfolger b, z mit einander verbunden sind. Die Addition von x kostet also O(n2 ), und wir m¨ ussen h¨ ochstens n/8 + n/50 + 1 addieren. 2 Satz 3.27. Der Algorithmus Ham findet in Gn, 21 fast sicher einen Hamiltonkreis. Die Laufzeit betr¨agt O(n3 ). Beweis: Propositionen 3.22 bis 3.26.

2

Vorlesung 1.12.

3.4

Perfekte Matchings

Ein perfektes Matching auf einem Graphen ist eine Teilmenge seiner Kanten, so dass diese Kanten paarweise disjunkt sind (nicht inzidieren) und jeder Knoten in einer Matchingkante enthalten ist (jeder Knoten ist u ¨ berdeckt oder gematcht“). Offensichtlich kann es ein perfektes Matching nur ” bei gerader Knotenzahl geben. Der √ zur Zeit beste deterministische Algorithmus f¨ ur perfekte Matchings erreicht eine Laufzeit von O( nm). Unser Ziel ist in diesem Abschnitt ein Algorithmus, der mit erwarteter Laufzeit O(n log n) fast sicher ein perfektes Matching in Gn, 21 (n gerade) findet (was auch impliziert, dass Gn, 21 fast sicher ein perfektes Matching hat). Der Algorithmus teilt sich in zwei Phasen, wobei die erste einen recht großen Teil der Knoten matcht und die zweite versucht, u ¨ ber ,,augmentierende” Pfade der L¨ange 3 die wenigen u ¨ brig gebliebenen aufzusammeln. 43

Algorithm 5: Phase 1 (Greedy–Matching) Input: Ein Graph auf der Knotenmenge [n] Output: Ein Matching M Match–1(G) (1) S := [n]; M := ∅; stop := false; (2) repeat (3) i := min S; (4) if S ∩ Γ(i) 6= ∅ (5) j := min S ∩ Γ(i); (6) S := S \ {i, j}; (7) M := M ∪ {ij}; (8) else (9) stop = true; (10) until stop

Notation: Es seien im folgenden M = {x1 y1 , . . . , xp yp } mit xi < yi die Menge der Matchingkanten, X = {x1 , . . . , xp } die Menge der linken“ Matchingknoten, ” Z = {z1 , . . . , z2q } die Menge der nicht u ¨berdeckten Knoten und ∗ z ∈ Z der nicht u ¨ berdeckte Knoten mit dem kleinsten Index,

nachdem Phase 1 abgeschlossen ist. Es gilt offenbar 2q = n − 2p. Es sei k ≥ 2 ein fester Parameter, den wir sp¨ater bestimmen k¨ onnen. Man beachte, dass Phase 1 alleine offenslichtlich nicht fast sicher ein perfektes Matching finden k¨ onnen wird, da es f¨ ur die letzte Maching–Kante nur eine Chance von 1/2 gibt. Wir stellen nun einige Eigenschaften des Matchings (bzw. des Algorithmus) nach (bzw. in) Phase 1 fest. Dabei setzen wir wieder voraus, dass wir nach der Methode der deferred decisions“ ” vorgehen, d.h., wir w¨ urfeln eine Kante des Gn, 12 erst aus, wenn wir sie das erste Mal benutzen wollen, was uns die Unabh¨ angigkeit unserer Entscheidungen sichern soll. (1) Jedes Knotenpaar wird in Phase 1 h¨ ochstens einmal befragt, ob es eine Kante hat, da ja der kleinere von beiden danach entweder u ¨ berdeckt ist oder der Algorithmus stoppt. (2) Die Wahrscheinlichkeit, dass man erst im Versuch Nummer t einen Nachbarn von v findet (und nicht vorher) ist (1/2)t = 2−t . (3) Sei k > 0 beliebig. F¨ ur einen Knoten u sei das Ereignis Au wie folgt definiert: Au = {#{j : xj < u < yj } ≥ k log n}. D.h. Au tritt ein, falls der Knoten u von sehr vielen Matchingkanten u ¨ berspannt wird. Wir wollen nun beweisen, dass Au ziemlich unwahrscheinlich ist. Sei dazu u ∈ X ∪ Z fest. Damit nun soviele Matchingkanten u urfen alle linken Knoten (xj ) dieser Kanten ¨ ber u hinweggehen, d¨ nicht zu u adjazent sein, denn als sie ihren Matchingpartner gesucht haben, war u (noch) nicht gematcht, da der Algorithmus die zuk¨ unftigen linken Knoten streng aufsteigend w¨ahlt und x ∈ X ∪ Z. Die Wahrscheinlichkeit daf¨ ur l¨asst sich aber wie in 2 bestimmen. P [Au ] ≤ 2−k log n = n−k (4) Die Wahrscheinlichkeit, dass es einen Knoten u gibt, so dass Au eintritt, ist nun sicher durch die Summe obiger Wahrscheinlichkeit u ¨ber alle Knoten beschr¨ankt. X P [∃u ∈ X ∪ Z : Au ] ≤ n−k ≤ n · n−k = n1−k u∈X∪Z

(5) Sei f¨ ur einen Matchingkantenindex i das Ereignis Bi wie folgt definiert: Bi = {yi − xi ≥ 2k log n} f¨ ur 1 ≤ i ≤ p. 44

D.h. Bi tritt gerade ein, wenn die Kante xi yi l¨anger als 2k log n ist. Auch Bi ist recht unwahrscheinlich, denn daf¨ ur dass xi nicht schon vorher einen Partner gefunden hat, kann es nur zwei Gr¨ unde geben: Er war zu dem potentiellen Partner nicht adjazent oder dieser war schon u ur mindestens k log n der 2k log n − 1 u ¨ berdeckt. Damit muss f¨ ¨ bersprungenen Knoten einer der beiden F¨ alle zutreffen. Es gibt also k log n Matchingkanten, die ihren Ursprung links von xi haben (die Wahrscheinlichkeit daf¨ ur haben wir in 3 berechnet) oder es fehlen k log n Kanten (dieses Ereignis nennen wir jetzt F und haben seine Wahrscheinlichkeit schon in 2 berechnet). P [Bi ] ≤ P [Axi ∨ F ] ≤ P [Axi ] + P [F ] ≤ 2n−k (6) Die Wahrscheinlichkeit, dass es eine Kante xi yi gibt, so dass Bi eintritt, ist nun sicher durch die Summe obiger Wahrscheinlichkeit u ¨ber alle Knoten beschr¨ankt. P [∃i ∈ [p] : Bi ] ≤ n · 2n−k = 2n1−k (7) Sei C das folgende Ereignis: C = {z ∗ ≤ n − 2k log n}. Das heißt C tritt ein, falls der Algorithmus relativ fr¨ uh abbricht. Es gilt wie in 5, dass alle Knoten rechts von z ∗ schon u ¨ berdeckt oder nicht zu z ∗ adjazent sind. Da jedoch z ∗ nicht fest ist, sch¨atzen wir sicherheitshalber wie in 4 ab. P [C] ≤ P [(∃u : Au ) ∨ F ] ≤ P [∃u : Au ] + P [F ] ≤ n1−k + n−k ≤ 2n1−k (8) Aus dem vorherigen Punkt folgt unmittelbar, dass in Phase 1 fast sicher ein Matching erzeugt wird, dass mindestens n − O(log n) Knoten u ¨ berdeckt. (9) F¨ ur xi yi ∈ M und z ∈ Z, z > yi sind sicher die Kanten xi z und yi z noch nicht ausgew¨ urfelt worden, da xi seinen Matchingpartner vor z fand und yi gar nicht suchen musste. (10) F¨ ur xi yi ∈ M , z ∈ Z beliebig und z ∗ > yi sind aufgrund des vorherigen Punktes und wegen z > z ∗ sicher die Kanten xi z und yi z noch nicht ausgew¨ urfelt worden. (11) F¨ ur alle i ∈ [p] gilt xi < 2i. Da alle xi vor dem ersten ungematchten Knoten liegen (Phase 1 arbeitet streng sequentiell) und nicht mehr yj als xj links von xi liegen k¨onnen (f¨ ur jedes Paar liegt x links von y), muss der Index eines x-Knotens offenbar mindestens doppelt so groß sein, wie seine eigene Nummer. Algorithm 6: Phase 2 (Augmentierende Pfade der L¨ange 3) Input: Ein Graph auf der Knotenmenge [n] und ein Matching M mit p Kanten xi yi und 2q ungematchten Knoten zi Output: Ein (hoffentlich gr¨ oßeres) Matching M Match–2(G, M ) (1) t := 1; (2) for i := 1 to q (3) stop := false; (4) repeat (5) if xt z2i−1 ∈ E(G) and yt z2i ∈ E(G) (6) M := M \ {xt yt } ∪ {xt z2i−1 , yt z2i }; (7) stop = true; (8) t := t + 1 (9) until stop or t = p + 1 (10) if t = p + 1 (11) halt

Wir nehmen im folgenden an, dass Phase 1 verlief, ohne dass eines der Ereignisse in 4, 6 oder 7 eintraf (und wollen dieses Ereignis eine erfolgreiche Phase 1 (P1 ) nennen). Phase 2 ist offensichtlich erfolgreich (im Matchen aller Knoten), wenn nie “halt” aufgerufen wird. Eine erfolgreiche Phase 2 heißt entsprechend P2 . 45

(12) Sei i ≤ n3 . Daraus folgt mit 11: xi ≤ 2n ur kein i das Ereignis Bi eingetreten ist, folgt 3 . Da f¨ + 2k log n. Da C auch nicht eingetreten ist, wissen wir auch: z ∗ ≥ n − 2k log n. daraus: yi ≤ 2n 3 ∗ Das heißt f¨ ur ein ausreichend großes n gilt: yi < z . (13) Aufgrund von 10 und 12 gilt also f¨ ur alle i ≤ n3 und alle z ∈ Z, dass die Kanten xi z und yi z noch nicht ausgew¨ urfelt wurden. Damit l¨asst sich die Wahrscheinlichkeit f¨ ur einen Fehlschlag (halt) von Phase 2 bestimmen. P [Anzahl der Versuche f¨ ur z2i−1 , z2i

3k log n k log n 27 3 = > 3k log n] ≤ 4 64 k log n ! 1 = o(n−k ) =o 2

(14) Daraus folgt unmittelbar: P [¬P2 |P1 ] = o((2k log n)n−k ) (15) P [P1 ∧ P2 ] = P [P1 ] · P [P2 |P1 ]

= (1 − O(n1−k )) · (1 − o((k log n)n−k )) = 1 − O(n1−k )

Satz 3.28. Die Algorithmen Phase 1 und Phase 2 finden mit Wahrscheinlichkeit 1 − O(n1−k ) ein perfektes Matching in O(nk log n) Schritten.

Vorlesung **

3.5

Knapsack

Beim Knapsack-Problem sind n Objekte {1, ..., n} mit positiven Gewichten w1 , ..., wn und positiven Nutzen p1 , ..., pn gegeben. Unter Einhaltung einer Gewichtskapazit¨at c soll der Nutzen maximiert werden. Das heisst wir suchen X X max { pi | wi ≤ c}. S⊆[n]

i∈S

i∈S

(Das Problem ist N P −vollst¨ andig, hat ein P AS (polynomial approximation scheme)). Um das Optimum zu bestimmen kann man naiverweise alle 2n Teilmengen berechnen. Wir werden im Folgenden zeigen, dass es gen¨ ugt, bestimmte Teilmengen zu berechnen und dass diese Methode bei geeignetem Eingabemodell zu guter Laufzeit f¨ uhrt. Definition 3.29. Wir sagen, dass eine Teilmenge S ⊆ [n] eine Teilmenge T ⊆ [n] dominiert (geschrieben S ≻ T ), wenn P wi ≤ w(T ) := i∈T wi , und P P • p(S) := i∈S pi ≥ p(T ) := i∈T pi .

• w(S) :=

P

i∈S

S heißt dominierend (pareto-optimal), wenn es von keiner Menge dominiert wird. Offenbar kann T nicht optimal sein, wenn S ≻ T gilt. Es gen¨ ugt also, die dominierenden Mengen zu finden. Dies kann man mit dynamischer Programmierung effizient tun. Sei dazu S(i) := {S ⊆ [i] : S ist dominierend innerhalb P([i]) } aufsteigend nach Gewicht sortiert. Si+1 kann aus Si wie folgt berechnet werden: 46

• Sei S(i) = {S1 , S2 , ..., Sk } und S ′ (i) = {S1 + (i + 1), S2 + (i + 1), ..., Sk + (i + 1)}. • Merge S(i) und S ′ (i) und entferne in S(i) ∪ S ′ (i) jedes Element, das durch ein anderes dominiert wird und erhalte so S(i + 1). ¨ Ubung 3.30. Es ist leicht, zu u ufen, dass dadurch tats¨achlich S(i + 1) berechnet wird. ¨ berpr¨ Wir beleuchten ur i ∈ [n] sei die Funktion P dieses Verfahren nun von einer anderen Seite: F¨ fi : [0, c] → [0, ni=0 pi ] durch fi (t) := max{p(S) : w(S) ≤ t} S⊆[i]

definiert. Hierbei stellt t eine zwischenzeitliche Gewichtsschranke dar und fi (t) ist eine nicht fallende Treppenfunktion. ¨ Ubung 3.31. fi (t) springt genau an den Stellen springt, die dominierenden Mengen “entsprechen”. Das bedeutet insbesondere, dass die Anzahl der Stufen gerade |S(i)| entspricht. Wie oben kann man auch hier fi+1 (t) aus fi (t) gewinnen, indem man die folgende Rechnung ausf¨ uhrt: F¨ ur jedes t setzen wir fi′ (t) := fi (t − wi+1 ) + pi+1 (d.h. wir nehmen das Element i + 1 hinzu). Dann erhalten wir fi+1 durch fi+1 (t) := max{fi (t), fi′ (t)}. Dieses Vorgehen ist analog zum ersten. Pn Satz 3.32. Sei s(i) = |S(i)|. Dann l¨asst sich in O( i=1 s(i)) = O(n·s(n)) eine optimale Knapsack L¨osung berechnen. Beweis: Wie bereits gesehen k¨ onnen wir in O(s(i)) die Menge S(i) berechnen. Ist S(n) berechnet, dann teste alle Mengen S ∈ S(n). 2 ¨ Ubung 3.33. Es l¨aßt sich eine einfache Instanz finden, bei der S(n) = P([n]) gilt. Im worst-case bringt uns die obige Betrachtung also nichts. F¨ ur den Fall, bei dem man die Nutzen p1 , ..., pn zuf¨allig gleichverteilt aus [0, 1] w¨ahlt, k¨onnen wir allerdings zeigen, dass die erwartete Gr¨ oße von S(n) lediglich O(n3 ) betr¨agt. Um das zu beweisen, zeigen wir, dass in die erwartete Treppenh¨ohe relativ groß ausf¨allt: Sei P(n) = {S1 , S2 , ..., Sm } mit m = 2n , und es gelte 0 = w(∅) = w(S1 ) ≤ w(S2 ) ≤ .... ≤ w(Sm ) = w([n]). Ferner sei Pu := p(Su ) und △u := maxv∈[u] Pv − maxv∈[u−1] Pv f¨ ur u ∈ [2, m]. △n ist also die H¨ohe der Treppenstufen und man u ¨berlege sich leicht, dass aus der Dominanz von Su auch △u > 0 folgt. ¨ ¨ Ubung 3.34. Uberpr¨ ufen Sie folgende einfache Sachverhalte: • S1 ist immer dominierend • △u ≥ 0 • Su ist dominierend ⇒ △u > 0. Beweis: W¨are n¨ amlich △u = 0, dann ∃v ∈ [u − 1] mit Pv ≥ Pu . Wegen v < u ist w(Sv ) ≤ w(Su ). Das bedeutet Sv ≻ Su und Su w¨ are nicht dominierend. 2 Lemma 3.35. Seien die w1 , ..., wn beliebig gegeben und seien die p1 , ..., pn zuf¨allig gleichverteilt aus [0, 1] gew¨ahlt. Dann gilt ∀u ∈ [2, m] : E [△u |△u > 0] ≥ d.h. die Stufen der Treppenfunktion sind relativ hoch.

47

1 , 32n2

Beweis: Nach Markovs Ungleichung gilt E [X] ≥ k0 · P [X ≥ k0 ] f¨ ur ein festes k0 und es bleibt 1 1 1 E [△u |△u > 0] ≥ · P △u ≥ |△u > 0 ≥ 2 2 16n 16n 32n2 f¨ ur ein festes u zu zeigen. Dazu bezeichnen wir das Ereignis ,,△u ≥ 1/16n2” der K¨ urze wegen mit A, das Ereignis ,,△u > 0” mit B und werden zeigen, dass P [A|B] ≥ 1/2 gilt. F¨ ur v ∈ [u − 1] sei Xv = Su \ Sv und Yv = Sv \ Su und wir nehmen OBdA Su = {1, ..., k} an. Wegen △u ≥ α ⇔ Pu ≥ Pv + α, ∀v ∈ [u − 1] ist P [A|B]

=

=

"

P ∀v ∈ [u − 1] : "

P ∀v ∈ [u − 1] :

X

i∈Su

X

i∈Xv

pi ≥ pi ≥

X X 1 |∀v ∈ [u − 1] : pi > pi pi + 2 16n

X

i∈Su

i∈Sv

i∈Sv

#

X X 1 |∀v ∈ [u − 1] : pi > pi pi + 2 16n

X

i∈Xv

i∈Yv

i∈Yv

#

(30)

Nun benutzen wir die Tatsache, dass p1 , ..., pk gleichverteilt gew¨ahlt waren und folgern 1 |B P ∃j ∈ [k] : pj ≤ 4n

≤ ≤ =

Das Ereignis ,,∃j ∈ [k] : pj ≤ eintritt, d.h.:

1 4n ”

k X 1 P pj ≤ |B 4n j=1 k X 1 P pj ≤ 4n j=1 k 1 ≤ 4n 4

(31)

wollen wir nun mit C bezeichnen und annehmen, dass es nicht pj ≥

1 4n

∀j ∈ [k].

¨ Ubung 3.36. Allgemein gilt f¨ ur die Ereignisse A, B, C: P [A|B] ≥ P A|B ∩ C¯ − P [C|B].

In (31) ist P [C|B] ≤ 1/4 gezeigt worden. Es bleibt also noch P A|B ∩ C¯ ≥ 3/4 nachzuweisen. P P Dazu setzen wir Lv := i∈Xv pi und Rv := i∈Yv pi und rufen ins Ged¨achtnis, dass Xv ⊆ {1, ..., k} und wegen △u > 0 auch Xv 6= ∅ ∀v ∈ [u − 1] gilt. Unter der Annahme, dass C nicht eintritt, enth¨ alt jedes Xv somit ein Element pj , f¨ ur das Lv ≥ pj ≥ 1/4n gilt Die Variablen p1 , ..., pk seien nun gew¨ahlt und C sei nicht eingetreten. Damit ist Lv nun eine Konstante und Rv ist eine Zufallsvariable, deren Gr¨oße vom Ausw¨ urfeln der pk+1 , ..., pn abh¨angt. Wir definieren nun A

:= {(pk+1 , ..., pn ) ∈ [0, 1]n−k : ∀v ∈ [u − 1] : Rv ≤ Lv −

B

:= {(pk+1 , ..., pn ) ∈ [0, 1]n−k : ∀v ∈ [u − 1] : Rv < Lv }.

(Man beachte, dass das Ereignis C bereits in A und B kodiert ist.) Da nun aus (30) A

≡ (∀v ∈ [u − 1] : Lv ≥ Rv +

B

≡ (∀v ∈ [u − 1] : Lv > Rv ) 48

1 ), 16n2

1 }, 16n2

folgt und die p1 , ..., pk ausgew¨ urfelt sind, ist V ol(A) P A|B ∩ C¯ = . V ol(B)

F¨ ur den letzten Term ist die untere Schranke von

3 4

zu zeigen.

Wir holen nun zum letzten Schlag aus und definieren nun Bǫ := {(pk+1 , ..., pn ) ∈ [0, 1 − ǫ]n−k : ∀v ∈ [u − 1] : Rv ≤ (1 − ǫ)Lv } Es ist B0 = B und V ol(Bǫ ) = (1 − ǫ)n−k V ol(B), da p~ ∈ B genau dann gilt, wenn (1 − ǫ) · p~ ∈ Bǫ . W¨ahlt man nun ǫ := 1/4n, so ist wegen Lv ≥ 1/4n Rv ≤ (1 −

1 1 1 . )Lv ≤ Lv − Lv ≤ Lv − 4n 4n 16n2

F¨ ur ǫ := 1/4n ist also Bǫ ⊆ A und durch Umstellen der Gleichung (1 − ǫ)n−k V ol(B) (1 − ǫ(n − k))V ol(B) n−k )V ol(B) (1 − 4n 1 (1 − )V ol(B) 4 3 V ol(B). 4

V ol(A) ≥ V ol(Bǫ ) = ≥ = ≥ = erhalten wir das Behauptete.

2

Damit ist die meiste Arbeit getan und der Beweis des Hauptsatzes wird wenig M¨ uhe kosten. Satz 3.37. Seien die w1 , ..., wn beliebig gegeben und seien die p1 , ..., pn zuf¨allig gleichverteilt aus [0, 1] gew¨ahlt. Ist s = |S(n)|, dann ist E [s] = O(n3 ). Beweis: Das Lemma 3.35 besagt, dass die erwartete Stufenh¨ohe relativ groß ist. Da p1 , ..., pn zuf¨allig gleichverteilt aus [0, 1] gew¨ ahlt war und der erwartete Gesamtnutzen folglich n/2 betr¨agt, kann es also nicht so viele Stufen, bzw. nicht so viele dominierende Mengen geben. Wir geben dieser Idee nun eine formale Rechfertigung: Zun¨achst gilt offensichtlich P1 = erhalten

P

i∈S1

pi = 

E [Pm ] = E 

P

X

i∈∅

i∈[n]

pi = 0 und Pm =



pi  =

P

i∈Sm

n 2

Ferner ist "

E [Pm ] = E ( =

m X

u=2

≥

m X

u=2

max Pv − max Pv ) + P1

v∈[u]

v∈[u−1]

E [△u |△u > 0] · P [△u > 0]

m 1 X P [△u > 0]. 32n2 u=2

49

#

pi =

P

i∈[n]

pi . Wir

Daraus folgt E [s(n)] =

1+

m X

u=2 m X

P [Su domimierend] P [△u > 0]

≤

1+

≤ =

1 + 32n2 E [Pm ] 1 + 16n3 ,

u=2

was zu beweisen war.

2

50

4

Probabilistische Existenzbeweise

Vorlesung 14.12. In diesem Kapitel wollen wir – nach der probabilistischen Analyse von Algorithmen – eine weitere Anwendung der Theorie zuf¨ alliger diskreter Strukturen betrachten, n¨amlich probabilistische Existenzbeweise. Historisch gesehen stellen sie den Ursprung des Gebiets dar. Die beiden grundlegenden Prinzipien der sogenannten probabilistischen Methode“ lassen sich ” wie folgt, beispielhaft f¨ ur den Fall von Graphen, formulieren. Es sei X = X(Gn,p ) eine Zufallsvariable. (I) Wenn P [X(Gn,p ) = t] > 0, dann existiert ein Graph G mit X(G) = t. (II) Wenn E [X(Gn,p )] = t, dann existiert ein Graph G+ mit X(G+ ) ≥ t und es existiert ein Graph G− mit X(G− ) ≤ t. Wir beginnen mit einem sehr einfachen Beispiel. Satz 4.1. Jeder Graph G = (V, E) enth¨alt einen bipartiten aufspannenden Subgraphen H = (V, E ′ ) mit |E ′ | ≥ |E|/2. Beweis: F¨arbe jeden Knoten in V zuf¨ allig mit Farbe 0 oder 1, jeweils mit Wahrscheinlichkeit 1/2. Sei E ′ die Teilmenge der Kanten aus E, die unterschiedlich gef¨arbte Knoten hat, und betrachte den bipartiten aufspannenden Subgraphen H := (V, E ′ ). Die Wahrscheinlichkeit daf¨ ur, dass eine bestimmte Kante {u, w} ∈ E auch in E ′ liegt, betr¨agt 1/2, und mittels Linearit¨at des Erwartungswerts ergibt sich |E ′ | = |E|/2. Mit Hilfe des obengenannten Prinzips (II) existiert also ein bipartiter Subgraph mit den gew¨ unschten Eigenschaften. 2

4.1

Einfarbige Cliquen, arithmetische Progressionen und Hyperkanten

F¨ ur eine Zahl k ∈ N bezeichnet die Ramseyzahl R(k) die kleinste nat¨ urliche Zahl n mit der Eigenschaft, dass jede Kantenf¨ arbung des vollst¨ andigen Graphen Kn mit zwei Farben einen einfarbigen Kk erzeugt. Statt einer Zweif¨ arbung kann man auch die An- bzw. Abwesenheit der Kanten im Kn betrachten. Die Eigenschaft ist dann ¨ aquivalent zu der Existenz einer Clique oder einer stabilen Menge der Gr¨oße k. Beispiel: 5 < R(3) ≤ 6. Dies besagt, dass ein K5 ohne einfarbigen K3 gef¨arbt werden kann, w¨ahrend jede Zweif¨ arbung von K6 ein einfarbiges Dreieck besitzt. Wieso existiert u ur ¨ berhaupt ein solches kleinstes n? Wir wollen zun¨achst eine obere Schranke f¨ R(k) kennenlernen. Satz 4.2. F¨ ur k ∈ N gilt: R(k) ≤ 22k−2 . Beweis: F¨ ur k = 0 oder k = 1 gilt die Aussage offensichtlich. Sei also k ≥ 2 und eine beliebige rot/blau-F¨arbung der Kanten des vollst¨ andigen Graphens Kn auf n = 22k−2 Knoten gegeben. Wir m¨ ussen zeigen, dass sie einen einfarbigen Kk enth¨alt. Setze V0 := [n] und w¨ ahle v0 ∈ V0 beliebig. Wir definieren eine Folge von Knoten v0 , v1 . . . und Teilmengen V0 , V1 . . . wie folgt. Wenn vi ∈ Vi gew¨ahlt, dann betrachte rote und blaue Nachbarn von vi innerhalb von Vi . Bezeichne die gr¨ oßere der beiden Mengen mit Vi+1 und w¨ahle beliebiges vi+1 ∈ Vi+1 . Daraus folgt, dass |Vi+1 | ≥ |Vi |/2, und wegen n = 22k−2 folgt damit, dass wir somit eine Folge v0 , . . . , v2k−2 konstruieren k¨ onnen. Wenn mindestens die H¨alfte der Knoten vi mehr rote 51

als blaue Nachbarn in Vi hat, dann haben wir einen roten Kk gefunden, andernfalls einen blauen. 2 Die beste bekannte obere Schranke ist von der Gr¨oßenordnung ke. Satz 4.3. R(k) > n, falls

2k 2 √ . k

Nun zu der unteren Schran-

1−(k) 2 2 < 1.

n k

Beweis: Sei n gegeben. Wir f¨ arben die Kanten des Kn zuf¨allig mit Wahrscheinlichkeit 12 und zeigen, dass eine zul¨ assige F¨ arbung (d.h. eine ohne einfarbigen Kk ) existiert bzw. dass die Wahrscheinlichkeit f¨ ur eine zul¨ assige F¨ arbung positiv ist. Sei dazu S ⊆ [n] eine Teilmenge der Gr¨ oße k, und bezeichne AS das Ereignis S ist einfarbig“. Es ” gilt nun: k

k

P [AS ] = 2−(2) · 2 = 21−(2) und die Wahrscheinlichkeit, dass eine Teilmenge einfarbig ist, ist:   X _ P [AS ] AS  ≤ P S⊆[n]

S⊆[n]

k n = · 21−(2) k

Ist n nun so gew¨ ahlt, dass der letzte Term kleiner als Eins ist, so gilt:     _ ^ AS  > 0 A¯S  = 1 − P  P S⊆[n]

S⊆[n]

und somit ist eine zul¨ assige F¨ arbung m¨ oglich.

2 k 2

Proposition 4.4. Sei k ≥ 2. Dann gilt R(k) ≥ 2 . k

Beweis: Sei n ≤ 2 2 . Dann gilt:

2 2k /2 21+k/2 21+k/2 nk 21+k/2 n 1−(k2) ≤ 1. ≤ = 2 < 2 /2 2 /2 k k k! 2 k! 2 k! k 2

Bemerkung 4.5. Durch etwas genauere Rechnung folgt: R(k) ≥

k √ e 2

k 2

·2 .

Eine k-arithmetische Progression (k-AP) ist eine Folge der Form (a, a + d, a + 2d, ..., a + (k − 1) · d) f¨ ur gewisse nat¨ urliche Zahlen a, d ≥ 1. Mit der Zahl W (k) bezeichnet man die kleinste nat¨ urliche Zahl n, f¨ ur die jede rot-blau F¨ arbung von [n] eine einfarbige k-AP erzeugt. Beispiel: W (2) = 3, d.h. jede Zweif¨ arbung von {1, 2, 3} enth¨alt eine arithmetische Progression der L¨ange 2. ¨ Ubung 4.6. Bestimmen Sie W (3). Satz 4.7. W (k) > n, falls n2 2−k < 1. Beweis: Sei n gegeben. Wieder konstruieren wir eine F¨arbung zuf¨allig und notieren mit S eine k-AP und mit AS das Ereignis S ist einfarbig“. Ein ¨ahnliches Vorgehen wie oben ergibt: ” P [AS ] = 2 · 2−k = 21−k 52

2

n Weiterhin ist die Anzahl der k-AP ist durch 2 beschr¨ankt, da eine k-AP durch ihre ersten beiden n Zahlen eindeutig bestimmt ist und es 2 M¨oglichkeiten gibt, diese auszuw¨ahlen. Daraus erh¨alt man: h_ i X ≤ P [AS ] P AS

n2 1−k 2 2 = n2 2−k ≤

Ist auch hier der letzte Term kleiner als Eins, erhalten wir mit i i h_ h^ P AS > 0 A¯S = 1 − P

wieder das gew¨ unschte Ergebnis, da f¨ ur diesen Fall eine F¨arbung ohne einfarbige k-AP m¨oglich ist. 2 Durch leichte Umformung erhalten wir das k

Korollar 4.8. W (k) ≥ 2 2 . Vorlesung 15.12.

Ein Hypergraph H = (V, E) heißt k-uniform, wenn E ⊆ Vk , also alle Kanten genau k Knoten enthalten. H heißt dar¨ uber hinaus k-regul¨ ar, wenn jeder Knoten in genau k Kanten enthalten ist. Proposition 4.9. F¨ ur jeden k-regul¨aren k-uniformen Hypergraph H = (V, E) gilt: |V | = |E|. Beweis: klar.

2

Satz 4.10. Sei H = (V, E) ein k-regul¨arer k-uniformer Hypergraph. Wenn n21−k < 1, dann exitisert eine rot-blau Knotenf¨arbung von H, so dass keine Kante einfarbig ist. Beweis: Sei n gegeben. Wieder konstruieren wir eine F¨arbung zuf¨allig in dem jeder Knoten mit Wahrscheinlichkeit 1/2 rot oder blau gef¨arbt wird. F¨ ur die i-te Kante sei Ai das Ereignis i-te ” Kante ist einfarbig“. Ein ¨ ahnliches Vorgehen wie oben ergibt: P [Ai ] = 2 · 2−k = 21−k P

h_

und somit P

Ai

i

h^

≤

n X

P [Ai ] = n21−k < 1,

i=1

i i h_ AS > 0 A¯S = 1 − P

wieder das gew¨ unschte Ergebnis, da f¨ ur diesen Fall eine F¨arbung ohne einfarbige Kanten m¨oglich ist. 2 Bemerkung 4.11. Die obige Bedingung ist ¨aquivalent dazu, dass k > 1 + log n. Tats¨achlich gilt die Aussage aber schon f¨ ur konstante k, unabh¨angig von n. F¨ ur k = 2 ist nat¨ urlich der C5 ein Gegenbeispiel, und auch f¨ ur k = 3 gibt es Gegenbeispiele. F¨ ur k ≥ 4 ist sie aber richtig, und wir werden im folgenden Kapitel eine Methode kennenlernen, mit der wir dies (immerhin) f¨ ur k ≥ 10 beweisen werden. ¨ Ubung 4.12. Finden Sie einen 3-regul¨aren 3-uniformen Hypergraphen auf 7 Knoten, die man nicht so rot-blau f¨arben kann, dass keine Kante einfarbig ist.

53

4.2

Das Lovasz Local Lemma

Bislang haben wir wie folgt abgesch¨ atzt: h^ i h_ i X A¯S = 1 − P AS ≥ 1 − P P [AS ] > 0.

Diese Absch¨atzung ist immer m¨ oglich, egal ob die Ereignisse AS abh¨angig sind oder nicht. Wenn wir die Abh¨ angigkeiten kontrollieren k¨ onnen, dann erlaubt das sogenannte Lovasz Local Lemma (LLL) bessere Schranken. Als Vorbereitung f¨ ur das Lemma ben¨otigen wir die Definition 4.13. Sei A1 , ..., An Ereignisse. G = ([n], E) heißt Abh¨angigkeitsgraph f¨ ur A1 , ..., An , wenn die folgende Eigenschaft gilt: {i, j} 6∈ E ⇒ Ai ist unabh¨angig von Aj . Nun werden wir das LLL angeben und beweisen. Anzumerken ist, dass es von diesem viele Variationen und Versch¨ arfungen gibt. Wir werden hier folgende Variante zugrunde legen: Lemma 4.14 (Lovasz Local Lemma - LLL). Sei G ein Abh¨angigkeitsgraph f¨ ur A1 , ..., An , und seien (i) P [Ai ] ≤ p, ∀i ∈ {1, ..., n} (ii) degG (i) ≤ d, ∀i, d ≥ 1 (iii) 4dp ≤ 1. Dann ist P

"

n ^

#

A¯i > 0.

i=1

Beweis: Die Behauptung



P Ai |

^

j∈S



A¯j  ≤ 2p, ∀S ⊆ [n]

soll uns das Leben erleichtern. Diese zeigen wir durch Induktion u ¨ ber s = |S|. Die leere Menge macht einen erfolgreichen Induktionsanfang. G¨onnen wir ihr die Freude und betrachten nun, ohne Einschr¨ ankung, S = {1, ..., s}. Da die Aussage trivial (mit Wahrscheinlichkeit 0) f¨ ur den Fall i ∈ S ist, k¨ onnen wir ebenfalls ohne Einschr¨ankung annehmen, dass i = n. Ferner seien A1 , . . . , At mit t ≤ d die Ereignisse in A1 , . . . , As , die von An abh¨angig sind. (32) annehmen. Man vollziehe nun die folgende Rechnung nach:

P An ∧ A¯1 ∧ ... ∧ A¯t |A¯t+1 , ..., A¯s P A¯1 ∧ ... ∧ A¯t |A¯t+1 , ..., A¯s

=

= = =

¯1 ∧...∧A ¯s ] P[An ∧A ¯ ¯ P[At+1 ∧...∧As ] ¯1 ∧...∧A ¯s ] P[A ¯ ¯s ] P[At+1 ∧...∧A

P An ∧ A¯1 ∧ ... ∧ A¯s P A¯1 ∧ ... ∧ A¯s P An |A¯1 ∧ ... ∧ A¯s   ^ P An | A¯j . j∈S

Dieser technische Aufwand bringt den Vorteil, dass wir nun f¨ ur den ersten Term die obere Schranke 2p nachweisen k¨ onnen. F¨ ur den Z¨ ahler ergibt sich n¨amlich: (32) P An ∧ A¯1 ∧ ... ∧ A¯t |A¯t+1 ∧ ... ∧ A¯s ≤ P An |A¯t+1 ∧ ... ∧ A¯s = P [An ] ≤ p, 54

und f¨ ur den Nenner: P A¯1 ∧ ... ∧ A¯t |A¯t+1 ...A¯s

Insgesamt erh¨ alt man



P An |

≥

1−

IV

l=1

t X

≥

1−

=

1 − 2pt ≥ 1 − 2pd ≥ 1 −

^

j∈S

und somit die Induktionsbehauptung.

t X P Al |A¯t+1 ∧ ... ∧ A¯s



2p

l=1

1 1 = . 2 2

p A¯j  ≤ 1 = 2p 2

Mit diesem Ergebnis beansprucht der Beweis des Lemmas nur noch drei Zeilen: # "n n Y ^ ¯ P A¯i |A¯1 ∧ .... ∧ A¯i−1 = P Ai i=1 n Y

i=1

Beh.

≥

i=1

(1 − 2p) > 0,

da 2p < 4p ≤ 4dp ≤ 1.

2

Mit Hilfe des Lovasz Local Lemma wollen wir nun die bisher erzielten Schranken verbessern. Satz 4.15. Sei k ≥ 10 und H = (V, E) ein k-regul¨arer k-uniformer Hypergraph. Dann exitisert eine rot-blau Knotenf¨arbung von H, so dass keine Kante einfarbig ist. Beweis: Wieder konstruieren wir eine F¨ arbung zuf¨allig in dem jeder Knoten mit Wahrscheinlichkeit 1/2 rot oder blau gef¨ arbt wird. F¨ ur die i-te Kante sei Ai das Ereignis i-te Kante ist einfarbig“. ” Wir u ufen die Voraussetzungen des LLL: ¨ berpr¨ (i) P [Ai ] ≤ 21−k , ∀i ∈ {1, ..., n} (ii) degG (i) ≤ k(k − 1), ∀i (iii) 4k(k − 1)21−k ≤ 1. Wie man leicht nachpr¨ uft, ist (iii) f¨ ur k ≥ 10 erf¨ ullt. Also folgt, dass # "n ^ ¯ Ai > 0, P i=1

und somit existiert die gesuchte F¨ arbung ohne einfarbige Kanten.

2

¨ Ubung 4.16. Zeigen Sie mit Hilfe des LLL: n 1−(k) Wenn 4 k2 k−2 2 2 < 1, dann R(k) > n.

¨ Ubung 4.17. Zeigen Sie mit Hilfe des LLL: Wenn 4nk21−k < 1, dann W (k) > n.

Anwendung des LLL - Ramseyzahl Zur Bestimmung von R(k) m¨ ussen wir zuvor f¨ ur ein gegebenes n den Abh¨angigkeitsgraph G = (V, E) konstruieren und setzen: V E

:= :=

{S ⊆ [n] : |S| = k} und {{S, T } : |S ∩ T | ≥ 2} 55

Offenbar ist dieser ein Abh¨ angigkeitsgraph, da {S, T } 6∈ E(G) ⇒ AS und AT haben keine Kante gemeinsam ⇒ AS ist unabh¨angig von AT . Bleibt nun noch p und d zu bestimmen. Sei dazu S ⊆ [n] eine beliebige, aber feste Teilmenge der Gr¨oße k: k

(i) p := 21−(2) = P [AS ], n (ii) d := k2 k−2 ≥ degG (S) = #{T : |S ∩ T | ≥ 2}.

W¨ahrend (i) klar ist, sieht man (ii) ein, wenn beachtet wird, dass es aussreicht, 2 Elemente aus S und die verbliebenen k − 2 Elementen beliebig aus [n] auszuw¨ahlen, um alle Nachbarn von S in G zu erhalten. Nun kann das Local Lemma direkt angewendet werden und wir erhalten das n 1−(k) Korollar 4.18. Wenn 4 k2 k−2 2 2 < 1, dann R(k) > n. Damit haben wir

n k

aus Satz 4.3 auf 4

Korollar 4.19. R(k) >

√ k 2 2 e k2 .

k 2

n k−2

verbessert.

Anwendung des LLL - arithmetische Progressionen Wir gehen auch hier analog vor und konstruieren zu gegebenen k und n den Abh¨angigkeitsgraph G = (V, E): V E

:= :=

{S ⊂ [n] : Sist eine k-AP} , {{S, T } : S ∩ T 6= ∅}

und

Bleibt noch p und d zu bestimmen. Sei S dazu eine k-AP. Wir setzen (i) p := 21−k = P [AS ], (ii) d := k · k ·

n k

≥ {T : S ∩ T 6= ∅}.

Auch hier ist (i) klar. Um alle Nachbarn einer Menge S zu bestimmen und dadurch (ii) einzusehen, bedenke man, dass ein Nachbar der (k-elementigen) Menge S ein Element mit dieser teilen muss. Da der Nachbar selbst k Elemente hat und durch das gemeinsame Element und einen Abstand (wof¨ ur es h¨ochstens nk geben kann) eindeutig bestimmt ist, ist d die behauptete obere Sschranke. Nun k¨onnen wir wieder das Local Lemma anwenden und erhalten das Korollar 4.20. Wenn 4nk21−k < 1, dann W (k) > n, womit n2 aus Satz 4.7 auf 8nk verbessert worden ist. Korollar 4.21. W (k) ≥

2k 8k .

¨ Ubung 4.22. Eine k-AP heißt bunt, wenn alle k Terme unterschiedliche Farben haben. • Finden Sie eine F¨arbung von N mit unbeschr¨ankt vielen Farben, die keine bunte 4-AP enth¨alt. • Finden Sie eine F¨arbung von N mit unbeschr¨ankt vielen Farben, die keine bunte 3-AP enth¨alt. 56

4.3

Graphen mit hoher chromatischer Zahl aber ohne kurze Kreise

Wir hatten bereits die triviale Ungleichung ω(G) ≤ χ(G) kennengelernt und festgestellt, dass f¨ ur ungerade Kreise ω = 2 und χ = 3 gilt. Der folgende Satz zeigt, dass sich die Parameter beliebig weit entfernen k¨ onnen, und dass die entsprechenden Graphen nicht nur kein Dreieck, sondern auch keinen “kurzen” Kreis enthalten. Mit anderen Worten: sie sehen lokal so einfach aus wie ein Baum, haben aber global eine hohe Komplexit¨ at (im Sinne einer hohen chromatischen Zahl). Satz 4.23. Zu jedem fest gew¨ahlten k, l ∈ N existiert ein Graph G∗ mit χ(G∗ ) ≥ k, der keine Kreise der L¨ange ≤ l enth¨alt. Beweis: Im Folgenden nennen wir einen Kreis der L¨ange h¨ochstens l einen “kurzen Kreis”. W¨ahle γ ∈ R so, dass 0 < γ < 1/l und G = Gn,p mit p = nγ−1 . Sei X die Anzahl kurzer Kreise in G. Es gilt: l X X ni pi = (nγ )i ≤ lnγl = o(n), E [X] ≤ i=3

und daraus folgt mit Hilfe der Markov Ungleichung, dass

P [X ≥ n/2] ≤ E [X]/(n/2) = o(1).

(33)

G hat also eventuell kurze Kreise, aber nicht viele. Wie ist es um die chromatische Zahl bestellt? Setze x := ⌈ p3 ln n⌉. Es gilt P [α(G) ≥ x] ≤

x n (1 − p)(2 ) ≤ nx e−px(x−1)/2 = (ne−p(x−1)/2 )x = o(1), x

(34)

wegen p(x − 1)/2 > (ln n). Sei n nun so groß, dass die Wahrscheinlichkeiten in (33) und (34) beide kleiner 1/2 sind. Somit existiert ein Graph G mit weniger als n/2 kurzen Kreisen und α(G) < x. Entferne aus jedem kurzen Kreis in G einen Knoten und erhalte den neuen Graphen G∗ . Dieser hat noch mindestens n/2 Knoten, keine kurzen Kreise und seine chromatische Zahl erf¨ ullt: χ(G∗ ) ≥

|G∗ | n/2 n np nγ ≥ ≥ = = ≥ k, ∗ α(G ) α(G) 2x 6 ln n 6 ln n

f¨ ur n groß genug.

2

Vorlesung 21.12.

4.4

Listenf¨ arbungszahl

Definition 4.24. N χl (G) := min{k ∈ N : ∀L : V → ∃ zul¨ assige F a ¨rbung f : V → N mit f (i) ∈ L(i)}. k Die so definierte Zahl nennt man die listenchromatische Zahl des Graphen G. Beispiel.

χl (K3,3 ) > 2

q {1,2} {1,2} q @ A A@ {1,3} q A@q {1,3} @A @A Aq {2,3} {2,3} q @

Wenn der linke obere Knoten mit der Farbe 1 gef¨arbt wird, muss der rechte obere Knoten die Farbe 2 und der rechte mittlere Knoten die Farbe 3 annehmen. Dann kann der linke untere Knoten nicht mehr zul¨assig gef¨arbt werden. Auch die Wahl von Farbe 2 als Startfarbe f¨ uhrt zu keiner erlaubten F¨arbung.

57

Ist die listenchromatische Zahl χl (G) = k, so gibt es insbesondere eine F¨arbung f¨ ur die Liste L : V → {1, . . . , k}, d.h. der Graph ist k-f¨arbbar und wir erhalten die Proposition 4.25. χ(G) ≤ χl (G). Dass die Umkehrung nicht gilt, zeigt das obige Beispiel. Wir werden mit der Probabilistischen Methode u.a. zeigen, dass die Absch¨ atzung χ(G) ≤ χl (G) beliebig schlecht ist. Satz 4.26. a) ∀g ∈ N gibt es einen Graph G mit χ(G) = 2 und χl (G) ≥ g. d→∞

b) Es gibt eine Funktion g(d) mit g(d) −→ ∞, so dass f¨ ur jeden bipartiten Graphen G mit δ(G) ≥ d gilt: χl (G) ≥ g(d). Beweis: Da a) eine Konsequenz von b) ist, reicht es letzteres zu zeigen. Sei s ≥ 2 beliebig und sei ein beliebiger bipartiter Graph H = (A ∪ B, E), mit minimalem Grad 4 δ(H) ≥ s4 ss , |A| ≥ |B| gegeben. Wir zeigen die Existenz von Listen der L¨ange s (mit Farben aus der Menge {1, . . . , s4 }), die keine zul¨ assige F¨arbung von H erlauben. Dies w¨ urde χl (G) > s zeigen. F¨ ur den bipartiten Graphen H = (A ∪ B, E) vereinbaren wir, dass eine Zuweisung von Listen an alle Knoten in A bzw. B eine A-Familie bzw. B-Familie genannt werden soll. Ferner nennen wir 4 einen Knoten v ∈ A von der B-Familie B umringt, wenn durch B jede der ss m¨oglichen Listen bei mindestens einem Nachbarn von v auftaucht. Falls B mindestens die H¨alfte der Knoten aus A umringt, so nennen wir B schlecht. Der Beweis verl¨ auft nun in zwei Schritten: (i) Ist δ(H) ≥ s4

s4 s

, so gibt es eine schlechte B-Familie.

(ii) F¨ ur jede schlechte B-Familie B gibt es eine A-Familie A, so dass H auf A ∪ B nicht zul¨assig f¨arbbar ist. 4 zu (i): Wir w¨ ahlen f¨ ur jeden Knoten aus B eine der ss m¨oglichen Listen zuf¨allig gleichverteilt und bezeichnen mit der Zufallsvariable Xv die Anzahl der Listen der L¨ange s, die bei keinem Nachbar von v ∈ A auftreten.

Es gilt nun:

P [Eine feste Liste taucht bei einem festen Nachbarn auf] = P [Eine feste Liste taucht bei keinem Nachbarn auf] ≤ 1 − und folglich

1 s4 s

.

1 d .

s4 s

P [v nicht umringt] = P [Xv ≥ 1]

!d 4 1 s ≤ E [Xv ] ≤ 1 − s4 s s

−

d s4 s

4 4 4 < 2s e ( ) ≤ 2s e−s 1 . < 2

Damit ist die erwartete Anzahl nicht umringter Knoten echt kleiner als 12 |A| und eine schlechte Familie muss existieren. 58

zu (ii): Sei B also eine schlechte B-Familie. Betrachte F¨arbungen fB , die zun¨achst nur die Knoten in B f¨arben, dort aber die Vorgaben aus B respektieren. Es gibt genau s|B| solche F¨arbungen. Gegeben fB , dann heißt eine Farbe i f¨ ur v ∈ A erlaubt, wenn fB bei keinem Nachbarn von v die Farbe i benutzt hat. Offensichtlich ist fB genau dann bez¨ uglich einer A-Familie A auf A erweiterbar, wenn A f¨ ur jeden Knoten v ∈ A mindestens eine erlaubte Farbe bereit h¨alt.

Andererseits hat ein von B umringter Knoten v ∈ A h¨ochstens s − 1 erlaubte Farben aus {1, . . . , s4 }. H¨ atte v n¨ amlich s (oder mehr) erlaubte Farben dann w¨ urde das eine vollst¨andige s-Liste darstellen, die bei einem Nachbarn von v liegt. Eine Farbe wurde von f zur F¨arbung genutzt und w¨ are demnach f¨ ur v verboten. Wenn wir nun eine eine A-Familie A zuf¨allig ausw¨ahlen, dann gilt: Wenn v ∈ A von B umringt, dann P [eine zuf. Farbe i ist f¨ ur v erlaubt] ≤ ⇒

s−1 s4

P [zuf. Liste f¨ ur v enth¨alt erlaubte Farbe] ≤

1 s · (s − 1) < 2. s4 s

Da mindestens 12 |A| Knoten von B umringt sind, folgt P [f ist auf A zul¨assig erweiterbar] ≤ P [ jeder umringte Knoten in A hat erlaubte Farbe in seiner Liste ] |A| 1 2 < = s−|A| ≤ s−|B| . s2 Z¨ahlen wir nun mit der Zufallsvariable Z die Anzahl zul¨assiger F¨arbungen von B, die auf A erweiterbar sind und summieren u ¨ber alle m¨oglichen F¨arbungen von B, dann ist E [Z] < s|B| · s−|B| = 1. Das beweist, dass es Familien A und B von Listen der L¨ange s gibt, die keine zul¨assige F¨arbung haben. 2 ¨ ¨ Ubung 4.27. Diese Ubung ist ein Ausflug in die Welt der planaren Graphen. Ein Graph G = (V, E) heißt planar, wenn er sich so in die Ebene einbetten (“zeichnen”) l¨asst, dass sich Kanten nicht ¨ uberschneiden – sie ber¨ uhren sich also h¨ochstens in (gemeinsamen) Endpunkten. Ein dergestalt eingebetteter Graph besitzt also neben Knoten V und Kanten E auch Gebiete R, womit wir die durch die Einbettung der Kanten entstandenen Zusammenhangskomponenten der Ebene bezeichnen wollen. Das (einzige) unbeschr¨ankte Gebiet nennt man auch das ¨außere Gebiet. a) Beweisen Sie (z.B. durch Induktion ¨ uber |E|) die Euler Formel: F¨ ur jeden zusammenh¨angenden planaren Graphen gilt: |V | − |E| + |R| = 2. b) Folgern Sie: Wenn G planar, dann |E| ≤ 3n − 6. c) Zeigen Sie: 1/n ist eine Schwellenwertfunktion f¨ ur die Eigenschaft von Gn,p , planar zu sein. Der ber¨ uhmte Vierfarbensatz besagt, dass χ(G) ≤ 4 f¨ ur jeden planaren Graphen G. Es gibt allerdings planare Graphen G mit χl (G) = 5. d) Zeigen Sie, dass f¨ ur jeden planaren Graph G gilt: χl (G) ≤ 5. Anleitung: Man zeige zun¨achst per Induktion ¨ uber |V | die folgende Aussage: Sei G ein planarer Graph, der aus einem Kreis C = (v1 , v2 , . . . , vr , v1 ) und Knoten und Kanten innerhalb von C besteht, so dass das Innere von C nur aus Gebieten besteht, die durch genau drei Kanten berandet sind. Seien v1 und v2 bereits mit Farben 1 und 2 gef¨arbt. Sei ferner L(v) eine Liste von mindestens 3 Farben, falls v ∈ C − {v1 , v2 }, und von genau 5 Farben, falls v ∈ V − C. Dann l¨asst sich die F¨arbung von v1 und v2 zu einer Listenf¨arbung von G erweitern.

59

4.5

Kleine Dreiecke in der Ebene: Heilbronn’s Problem

Wir betrachten das Einheitsquadrat U in der Euklidischen Ebene. Gesucht sind Punktkonfigurationen, so dass jedes aufgespannte Dreieck einen m¨oglichst großen Fl¨acheninhalt hat. Satz 4.28. Es gibt n Punkte P1 , . . . , Pn in U , so dass der Fl¨acheninhalt jedes Dreiecks Pi Pj Pk mindestens 1/(100n2) betr¨agt. Beweis: Wir wollen hier erst eine deterministische Konstruktion kennenlernen. Betrachte statt ur n prim und die n Punkte Pi = (i, i2 mod n) mit U zun¨achst das Gitter [0, n − 1]2 ⊆ Z⋉ 2 f¨ i = 0, 1, 2, . . . , n − 1. Man kann einsehen, dass keine drei Punkte Pi , Pj , Pk auf einer Geraden y = xm + b liegen (weil sonst die Parabel x2 − xm − b = 0 drei Nullstellen h¨atte), somit haben alle Dreiecke positiven Fl¨ acheninhalt. Da die Punkte alle auf Gitterpunkten liegen, m¨ ussen die Fl¨acheninhalte von der Form k/2 mit k ∈ N+ sein (das folgt entweder als Korollar aus dem Satz von Pick oder ganz elementar durch Erg¨ anzen des Dreiecks zu einem Rechteck), und haben damit mindestens Fl¨ acheninhalt 1/2. Nach Reskalierung um den Faktor n − 1 ergibt sich dadurch ein Mindestfl¨acheninhalt von 1/(2(n − 1)2 ). Vorlesung 22.12. Nun zu dem probabilisitischen Ansatz. Als Vor¨ uberlegung werfen wir zun¨achst nacheinander drei Punkte P, Q, R in das Einheitsquadrat U , zuf¨allig gleichverteilt. Angenommen, P sei bereits positioniert, werfe nun Q hinterher. Die Zufallsvariable x bezeichne den Abstand von Q zu P . Es gilt P [b ≤ x ≤ b + ∆b] ≤ π(b + ∆b)2 − πb2 = 2πb∆b + π(∆b)2 F¨ ur db = ∆b → 0 wollen wir das durch P [b ≤ x ≤ b + ∆b] ≤ 2πbdb absch¨atzen. Sei nun also auch Q positioniert, mit Abstand b zu P , und wir werfen R hinterher. Sei A die Zufallsvariable, die den Fl¨acheninhalt des Dreiecks P QR bezeichnet und h der Abstand von R zur Gerade durch P und Q. Dann ist A = hb/2 und daher √ √ 4ǫ 2 P [A ≤ ǫ|dist(P, Q) = b] ≤ 2h 2 ≤ . b

Somit ist P [A ≤ ǫ] ≤

Z

0

√ 2

√ 4ǫ 2 2πbdb = 16πǫ. b

Wir werfen nun zuf¨ allig gleichverteilt 2n Punkte P1 , . . . , P2n nach U . Ein Dreieck Pi Pj Pk mit Fl¨ach A ≤ 1/(100n2) =: ǫ wird als klein bezeichnet. Sei X die Anzahl kleiner Dreiecke, dann ist (2n)3 16π 2n E [X] ≤ 16πǫ ≤ < n. 3 6 100n2 Es gibt also 2n Punkte mit weniger als n kleinen Dreiecken. Entferne nun als jedem kleinen Dreieck einen Punkt, und wir sind fertig. 2 Die zuletzt angegebene probabilistische Konstruktion ist zwar schlechter (um einen konstanten Faktor) als die zuerst angegebene probabilistische, l¨asst sich aber mit einigem Aufwand verbessern, so dass man die Existenz von Punktmengen mit minimalem Dreiecksfl¨acheninhalt Ω(ln n/n2 ) zeigen kann. Das ist zur Zeit der Rekord, die beste bekannte obere Schranke ist O(1/n8/7 ).

4.6

Nachtr¨ age zur Evolutionsgeschichte von Gn,p

¨ Wir hatten bereits eine Vielzahl von Phasen¨ uberg¨angen untersucht. Hier noch einmal ein Uberblick, sowie einige Erg¨ anzungen, die wir hier ohne Beweis angeben. Zusammenhangsstruktur. Komponente von Gn,p .

Wir bezeichnen mit L1 = L1 (Gn,p ) die maximale Gr¨oße einer

60

• p ≪ n1 Gn,p ist ein Wald. B¨ aume auf k Knoten tauchen bei p = n−k/(k−1) auf. • p → nc , c < 1 Gn,p besteht aus sogenannten unizyklischen Komponenten, die (jeweils) nur h¨ochstens einen Kreis haben. Es gilt: L1 = O(log n). λ • p = 1±ǫ n , mit ǫ ∼ n1/3 . Man spricht von der kritischen Phase, hier ist bereits L1 = Θ(n2/3 ).

• p → nc , c > 1 Hier gilt nun schon L1 = Θ(n), und zwar L1 ∼ (1 − x(c)/c)n mit x ∈ (0, 1) und xe−x = c. Alle anderen Komponten haben O(ln n) Knoten. • p = lnnn + nc Isolierte Knoten verschwinden, Gn,p wird zusammenh¨angend, und bekommt (wenn n gerade) ein perfektes Matching. n + nc • p = lnnn + (k − 1) ln ln n Knoten von Grad ≤ k − 1 verschwinden, Gn,p wird k-fach zusammenh¨angend, und bekommt (wenn k = 2) einen Hamiltonkreis.

Angesichts des rapiden Wachstums der gr¨oßten Komponente bei p ∼ 1/n, also kurz vor, innerhalb und nach der kritischen Phase spricht man auch von dem double jump: L1 springt gr¨oßenordnungsm¨aßig erst von ln n auf n2/3 , und dann auf n. Durch eine geeignete Zeitlupe (Reskalierung), l¨asst sich aber auch dieses Verhalten “verstetigen”. 1 • p = 1−ǫ n , ǫ → 0 aber ǫ ≫ n1/3 . Sogenannte subkritsche Phase, beachte: wir sind hier bereits im Bereich p ∼ 1/n. Es gilt: L1 ∼ 2ǫ−2 ln(ǫ3 n) ≪ n2/3 , und die gr¨oßten Komponeten sind B¨aume. 1 • p = 1+ǫ n , ǫ → 0 aber ǫ ≫ n1/3 . Sogenannte superkritsche Phase, auch hier ist nat¨ urlich noch p ∼ 1/n. Es gilt: L1 ∼ 2ǫn ≫ n2/3 , alle anderen Komponenten haben h¨ochstens O(n2/3 ) Knoten. Die gr¨oßte Komponente hat ∼ 2ǫn + 23 ǫ3 n Kanten.

Man beachte, dass die Kantenwahrscheinlichkeit in der subkritischen Phase noch nicht hoch genug ist, um die großen Komponenten mit 2ǫ−2 ln(ǫ3 n) Knoten zu verschmelzen: addiert man, um etwa von p1 = (1 − 2ǫ)/n zu p2 = (1 − ǫ)/n zu gelangen, Kanten mit Wahrscheinlichkeit ǫ/n hinzu, dann ist die erwartete Anzahl Kanten zwischen zwei solchen Komponenten 4ǫ−4 ln2 (ǫ3 n)ǫ 4 ln2 (ǫ3 n) = , n ǫ3 n 1 , also ǫ3 n → ∞, noch gegen 0 strebt. Dies ¨andert sich erst in der kritischen Phase, was f¨ ur ǫ ≫ n1/3 3 wenn ǫ n konstant ist.

Chromatische Zahl. Wir hatten bereits gesehen, dass bei p = 1/n durch das Auftreten ungerader Kreise die chromatische Zahl χ(Gn,p ) von 2 auf 3 springt. Weiterhin hatten wir gesehen (Proposition 2.31), dass es zu jedem l ≥ 3 eine Konstante cl gibt, so dass χ(Gn,p ) > l f¨ ur p > cnl . Hier sind entscheidende Fragen aber noch offen: Warum springt die chromatische Zahl? Wann genau springt sie? Bez¨ uglich des “warums” gab es eine Vermutung, dass die chromatische Zahl vielleicht gleichzeitig mit dem Auftreten des l-cores von l auf l + 1 springt (vorher kann sie offensichtlich nicht). Dies wurde aber widerlegt: so taucht beispielsweise der 3-core bei p ≈ 3.35/n auf, aber χ(Gn,p ) ≤ 3 f¨ ur p ≤ 3.84/n. F¨ ur p ≥ 4.99/n ist bekannt, dass χ(Gn,p ) ≥ 4, was aber auch bez¨ uglich des “wann genau” noch Platz f¨ ur Verbesserungen l¨ asst, und zwar sowohl f¨ ur Existenzaussagen (“es muss eine F¨arbung geben”), wie auch f¨ ur Algorithmen (die fast sicher eine solche finden).

61

F¨ ur dichte Graphen hatten wir gesehen, dass χ(Gn, 12 ) ∼ n/2 log n gilt. Allgemeiner weiss man, dass np f¨ ur C/n < p = o(1) : χ(Gn,p ) ∼ , 2 ln np n f¨ ur p = const : χ(Gn,p ) ∼ , 2 logb n wobei C eine gen¨ ugend große Konstante ist und b = 1/(1 − p). Automorphismen. Ein Automorphismus eines Graphens G = (V, E) ist eine Bijektion φ : V → V mit {x, y} ∈ E ↔ {φ(x), φ(y)} ∈ E, also eine Art den Graphen “umzunumerieren”, ohne ihn zu ver¨andern. Es ist klar, dass G nicht-trviale Automorphismen hat, solange G isolierte Knoten hat. Tats¨achlich fallen die Schwellenwerte f¨ ur die beiden Eigenschaften zusammen: Satz 4.29. F¨ ur

ln n n

≪p≤

1 2

hat Gn,p fast sicher keinen nicht-trivialen Automorphismus.

62

5

Randomisierte Algorithmen

Vorlesung 11.1.

5.1

Min-Cut

Beim Min-Cut-Problem stellt sich die Frage nach einer Bipartition eines Multi-Graphen G = (V, E), so dass die Anzahl der zwischen den Partitionen verlaufenden Kanten minimal ist. Die zur Zeit schnellsten deterministischen Algorithmen l¨osen dieses Problem in O(mn log(n2 (m))). Das Ziel dieses Abschnitts ist es, einen randomisierten Algorithmus vorzustellen, der einen Min-Cut mit hoher Wahrscheinlichkeit findet und eine geringere Komplexit¨at aufweist. ¯ (oder kurz C) ein Cut, also eine Bipartition der Knotenmenge Bezeichne im folgenden (C, C) ¯ und sei E(C, C) ¯ die Kantenmenge zwischen den Partitionen. Ferner bezeichne G/{x, y} V = C ∪ C, den Graphen, der aus Kontraktion der Kante {x, y} ∈ E entsteht. Hierbei werden in G die Knoten x und y zum Knoten xy kontrahiert, welcher mit allen Nachbarn von x und y (samt ihrer Vielfachheiten) verbunden ist. Die durch die Kanten zwischen x und y verursachten Schleifen (loops) werden entfernt. Betrachten wir nun einen einfachen Ansatz, der die Kontraktion und den Zufall zusammenf¨ uhrt. Algorithm 7: Contract Input: Ein Multi-Graph G = (V, E) Output: Ein Cut C von G Contract(G) (1) while |V | > 2 (2) W¨ ahle eine Kante e = {x, y} aus G zuf¨allig gleichverteilt. (3) G := G/{x, y}. (4) Bezeichne mit x und y die zuletzt verbleibenden Knoten in G. (5) C := Knoten, die zu x kontrahiert wurden. (6) C¯ := Knoten, die zu y kontrahiert wurden.

Proposition 5.1. (i) Contract durchl¨auft die while-Schleife genau n − 2 mal. (ii) Contract findet einen Cut im urspr¨ unglichen Graphen. (iii) W¨ahrend Contract verkleinert sich der Min-Cut nie. (iv) Es sei C ein Min-Cut. Dann gilt: ¯ Contract findet C ⇔ Contract w¨ahlt in Schritt (2) nie eine Kante aus E(C, C). Beweis: (i), (ii) und (iv): klar (iii): Ein Cut im kontrahierten Graphen ist auch immer Cut im urspr¨ unglichen Graphen. Satz 5.2. Contract findet einen Min-Cut mit Wahrscheinlichkeit mindestens 1/ n2 .

2

¯ Es gilt δ(G) ≥ k, da sich sonst ein kleinerer Beweis: Sei C ein Min-Cut von G und k := |E(C, C)|. Cut finden ließe, indem man den Knoten mit minimalem Grad und den Rest des Graphen jeweils einer Partition zuweist. Es gilt also

63

|E| =

1X nk . deg(v) ≥ 2 2

(35)

v∈V

Sei nun Ei das Ereignis ,,keine Kante von C wird im i-ten Schritt kontrahiert ”, 1 ≤ i ≤ n − 2. Es gilt:   "n−2 # i−1 n−2 ^ Y ^ Ej , P Ei | Ei = P [En−2 |En−3 ∧ · · · ∧ E1 ] · . . . · P [E2 |E1 ]P [E1 ] = P i=1

i=1

j=1

und laut (iv) gen¨ ugt nun zu zeigen:

"n−2 # n−2  i−1  Y ^ ^ n 1/ ≤P P Ei | Ei = Ej . 2 i=1 i=1 j=1 i h V i−1 Dazu berechnen wir die Wahrscheinlichkeiten P Ei | j=1 Ej wie folgt: Ist i = 1, so ist 2 2 k (35) k ≤ = also P [E1 ] ≥ 1 − . P E¯1 = |E| nk/2 n n

Und allgemein gilt: Vor der i-ten Kontraktion haben wir genau ni := n − i + 1 Knoten. Wenn wir darauf bedingen, dass bislang keine Kante von C kontrahiert wurde, dann ist der Min-Cut noch immer h¨ochstens k und wegen (iii) genau k. Damit k¨ onnen wir wie in (35) schlussfolgern und erhalten:     i−1 i−1 ^ ^ 2 k 2 P E¯i | also P Ei | = Ej  ≤ Ej  ≥ 1 − . ni k/2 ni ni j=1 j=1 Also gilt insgesamt "n−2 # n−2 n−2 3 Y Y n−i−1 Y ^ 2 j−2 n−2 n−3 2 1 n (1 − ) = Ei ≥ P = = · · . . . · · = 1/ . n n − i + 1 j n n − 1 4 3 2 i i=1 i=1 j=n i=1

2 Bemerkung 5.3. (i) F¨ uhrt man Contract bei gleicher Instanz rn2 -mal hintereinander aus, dann sinkt die Fehlerwahrscheinlichkeit von 1 − n12 auf (1 −

1 rn2 ) n2

(2.13)

1

2

≤ e− n2 rn = e−r

(ii) Eine Kontraktion l¨asst sich in O(n) implementieren, inklusive der zuf¨alligen Wahl der Kante. F¨ ur Contract erg¨abe sich damit eine Laufzeit von O(n2 ), womit rn2 Durchl¨aufe O(rn4 ) Schritte kosteten. Lemma 5.4. Stoppt man Contract in dem Moment, in dem der Graph noch genau t Knoten enth¨alt, dann ¨ uberlebt ein beliebiger, fester Min-Cut mit Wahrscheinlichkeit mindestens 2 ! t n t / =Ω . 2 2 n Beweis: Analog zum Beweis von Satz 5.2.

2

Ziel ist es nun, die Fehlerwahrscheinlichkeit des Algorithmus zu senken. Auff¨allig bei Contract ist, dass ein Min-Cut, der bis zu einem gewissen Zeitpunkt alle Kontraktionsschritte ,,¨ uberlebt” 64

hat, die folgenden Kontraktionen nur mit extrem schnell fallender Wahrscheinlichkeit u ¨ berlebt, da die ,,guten” Kanten immer seltener werden. Es ist also nahliegend, den Algorithmus mit zunehmender Zeit ¨ofter zu wiederholen um dies zu kompensieren. Dieser Ansatz wird durch den folgenden Algorithmus umgesetzt: Algorithm 8: Fast-Cut Input: Ein Multi-Graph G = (V, E) Output: Ein Cut C von G Fast-Cut(G) (1) if n ≤ 6 (2) Finde Min-Cut durch brute force (3) else m l

(4) (5)

(6) (7) (8)

t := 1 + √n2 Starte zwei unabh¨ angige L¨aufe von Contract(G), die gestoppt werden wenn zwei Graphen H1 und H2 mit jeweils t Knoten erreicht sind. C1 := Fast-Cut(H1 ) C2 := Fast-Cut(H2 ) return Cut mit kleinerer Kantenanzahl.

Der Berechnungsbaum von Fast-Cut ist also ein bin¨arer Baum, in dem jeder Knoten √ einen Graphen repr¨ asentiert. Hat ein Graph n Knoten, dann haben seine Kinder (ungef¨ahr) n/ 2 Knoten. Der Baum hat also H¨ ohe log√2 n = 2 log n, und damit 22 log n = n2 Bl¨atter. Lemma 5.5. Fast-Cut hat eine Laufzeit von O(n2 log n). Beweis: Sei T (n) die Laufzeit von Fast-Cut f¨ ur einen Graphen auf n Knoten, und sei dn2 eine obere Schranke f¨ ur die Laufzeit von Contract(G). Dann gilt: n + 2dn2 . T (n) ≤ 2T 1 + √ 2 Vorlesung 12.1. Nun gen¨ ugt zu zeigen, dass eine Konstante A existiert mit T (n) ≤ An2 log n. Wir setzen 10 A := T (2 )20d und zeigen diese Behauptung durch Induktion u ¨ber n zeigen. Als Induktionsanfang betrachten wir n ≤ 210 . Hier gilt: T (n) ≤ T (210 ) ≤ A ≤ An2 log n. Sei nun also n > 210 und die Behauptung f¨ ur kleinere n bewiesen. Beachte: f¨ ur n > 210 k¨onnen n n wir 2 + √2 ≤ 1.4 absch¨ atzen. Im Induktionsschritt sehen wir: " # 2 IV n n · log(2 + √ ) + 2dn2 T (n) ≤ 2 · A · 2 + √ 2 2 2 n n 4 √ n+ · log + 2dn2 ≤2· A· 4+ 2 1.4 2 n2 n 4 =2· A· (log n − log 1.4) + 2dn2 + 2A(4 + √ n) log 2 1.4 2 ≤ A · n2 · log n − An2 log 1.4 + 2dn2 + 16An log n Es gen¨ ugt nun zu zeigen, dass 2dn2 + 16An log n ≤ An2 log 1.4. 65

(36)

Um dies einzusehen u ufen wir, dass aus 20d ≤ A folgt, dass 2dn2 ≤ 0.1An2 . Aus 16 log n ≤ ¨ berpr¨ 0.3n folgt, dass 16An log n ≤ 0.3An2 log n, und beides zusammen impliziert wegen 0.4 < log 1.4 (36). 2 Wir sehen also, dass Fast-Cut eine etwas h¨ohere Laufzeit als Contract hat, und wenden uns nun der Erfolgswahrscheinlichkeit zu. Satz 5.6. Fast-Cut hat eine Erfolgswahrscheinlichkeit von mindestens Ω( log1 n ). Beweis: Zun¨ achst eine Vor¨ uberlegung: Es sei H auf t Knoten, auf dem wir Contract m l ein Graph t ′ ′ ausf¨ uhren, bis wir einen Graphen H auf t := 1 + √2 Knoten erhalten. Dann gilt nach Lemma 5.4 f¨ ur einen beliebigen, festen Min-Cut C von H: P [C u ¨bersteht Kontraktion von H auf H ′ ] ′ t t ≥ / 2 2 t′ (t′ − 1) 1 ≥ · 2 t(t − 1) (1 + √t2 ) √t2 = t(t − 1) ≥

t2 2 t2

=

1 . 2

Wir bezeichnen mit P (H) die Wahrscheinlichkeit, dass Fast-Cut (kurz FC) in einem Graphen H einen Min-Cut findet. Es gilt: P (H) = 1 − P [FC findet keinen Min-Cut in H] = 1 − P [FC via H1 findet keinen Min-Cut von H]P [FC via H2 findet keinen Min-Cut von H]

= 1 − (1 − P [FC via H1 liefert Min-Cut von H])(1 − P [FC via H2 liefert Min-Cut von H]) = 1 − (1 − P [ein Min-Cut von H u ¨ berlebt Kontraktion nach H1 ] P [FC findet in H1 einen Min-Cut]) (1 − P [ein Min-Cut von H u ¨ berlebt Kontraktion nach H2 ] P [FC findet in H2 einen Min-Cut]) 1 1 ≥ 1 − 1 − · P (H1 ) 1 − · P (H2 ) . 2 2

Betrachten wir nun wieder den Rekursionsbaum von Fast-Cut und bezeichne mit d = O(log n) seine H¨ohe. Mit der H¨ ohe eines Knoten (Graphen) im Rekursionsbaum bezeichnen wir den k¨ urzesten Abstand zu einem Blatt. Es sei p(h) eine untere Schranke f¨ ur die Wahrscheinlichkeit, dass Fast-Cut in einem Graphen der H¨ ohe h ein Min-Cut findet. Unser Ziel ist es, p(d) ≥ Ω( log1 n ) zu zeigen. Offensichtlich ist p(0) = 1. Außerdem l¨aßt sich aus der obigen Rekursion f¨ ur P (H) ableiten, dass f¨ ur h ≥ 1 gilt 2 1 1 1 p(h) ≥ 1 − 1 − · p(h − 1) 1 − · p(h − 1) = 1 − 1 − · p(h − 1) . 2 2 2

Wir zeigen durch Induktion nach h, dass p(h) ≥ 1/(h + 1).

(37)

Vorlesung 18.1. F¨ ur den Induktionsanfang h = 0 ist (37) mit p(0) = 1 erf¨ ullt. F¨ ur den Induktionsschritt gilt

66

mit Hilfe der eben gezeigten Rekursion f¨ ur h ≥ 1: 2 1 p(h) ≥ 1 − 1 − · p(h − 1) 2 2 IV (2h − 1)2 4h − 1 1 1 =1− = ≥ 1− 1− · 2 h (2h)2 4h2 2 (4h − 1)(h + 1) 1 4h + 3h − 1 1 1 = = ≥ , 4h2 h+1 4h2 h+1 h+1 und damit ist (37) bewiesen. Somit folgt f¨ ur die H¨ ohe des Rekursionsbaums d = O(log n), dass p(d) ≥

1 1 = Ω( ), d+1 log n

was zu beweisen war.

2

Bemerkung 5.7. Um die Fehlerwahrscheinlichkeit zu senken, f¨ uhrt man Fast-Cut einfach mehrfach aus. Dabei kosten log2 n Iterationen O(n2 log3 n) und senken die Fehlerwahrscheinlichkeit auf ≤ 1−

log n·log n c log n log n·log n c

≤ e− log n

= e−c log n 1 = c. n

Die Fehlerwahrscheinlichkeit geht also gegen 0 f¨ ur n → ∞. ¨ Ubung 5.8. Wenn man Contract so modifiziert, dass in Schritt (2) ein zuf¨alliges, beliebiges Knotenpaar (und keine Kante) kontrahiert wird, dann gibt es Graphen, f¨ ur die der modifizierte Algorithmus nur mit exponentiell kleiner Wahrscheinlichkeit einen Min-Cut findet. ¨ Ubung 5.9. Angenommen 237 Studenten verlassen in der Vorlesungspause den H¨orsaal (mit exakt 237 Pl¨atzen) und kehren nach einem Besuch der Cafeteria so betrunken zur¨ uck, dass sie sich auf einen zuf¨alligen Platz setzen (Mehrfachbelegungen billigend in Kauf genommen). Wie groß ist die erwartete Anzahl von Studenten, die wieder auf ihrem alten Platz landen?

5.2

Fingerabdru ¨cke

Fingerabdruck ist eine Methode, die oftmals in Indentifikationsvorg¨angen zum Einsatz kommt. Dabei wird von diesen Vorg¨ angen h¨ aufig eine geringe Komplexi¨at verlangt. Die Informationen der zu identifizierenden Objekte sollen daher m¨oglichst kompakt und charakateristisch sein. Betrachten einige Beispiele: 5.2.1

Bitw¨ orter-Vergleiche

Seien zwei n-Bit W¨ orter ~a = (a0 , . . . , an−1 ) ∈ {0, 1}n ~b = (b0 , . . . , bn−1 ) ∈ {0, 1}n an zwei verschiedenen Orten A und B gegeben. Zur Beantwortung der Frage, ob diese gleich sind, sollen m¨oglichst wenig Bits ausgetauscht / verglichen werden. Das naive Vorgehensweise w¨ are der Vergleich von zuf¨alligen Bits. Diese h¨atte bei n2 Bitvergleichen und zwei W¨ orter, die sich nur in einem Bit unterscheiden, eine Fehlerwahrscheinlichkeit von 12 .

67

Wir suchen nun geeignete Fingerabdr¨ ucke“ und zeigen, dass der Vergleich dieser ein besseres ” Ergebnis liefern. Algorithm 9: Randomisierter Bitvergleich Input: Zwei zu vergleichende Bitw¨orter Output: Gibt aus, ob diese W¨ orter gleich sind rand BV(~a,~b) (1) Wandle Bitfolge in eine Dezimalzahl um: Pn−1 (2) A: a := i=0 ai 2n−1−i Pn−1 n−1−i (3) B: b := i=0 bi 2 (4) A w¨ ahlt Primzahl p ≤ τ zuf¨allig gleichverteilt aus. (5) A: Fp (a) := a mod p. (6) B: Fp (b) := b mod p. (7) A schickt p und Fp (a) zu B. (8) if Fp (a) = Fp (b) (9) return ja“ ” (10) else (11) return nein“ ”

Entscheidend f¨ ur die Analyse der G¨ ute ist der Satz 5.10. (Der Große Primzahlsatz) Es sei τ ∈ N beliebig und π(τ ) := Anzahl Primzahlen ≤ τ . τ Dann gilt π(τ ) ∼ ln(τ ). Dieser Satz wurde von Hadamard (1865-1963) und de la Vall´ee Poussin (1866-1962) im Jahre 1896 unabh¨angig von einander bewiesen, nachdem er u ¨ ber 100 Jahre als Vermutung existierte. Doch nun kehren wir zu unserem Algorithmus Randomisierter Bitvergleich zur¨ uck und beweisen den Satz 5.11. Der Algorithmus Randomisierter Bitvergleich ben¨otigt O(log τ ) Bitvergleiche bei ) ). einer Fehlerwahrscheinlichkeit von O( n ln(τ τ Beweis: Zuerst betrachten wir die Anzahl Bitvergleiche und stellen fest, dass nur die Primzahl p und der Fingerabduck Fp (a) verschickt werden. Wegen p ≤ τ und Fp (a) < p ≤ τ folgt die bahauptete Schranke f¨ ur die Anzahl Bitvergleiche. Zur Analyse der Fehlerwahrscheinlichkeit betrachten nun den Fall, bei dem der Algorithmus nein ausgibt. Es gilt hier Fp (a) 6= Fp (b), folglich a 6= b und die Antwort des Algorithmus ist richtig. Lautet die Antwort dagegen ja - d.h. Fp (a) = Fp (b) - liegt f¨ ur den Fall a 6= b ein Fehler vor. Es sei dann oBdA a > b und c := a − b. Aus Fp (a) = Fp (b) folgern wir: a mod p = b mod p

⇒

c mod p = 0

Damit gilt f¨ ur die Fehlerwahrscheinlichkeit: P [Ein Fehler tritt auf] = P [c mod p = 0|c 6= 0] ≤

#{Primfaktoren von c} n = O( τ ). #{Primzahlen ≤ τ } ln(τ )

Bei der Ungleichung haben wir ausgenutzt, dass p ein Primfaktor von c sein muss und als eine Primzahl kleiner als τ zuf¨ allig gew¨ ahlt wurde. Ferner ist c ≤ a < 2n und hat damit h¨ochstens n verschiedene Primfaktoren. Dies und der Große Primzahlsatz rechtfertigt die letzte Gleichung. 2 Beispiel: Sei τ = n3 . Dann ist die Anzahl Bit Vergleiche O(log(n3 )) = O(log(n)). Die Fehler3 ) ) = O( ln(n) wahrscheinlichkeit ist ≤ O( n ln(n n3 n2 ). 68

Einseitiger Fehler, wie bei Randomisierter Bitvergleich der Fall, ist u ¨ brigens eine charakteristische Eigenschaft vieler Verfahren, die auf Fingerabdruck basieren. Das werden wir auch in den folgenden Beipielen wiederfinden. 5.2.2

Polynomvergleich

Auch stichprobenartige Tests k¨ onnen bei bestimmten Strukturen einen effektiven Fingerabdruck liefern, wie unser letztes Beispiel zeigen wird. Es seien nun x1 , x2 , . . . , xn Variablen in R. Ein Monom ist definiert als: M=

n Y

xbi i ,

i=1

mit bi ∈ N und Grad(M ) =

n X

bi .

i=1

Und f¨ ur cj ∈ Q ist ein Polynom definiert als: P =

n X j=1

cj M j ,

mit Grad(P ) = max{Grad(Mj )}. j

Falls die Polynome durch alle ihre Monome explizit gegeben sind, ist die Gleicheit zweier Polynome schnell festzustellen. Sind die Polynome p(x1 , x2 , . . . , xn ) :=

k Y

pi (x1 , x2 , . . . , xn )

und

q(x1 , x2 , . . . , xn ) :=

l Y

qi (x1 , x2 , . . . , xn )

i=1

i=1

aber durch die Polynome (pi ) und (qi ) in den Variablen x1 , x2 , . . . , xn gegeben, so verh¨alt sich Sache schon ganz anders. Zwar gibt es den naheliegenden Ansatz, die beiden Produkte auszurechnen um anschließend die jeweiligen Koeffizienten zu vergleichen. Doch wenn √ man beispielsweise den Fall √ betrachtet, bei dem k = l = n und jedes der Polynome pi , qj aus n Monomen besteht, wird deutlich, dass dieser einfache Methode i.a. nicht polynomiell sein kann. In diesem Fall w¨are die √ √n 1√ Eingabe linear in n, w¨ ahrend das Ausmultiplizieren (jeder mit jedem) bereits Θ( n ) = Θ(n 2 n ) kostet. Wir versuchen einen anderen Ansatz: Algorithm 10: Randomisierter Polynomvergleich Input: Zwei Polynome als Produkte anderer Polynome Output: Antwort, ob die Polynome gleich sind rand PV(p,q) Pk Pl (1) d := max{ i=1 Grad(pi ), i=1 Grad(qi )} (2) W¨ ahle zuf¨ allig r1 , r2 , . . . , rn ∈ {1, 2, . . . , 2d} (3) if p(r1 , r2 , . . . , rn ) = q(r1 , r2 , . . . , rn ) (4) return ja“ ” (5) else (6) return nein“ ” Bemerkung 5.12.

(i) RandPV ist linear in Eingabel¨ange.

(ii) Fehler treten nur auf, wenn p(r) = q(r), aber p − q 6≡ 0 (iii) Grad(p) ≤ d und Grad(q) ≤ d, also Grad(p − q) ≤ d. Vorlesung 19.11. Satz 5.13. Es sei f ein Polynom mit Grad(f ) ≤ d und f 6≡ 0. Dann ist P [f (r1 , r2 , . . . , rn ) = 0] ≤ dl , wenn die ri zuf¨allig gleichverteilt in {1, 2, . . . , l} gew¨ahlt werden.

69

Beweis: Wir beweisen den Satz durch Induktion u ¨ber n. F¨ ur den Anfang ist P [f (r1 ) = 0] ≤ dl , da f maximal d Nullstellen besitzen kann und r1 aus einer Menge von l Elementen ausgew¨ ahlt wird. Sei nun f¨ ur den Induktionsschritt k der Grad von x1 in f . Dann l¨aßt sich f zerlegen in f (x1 , x2 , . . . , xn ) =

k X

xi1 gi (x2 , . . . , xn )

(38)

i=0

mit gk 6≡ 0 und Grad(gk ) ≤ d − k Man beachte, dass gi nicht von x1 abh¨ angt. Folglich gilt nach Induktionsannahme P [gk (r2 , . . . , rn ) = 0] ≤

d−k . l

F¨ ur den fall, daß gk (r2 , . . . , rn ) 6= 0 gilt, betrachte man F (x1 ) := f (x1 , r2 , . . . , rn ). Nach (38) ist Grad(F ) ≤ k. Nach Induktionsannahme (f¨ ur den Fall n = 1) folgt daher P [F (r1 ) = 0 | gk (r2 , . . . , rn ) 6= 0] ≤

k l

¯ + P [B] aus (2.6(ix)) erhalten wir Unter Verwendung der allgemeinen Absch¨ atzung P [A] ≤ P A|B insgesamt: P [f (r1 , r2 , . . . , rn ) = 0] = P [F (r1 ) = 0] ≤ P [F (r1 ) = 0 | gk (r2 , . . . , rn ) 6= 0] + P [gk (r2 , . . . , rn ) = 0] d−k k ≤ + l l d = l 2 Setzt man nun f (x1 , x2 , . . . , xn ) = p(x1 , x2 , . . . , xn ) − q(x1 , x2 , . . . , xn ) so ergibt sich aus dem obigen Satz sofort die Fehlerwahrscheinlichkeit f¨ ur unseren randomisierten Polynomvergleich. Korollar 5.14. F¨ ur den Fall p ≡ q ist P [randPV macht Fehler] = 0. Ist dagegen p 6≡ q dann betr¨agt die Fehlerwahscheinlichkeit P [randPV macht Fehler] ≤

5.3

1 2

Primzahltests

Große Primzahlen nehmen auch in der Praxis, so z.B. in der Krytographie, einen besonderen Platz ein, weswegen dem Primzahlproblem, also zu entscheiden, ob eine gegebene Zahl n prim ist, eine besondere Bedeutung zukommt. Gleichzeitig kann dieses Problem auf eine lange Historie verweisen. So ist sehr fr¨ uh schon das Sieb des Eratosthenes (276-195 v. Chr.) bekannt. Dieses bestimmt alle Primzahlen unterhalb einer √ Schranke n in Ω( n) Schritten. Beachte man, dass die Eingabe lediglich O(log n) betr¨agt, so ist klar, dass dieser Algorithmus nicht polynomiell ist. 70

Trotz intensiven Bem¨ uhens war bis 2002 nicht klar, zu welcher Komplexit¨atsklasse das Primzahlproblem geh¨ ort. In jenem Jahr zeigten Agrawal/Kayal/Saxena dann, dass das Primzahlproblem polynomiell l¨ osbar ist. Allerdings sind aktuell bekannte deterministische Algorithmen f¨ ur die Praxis nicht schnell genug. Auf der anderen Seite wurden in den 70er Jahren probabilistische L¨osungsversuche sowohl von Solovay/Strassen als auch von Miller/Rabin unternommen. Ihre erfolgreiche Arbeit ¨offnete den Randomisierten Algorithmen die T¨ ur zum Algorithmen-Design. Mit ihren Ergebnissen wollen wir uns im Folgenden vertraut machen. Bezeichne P = {2, 3, 5, . . . } die Menge der Primzahlen. Ferner definieren wir • die additive Gruppe modulo n als (Zn , +n ) = ({0, . . . , n − 1}, +n). • die multiplikative Gruppe modulo n als (Z∗n , ·n ) = ({a ∈ Zn : ggT (a, n) = 1}, ·n ). Beispiel. Z∗15 = {1, 2, 4, 7, 8, 11, 13, 14}, 0 6∈ Z∗n , 8 ·15 7 = 11. Offensichtlich gilt: p ∈ P ⇒ Z∗p = {1, 2, . . . , p − 1} Bei unserem ersten Herantasten an das Primzahlproblem hilft uns der Jurist und Mathematiker Fermat mit dem Satz 5.15. (Kleiner Satz von Fermat, 1640) p ∈ P ⇒ ∀a ∈ Z∗p : ap−1 ≡ 1(mod p) Dies motiviert die Bezeichnung ,,pseudoprim zur Basis a” f¨ ur all jene Zahlen n, f¨ ur die an−1 ≡ 1(mod n) gilt. Korollar 5.16. Wenn ggT(a,n)=1 (also a ∈ Z∗n ) und an−1 6≡ 1(mod n), also n nicht pseudoprim zur Basis a, dann n 6∈ P. Dieses bildet die Grundlage unseres ersten Versuchs zur L¨osung des Primzahlproblems. Algorithm 11: Pseudoprim-Algorithmus Input: n ∈ N, n ≥ 3 Output: n ∈ P ? Pseudoprim(n) (1) if ggT(n,2) 6= 1 (2) return ,,nicht prim” (3) else (4) if 2n−1 mod n 6= 1 (5) return ,,nicht prim” (6) else (7) return ,,prim”

Bemerkung 5.17. • Falls die Antwort ,,nicht prim” lautet, kann kein Fehler auftreten. Ist die Antwort dagegen ,,prim”, so ist n pseudoprim zur Basis 2 (evtl. aber keine Primzahl). • Es ist naheliegend, mehrere Basen zu versuchen. Allerdings gibt es Zahlen, bei denen dieser Ansatz notwendig scheitert. F¨ ur diese sogenannte Carmichael-Zahlen gilt n¨amlich: n 6∈ P und n ist pseudoprim zur Basis a,

∀a ∈ Z∗n

Die ersten Carmichael-Zahlen sind 561, 1105, 1729,. . . |{Carmichael-Zahl ≤ 108 }| = 255. 71

Da die Geschwindigkeit des Algorithmus wesentlich von der Berechnung von ab mod n abh¨angt, betrachten wir zu diesem Zweck den schnellen Algorithmus Modulare Exponentiation. Algorithm 12: Modulare Exponentiation Input: a, b, n ∈ N Output: ab mod n Modulare Exponentiation(a,b,c) (1) c := 0, d := 1 (2) b =: (bk , bk−1 , . . . , b1 , b0 )2 (3) for i:=k downto 0 do (4) c := 2 · c (5) d := (d · d) mod n (6) if bi = 1 (7) c := c + 1 (8) d := (d · a) mod n (9) return d

¨ Beispiel. Eingabe a = 3, b = 5 = (101)2 , n = 6, gesucht ist also 35 mod 6. Betrachte die Anderungen der Variablen c und d im Laufe des Algorithmus: c 0 1 2 4 5

d 1 3 3 3 3

Satz 5.18. Sei die L¨ange der Bin¨ardarstellung von a, b, n durch β beschr¨ankt. Der Algorithmus Modulare Exponentiation ist korrekt und braucht O(β) arithmetische Operationen bzw. O(β 3 ) Bitoperationen. Beweis: Wir sehen, dass die for-Schleife O(β) mal durchlaufen wird und dass jede O(1) arithmetischen Operationen bzw. O(β 2 ) Bitoperationen ben¨otigt. Zum Nachweis der Korrektheit zeigt man mittels Induktion, dass f¨ ur i = k, . . . , 0 gilt: Bevor die Schleife mit Index i durchlaufen wird, hat c die Bin¨ardarstellung (bk , bk−1 , . . . , bi+1 ) und es ist d = ac mod n. Die detailierte Ausf¨ uhrung u ¨ berlassen wir dem Leser – siehe die sp¨atere ¨ Ubung. 2 Der folgende Satz erm¨ oglicht eine zweite Verbesserung des Pseudoprim-Algorithmus. Mit Hilfe dieses Satzes k¨ onnen auch Carmichael-Zahlen als zusammengesetzte Zahlen erkannt werden. Satz 5.19. Sei p ∈ P, p > 2, e ∈ N+ . Dann hat die Gleichung x2 ≡ 1(mod pe ) in Zpe nur zwei L¨osungen, n¨amlich x = 1 und x = −1. Dies pr¨agt das Pr¨ adikat ,,nicht-triviale Wurzel von 1 modulo n” f¨ ur alle x mit x2 ≡ 1(mod n) aber x 6≡ 1( mod n) und x 6≡ −1( mod n). So ist z.B. 5 eine ,,nicht-triviale Wurzel von 1 modulo 8 ”. Korollar 5.20. Gibt es eine nicht-triviale Wurzel von 1 modulo n, so ist n keine Primzahl.

Damit kennen wir zwei F¨ alle, in denen eine Zahl n als ,,nicht prim” erkannt wird: (i) Es gibt eine Basis a, so dass n nicht pseudoprim zur Basis a ist. (ii) Es gibt eine nicht-triviale Wurzel von 1 modulo n. Diese beiden sind in der folgenden Routine umgesetzt:

72

Algorithm 13: Routine Witness Input: a, n ∈ N, n ungerade Output: Ist a Zeuge f¨ ur ,,n ist nicht prim” ? Witness(a,n) (1) n − 1 = 2t · u, u ungerade (2) x0 := au mod n (3) for i:=1 to t (4) xi := (xi−1 )2 mod n (5) if xi = 1 und xi−1 6= 1 und xi−1 6= n − 1 (6) return Ja (7) if xt 6= 1 (8) return Ja (9) else (10) return Nein

Die Routine Witness(a,n) kann bei passender Eigabe a auch eine Carmichael-Zahl n als ,,nicht prim” diskreditieren. Dies kann man anhand der Arbeitsweise von Witness(7,561) nachvollziehen. Lemma 5.21. Sei a ∈ Zn . Wenn Witness(a,n) = Ja, dann ist n nicht prim. Beweis: Wir wollen zeigen, dass bei der Ausgabe ,,Witness(a,n) = Ja” der Fall (i) bzw. (ii) vorliegt. Da n ungerade ist, sei n − 1 = 2t · u, mit u ungerade. Die Routine Witness berechnet zun¨ achst x0 = au (mod n) und quadriert dann fortlaufend das i Ergebnis modulo n. Das Zwischenresultat xi hat daher die Gestalt xi = (au )2 mod n. Es wird nachgepr¨ uft, ob dieses eine nicht-triviale Wurzel von 1 modulo n ist. G¨alte gem¨aß Zeile (5) xi ≡ (xi−1 )2

xi−1

xi−1 6 n − 1(mod n) ⇔ xi−1 ≡

≡

6≡ 6≡

1(mod n) und 1(mod n) und −1(mod n),

dann ist mit xi eine solche gefunden. Damit tritt der Fall (ii) ein und n ist nach Korollar 5.20 keine Primzahl. Außerdem gilt nach Zeile (6) f¨ ur xt : t

xt ≡ (au )2 (

mod n) ≡ an−1 (mod n).

Ist nun gem¨ aß Zeile (7) xt 6= 1, dann ist mit a eine Basis gefunden, so dass n nicht ,,pseudoprim zur Basis a” ist. Damit tritt Fall (i) ein und n ist nach Korollar 5.16 keine Primzahl. 2 Vorlesung 25.1. Das heißt: wenn n Primzahl ist, dann wird die die Routine Witness(a,n) mit Nein antworten, und zwar f¨ ur jedes a ∈ Zn . Umgekehrt h¨ atten wir gerne, dass wenn n nicht Primzahl ist, Witness(a,n) mit Ja antwortet. Sei also n zusammengesetzt, dann nennen wir eine Zahl a ∈ Zn f¨ ur die Witness(a,n) = Nein ist, ,,L¨ ugner f¨ ur n”. Unser Ziel ist es zu zeigen, dass die wenigsten a ∈ Zn L¨ ugner sind. ¨ Ubung 5.22. Zu jeden Zahlen a, b ∈ Z gibt es Zahlen x, y ∈ Z mit 3a2 + 6b2 = x2 + 2y 2 . ¨ Ubung 5.23. Die Gleichung ab = 2 c + 1 hat genau eine L¨osung f¨ ur a, b, c ∈ N mit b > 1.

73

¨ Ubung 5.24. Zeigen Sie die Korrektheit des Algorithmus Modulare Exponentiation. Weisen Sie dabei mittels Induktion folgendes nach: Bevor die Schleife mit Index i durchlaufen wird, hat c die Bin¨ardarstellung (bk , bk−1 , . . . , bi+1 ) und es ist d = ac mod n. Einige Vorbereitungen: Satz 5.25. (Chinesischer Restsatz) Qk (i) n1 , . . . , nk seien paarweise teilerfremde Zahlen, n = i=1 ni . F¨ ur jede Folge r1 ∈ Zn1 , . . . , rk ∈ Znk existiert ein eindeutiges r ∈ Zn mit r ≡ ri (mod ni )

∀i ∈ [k]

r l¨asst sich in polynomieller Zeit berechnen. Beispiel. k = 2, r ≡ 3(mod 4), r ≡ 5(mod 7) hat L¨osung r = 19. (ii) Wenn n1 , . . . , nk paarweise teilerfremd sind, n =

Qk

i=1

ni , dann gilt ∀x, a ∈ N

x ≡ a(mod ni ) ∀i ∈ [k] ⇔ x ≡ a(mod n). Den Beweis findet der Leser in jedem g¨angigen Buch der Algebra. Proposition 5.26. Wenn die Gleichung ax ggT (a, n) Teiler von b ist.

≡

b(mod n) eine L¨osung f¨ ur x hat, dann ist

Beweis: Wenn es eine L¨ osung gibt, dann existieren also x, ℓ mit ax = ℓn + b. Der ggT (a, n) ist Teiler von ax und ℓn, und somit auch von b. 2 ¨ Ubung 5.27. Zeigen Sie, dass eine Carmichael-Zahl keine Primzahlpotenz pi mit i ≥ 2enth¨alt. Hinweis: Beweis durch Widerspruch. Schreiben Sie n = pi m wobei m nicht durch p teilbar ist. Wenn m = 1, dann setzen Sie a = 1 + p, andernfalls sei a ∈ [1, p2 m − 1] die L¨osung von a ≡ 1 + p(mod p2 ) und a ≡ 1(mod m). Zeigen Sie, dass dann a ∈ Z∗n und an−1 6≡ 1(mod n). Wir wollen nun beweisen, dass nur wenige ,,L¨ ugner ” existieren, wenn n keine Primzahl ist. Aus der Gruppentheorie wissen wir: Ist (G, ∗) eine endliche Gruppe und U eine echte Untergruppe von G, so ist |U | Teiler von |G|. Wir werden zeigen, dass die Menge der L¨ ugner in einer echten Untergruppe von Z∗n enthalten ist, und haben damit dann den folgenden Satz bewiesen. Satz 5.28. Sei n eine ungerade, zusammengesetzte Zahl. Dann gibt es h¨ochstens n.

n−1 2

L¨ ugner f¨ ur

Sei n wie in dem Satz angegeben. Bevor wir zum Beweis kommen, wollen wir noch festhalten, dass die Routine Wittness(a,n) im Wesentlichen vier ,,Abl¨aufe” produzieren kann. Die Routine Witness berechnet x0 = au (mod n) und quadriert dann fortlaufend das Ergebnis modulo n. Sei i also X(a) = (x0 , x1 , ..., xt ), mit xi = a2 u mod n und 2t u = n − 1, die Zwischenergebnisse eines Ablaufs. Dann k¨ onnen nur folgende F¨ alle eintreten: (i) X(a) = (1, 1, ..., 1) ⇒ a ist ,,L¨ ugner”, falls n nicht prim. (ii) X(a) = (∗ ∗ ...∗, −1, 1, ..., 1) ⇒ a ist ,,L¨ ugner”, falls n nicht prim. 74

(iii) X(a) = (∗ ∗ ...∗, d),

d 6= 1 ⇒ a ist Zeuge f¨ ur ,,n nicht prim” (nach Fermat).

(iv) X(a) = (∗ ∗ ...∗, d, 1, ..., 1), dratwurzel).

d 6= ±1 ⇒ a ist Zeuge f¨ ur ,,n nicht prim” (nicht triviale Qua-

Mit diesen Bemerkungen beweisen wir nun Satz 5.28 Beweis: Sei n > 2 keine Primzahl und a ein beliebiger ,,L¨ ugner ”, d.h. Witness(a,n) = Nein. Dann ist ggT (a, n) = 1. Denn sonst h¨ atte nach Satz 5.26 die Gleichung ax ≡ 1(mod n) keine L¨osung. Insbesondere ist dann mit x = an−2 a · (an−2 ) 6≡ 1(mod n), mit Widerspruch, da a in diesem Falle wegen Zeile (7) des Algorithmus kein ,,L¨ ugner” w¨are. Damit sind alle ,,L¨ ugner” a ∈ Z∗n . Nun werden wir zeigen, dass alle ,,L¨ ugner ” in einer echten Untergruppe A von Z∗n enthalten sind und unterscheiden dazu zwei F¨ alle. Fall 1 : ∃x ∈ Z∗n : xn−1 6≡ 1(mod n). Dies bedeutet, dass n keine Carmichael-Zahl ist. ugner” in A enthalten sind, ist Sei dann A := {y ∈ Z∗n : y n−1 ≡ 1( mod n)}. Dass alle ,,L¨ ugner, so hat X(a) die Form (i) bzw. leicht einzusehen. Ist n¨ amlich a ∈ Zn∗ ein beliebiger L¨ (ii). Insbesondere gilt dann: t

xt = a2

u

mod n = 1,

t

a2

d.h.

u

= an−1 ≡ 1(modn),

und damit a ∈ A. Da A ferner abgeschlossen unter ·n ist, ist A Untergruppe von Z∗n . Schlußendlich ist nach Annahme x 6∈ A, also ist A eine echte Untergruppe von Z∗n . Fall 2 : ∀x ∈ Z∗n : xn−1 ≡ 1(mod n), womit n also eine Carmichael-Zahl ist. ¨ Damit k¨ onnen wir n nach Ubung 5.27 schreiben als n = n1 · n2 annehmen, mit n1 > 1, n2 > 1 teilerfremd. Wie in Algo Witness(a, n) sei n − 1 = 2t · u, u ungerade und wir w¨ahlen den gr¨oßten Index j, 0 ≤ j < t, so daß: j

∃v ∈ Z∗n : v u·2 0

Ein solches j existiert, da (−1)2

·u

≡ −1(mod n).

≡ −1(mod n) gilt.

Wir halten zu diesem j das zugeh¨ orige v fest, definieren ferner j

A := {a ∈ Z∗n : au·2

≡ ±1(mod n)}.

Wieder ist A abgeschlossen unter ·n , also eine Untergruppe von Z∗n . Nun gen¨ ugt es zu zeigen: Beh. 1 : Jeder ,,L¨ ugner” a liegt in A. Beh. 2 : ∃w ∈ Zn , w 6∈ A.

Beh. 3 : w ∈ Z∗n bzw. ggT (w, n) = 1. Zu 1 : Ist a ∈ Z∗n ein beliebiger ,,L¨ ugner”, so produziert a einen Ablauf X(a) aus Einsen bestehend oder (wegen Maximalit¨at von j) eine -1 sp¨atestens an der j-ten Stelle, gefolgt von Einsen. In beiden F¨ allen ist a ∈ A. j

j

Zu 2 : Wegen v u·2 ≡ (−1)(mod n) gilt v u·2 Restsatz (ii). Das Gleichungsystem x = v(mod n1 )

≡ (−1)(mod n1 ) nach dem Chinesischen

und

x = 1(mod n2 )

hat dem Chinesischen Restsatz (i) folgend eine (eindeutige) L¨osung in Zn . Sei w diese L¨ osung. Dann gilt: 75

j

wu·2 j

j

≡n1 v u·2 ≡ −1(mod n1 ) j wu·2 ≡ 1(mod n2 )

und

W¨ are nun wu·2 ≡ ±1(mod n), lieferten uns der Chinesische Restsatz (ii) und die obigen Gleichungen einen Widerspruch. Wie behauptet ist also w 6∈ A.

Zu 3 : w ∈ Z∗n mit ggT (w, n) = 1.

• Da v ∈ Zn ist ggT (v, n) = 1 und damit ggT (v, n1 ) = 1. Dem Beweis der Behauptung 2 folgend ist zugleich w ≡ v( mod n1 ). Damit ist ggT (w, n1 ) = 1. • Dem Beweis der Behauptung 2 folgend ist w ≡ 1( mod n2 ), also ggT (w, n2 ) = 1.

Somit ist gezeigt, dass A eine echte Untergruppe von Z∗n ist, die alle ,,L¨ ugner” enth¨alt. 2 Algorithm 14: Miller/Rabin Input: n, s ∈ N, n > 2 ungerade Output: n ∈ P ? Miller/Rabin(n,s) (1) for i:=1 to s (2) W¨ ahle a ∈ [n − 1] zuf¨ allig gleichverteilt (3) if Witness(a,n) = Ja (4) return ’nicht prim’ (5) return ’prim’

Aus dem vorangegangenen Satz folgt Korollar 5.29. Der Algorithmus von Miller/Rabin hat eine Fehlerwahrscheinlichkeit ≤ 2−s .

5.4

Markov-Ketten und Random Walks

VL 26.1.

Markov-Ketten sind stochastische Prozesse, die einfach strukturiert sind und dennoch in vielen Bereichen Anwendung findet. So kann man diese z.B. benutzen, um Elemente aus einer Menge (die m¨oglicherweise nicht vollst¨ andig bekannt ist) gem¨aß einer Verteilung auszuw¨ahlen. Unser Ziel ist es, dem Leser mit grundlegenden Begriffen und Konzepten dieser Theorie vertraut zu machen. Doch bevor wir Markov-Ketten formal definieren, wollen wir einige Beispiele betrachten: 5.4.1

Motivation und Beispiele

Motivation 1 1 2

1

'!&0"%$#o

1 2

'!&1"%$#

1 2

'!/ &2"%$#g

1 1 2

' &"%$# '! 3

¨ Im obigen Bild seien Zust¨ ande und Ubergangswahrscheinlichkeiten zwischen diesen dargestellt. Wir starten nun in Zustand 2 und verfolgen die Aufenthaltswahrscheinlichkeiten. Sei dazu X der jeweils aktuelle Zustand, und X ′ der neue. Es gilt: 1 P [X ′ = 2] = P [X = 2] · 0 + P [X = 3] · . 2 P [X = 2] =

1

0

P [X = 3] =

0

1

1 2 1 2

1 4 3 4

76

3 8 5 8

5 16 11 16

11 32 21 32

21 64 43 64

→ →

1 3 2 3

Man kann zeigen, dass die Aufenthaltswahrscheinlichkeiten gegen

1 2 3, 3

konvergieren.

Angenommen, wir h¨ atten mit Aufenthaltswahrscheinlichkeiten P [X = 2] = begonnen, dann bleibt mit P [X ′ = 2] =

P [X = 2] · 0 + P [X = 3] ·

P [X ′ = 3] =

2 3

diese Wahrscheinlichkeiten unver¨ andert. genannt.

1 2 3, 3

1 3,

P [X = 3] =

2 3

1 2 1 1 = · = 2 3 2 3

wird auch ”station¨are Verteilung”der Markovkette

Es stellt sich nun naheliegend die Frage, unter welchen Bedingungen und wie schnell eine Markovkette gegen welche station¨ aren Verteilungen konvergiert und ob diese station¨are Verteilung eindeutig ist. Motivation 2 2 Rechner A und B seien durch eine Datenleitung verbunden

Xt :=

(

1 0

Daten¨ ubertragung im t-ten Schritt erfolgreich sonst

P [Xt+1 = 1 |Xt = 1 ] = 0.9 P [Xt+1 = 0 |Xt = 1 ] = 0.1

P [Xt+1 = 1 |Xt = 0 ] = 0.2 P [Xt+1 = 0 |Xt = 0 ] = 0.8

0.8

'!&0"%$# g

0.9 0.2 0.1

'!' &1"%$#

Wichtig ist hierbei, dass die Wahrscheinlichkeiten unabh¨angig von der weiter zur¨ uckliegenden Vergangenheit sind. 5.4.2

Grundlegende Begriffe

Definition 5.30. Eine (endl.) Markov-Kette (mit diskreter Zeit) u ¨ ber der Zustandsmenge S = {0, . . . , n − 1} besteht aus • einer unendlichen Folge von Zufallsvariablen (Xt )t∈N0 , Xt ∈ S und Pn−1 • einer Startverteilung q0 = (q0 )0 , . . . , (q0 )n−1 mit (q0 )i ≥ 0 und i=0 (q0 )i = 1, d.h. P [X0 = i] = (q0 )i und ¨ • Ubergangswahrscheinlichkeiten mit der Eigenschaft: Ist I ⊆ {0, . . . , t − 1} eine beliebige Indexmenge und sind i, j, sk (k ∈ I) beliebige Zust¨ande, so gilt: P [Xt+1 = j |Xt = i ] = P [Xt+1 = j |Xt = i ∧ Xk = sk ∀k ∈ I ], (39) sofern P [Xt = i] 6= 0, P [Xk = sk ] 6= 0, k ∈ I. Man nennt eine Markov-Kette daher auch vergesslich (engl.: memoryless).

¨ Sind die Ubergangswahrscheinlichkeiten P [Xt+1 = j |Xt = i ] unabh¨angig von der Zeit t, so schreiben wir pij := P [Xt+1 = j |Xt = i ] 77

und malen

pi,j

i

'!' &j"%$#

Eine solche Markov-Kette heißt (zeit)homogen und P := (pij )0≤i,j
Beispiel. P =

0.8 0.2 0.1 0.9

, q0 = (0, 1)

¨ Lemma 5.31. Sei eine Markov-Kette mittels Ubergangsmatrix P und Startverteilung q0 gegeben. Bezeichne mit (qt )i = P [Xt = i]. Dann gilt qt+1 = qt · P Beispiel. P [X1 = 0] =

P [X0 = 0] · 0.8 + P [X0 = 1] · 0.1

P [X1 = 1] = (q1 )0

P [X0 = 0] · 0.2 + P [X0 = 1] · 0.9 0.8 0.2 (q1 )1 = (q0 )0 (q0 )1 · 0.1 0.9

¯ ·P B ¯ bzw. Beweis: Wir benutzen P [A] = P [A |B ] · P [B] + P A B P [A] =

n X i=1

wenn

Sn

i=1

P [A |Bi ] · P [Bi ],

Bi ⊇ A und Bi ∩ Bj = ∅ (totale Wahrscheinlichkeit). Dann ist P [Xt+1 = j] = ⇔ (qt+1 )j

=

⇔ qt+1

=

n−1 X

i=0 n−1 X i=0

P [Xt+1 = k |Xt = i ] · P [Xt = i] (qt )i · pij

qt · P 2

Korollar 5.32. (i) qt = qt−1 · P = qt−2 · P · P = . . . = q0 · P t (ii) qt+k = qt+k−1 · P = . . . = qt · P k (k)

(iii) pi,j := P [Xt+k = j |Xt = i ] = P k 5.4.3

i,j

Irreduzibilit¨ at

¨ Definition 5.33. Sei P eine Ubergangsmatrix einer Markov-Kette und π eine Wahrscheinlichkeitsverteilung. Ist π = π · P , so nennen wir π eine station¨ are Verteilung der Markov-Kette. Eine station¨ are Verteilung ist nicht immer eindeutig. Das wird uns das folgende Beispiel zeigen. Wir werden in diesem Abschnitt aber eine hinreichende Bedingung f¨ ur die Eindeutigkeit formulieren. 78

Beispiel. 1

'!&0"%$# o

1 1 2

'!&1"%$#

1 2

'!/ &2"%$#

(1, 0, 0) und (0, 0, 1) sind beides station¨are Verteilungen. Definition 5.34. Eine Markov-Kette heißt irreduzibel, wenn ∀i, j ∈ S eine Zahl k ∈ N existiert (k) mit pi,j > 0. (D.h. der gerichtete Graph ist (stark) zusammenh¨angend). Satz 5.35. Jede irreduzible Markov-Kette besitzt eine eindeutige station¨are Verteilung π. Die Gleichverteilung kann man mit Markov-Ketten recht einfach simmulieren, wie das folgende Lemma behauptet: Lemma 5.36. Eine Markov-Kette mit symmetrischer Matrix P hat die Gleichverteilung als station¨are Verteilung. 5.4.4

Periodizit¨ at

Eine irreduzible Markov-Kette konvergiert nicht notwendig gegen die (eindeutige) station¨are Verteilung, wie uns das folgende Beispiel zeigt. Beispiel. '!&0"%$#g

1 1

'!' &1"%$#

hat die station¨are Verteilung π = ( 12 , 12 ). Mit der Startverteilung q0 = (1, 0) erhielten wir q1 = (0, 1), q2 = (1, 0) . . . usw. Offenbar konvergiert die Kette wegen der Periodizit¨at“ nicht. ” (t)

Definition 5.37. Sei Ri := {t ∈ N|pii > 0} die Menge der Schrittzahlen mit einer positiven R¨ uckkehrwahrscheinlichkeit zum Zustand i“. Dann ist die Periode von Zustand i ist definiert als ” der ggT der Menge Ri , mit anderen Worten als die gr¨oßte Zahl l ∈ N mit (t)

{t ∈ N|pii > 0} ⊆ {0, l, 2l, 3l, . . .}. Hat der Zustand i die Periode 1, dann nennen wir ihn aperiodisch. Eine Markov-Kette heißt aperiodisch, wenn alle Zust¨ande aperiodisch sind. Beispiel. '!&0"%$#{ H¨atten alle angedeuteten Zust¨ande 0 bis 3 Periode von 4 zu 3 g¨abe, w¨are die

'! / &1"%$#

'!/ &2"%$#

'!/ &3"%$#

'!/ &4"%$#}

'!/ &5"%$#

'!/ &6"%$#

¨ Uberg¨ ange eine beliebige, positive Wahrscheinlichkeit, dann h¨atten die ¨ 4, die Zust¨ande 4 bis 6 Periode 3. Wenn es auch noch einen Ubergang Kette aperiodisch.

Bemerkung 5.38. (t)

(i) pii > 0 ⇔ ∃ geschlossener Weg der L¨ange t von i nach i. (ii) i ist periodisch, wenn pii > 0 (Schleife) oder i auf zwei geschlossenen Wegen der L¨ange l1 und l2 mit ggT (l1 , l2 ) = 1 liegt. Definition 5.39. Eine irreduzible, aperiodische Markov-Kette heißt ergodisch. Satz 5.40 (Fundamentalsatz f¨ ur ergodische Markov-Ketten). Jede ergodische MarkovKette konvergiert gegen eine eindeutige station¨are Verteilung lim qt = π.

t→∞

79

5.4.5

Konvergenzgeschwindigkeit von Markovketten – Kanonische Pfade

¨ Bis auf Widerruf bezeichne M eine ergodische Markovkette auf dem Zustandsraum S mit Ubergangsmatrix P = (pxy ) und es sei π die station¨are Verteilung von M . Weiterhin gelte: Q(x, y) := πx · pxy = πy · pyx und pxx ≥

1 2

∀x, y ∈ S.

Als Abweichung zwischen einer Verteilung und der station¨aren Verteilung definieren wir: Definition 5.41. (variation distance) X (t) p − π ∆x (t) = max y x,y S ′ ⊆S y∈S ′

Damit l¨aßt sich nun die Zeit, die die MK zum ,,Mischen” braucht als Definition 5.42. (mixing time) τx (ǫ) = min{t : ∆x (t′ ) ≤ ǫ

∀t′ ≥ t}.

definieren. Durch den folgenden Ansatz kann nun eine obere Schranke f¨ ur die mixing time ermittelt werden. Man betrachte dazu M als einen gerichteten Graphen (S, E), mit (x, y) ∈ E ⇔ Q(x, y) > 0. Angenommen, es w¨ are f¨ ur jedes Paar (x, y) ∈ S × S ein gerichteter x − y − P f ad γxy definiert und sei Γ := {γxy : (x, y) ∈ S × S} die Familie aller dieser Pfade. Definition 5.43. Die Last von Γ ist definiert als: ρ := ρ(Γ) := max

(u,v)∈E

1 Q(u, v)

X

γxy :(u,v)∈γxy

πx · πy · |γxy |.

Die mixing time l¨ aßt sich nun mit Hilfe der Last beschr¨anken: Satz 5.44. F¨ ur alle x ∈ S gilt:

1 1 . τx (ǫ) ≤ ρ · ln + ln πx ǫ

Dieser Satz bleibt hier unbewiesen. Wir betrachten stattdessen eine Anwendung: Vorlesung 1.2. Satz 5.45. Sei eine bit-flipping Markov-Kette auf dem vollst¨andigen Hyperw¨ urfel {0, 1}n mit einer Loop-Wahrscheinlichkeit von 1/2 gegeben. Dann existiert eine Familie Γ von Pfaden mit ρ(Γ) ≤ n2 . Beweis: Seien x := (x0 , . . . , xn−1 ), y := (y0 , . . . , yn ) ∈ {0, 1}n zwei beliebige Knoten im Hyperw¨ urfel. Der Pfad γxy := (e0 , . . . , en−1 ) ist durch folgende Regel konstruiert: ei := ((y0 , . . . , yi−1 , xi , xi+1 , . . . , xn−1 ), (y0 , . . . , yi−1 , yi , xi+1 , . . . , xn−1 )), i = 0, . . . , n − 1. Das heißt, der Pfad γxy entsteht dadurch, dass wir vom Anfangsknoten x erst das 0-te Bit x0 , dann das 1-te Bit, usw. durch das 0-te Bit y0 , dann das 1-te Bit, usw. von y ersetzen. Wenn xi = yi ist, so tritt eine Schleife auf. Ansonsten wird ein bit-flip vollzogen. Um die Last ρ abzusch¨ atzen zu k¨ onnen, m¨ ussen wir noch f¨ ur eine beliebige Kante im Hyperw¨ urfel die Anzahl der Pfade bestimmen, die diese Kante benutzen. Sei e := (w, w′ ) eine beliebige Kante im Hyperw¨ urfel mit w := (w0 , . . . , wi , . . . , wn−1 ), w′ := (w0 , . . . , wi′ , . . . , wn−1 ) ∈ {0, 1}n. Per constructionem enth¨ alt ein Pfad γxy die Kante e genau dann, wenn xi = wi , . . . , xn−1 = wn−1 80

f¨ ur x und y0 = w0 , . . . , yi−1 = wi−1 , yi = wi′ f¨ ur y gilt. Dadurch sind bei x die ersten i Bits x0 , . . . , xi−1 und bei y die letzten n − i − 1 Bits yi+1 , . . . , yn−1 frei w¨ahlbar. Somit existieren 2i viele M¨oglichkeiten f¨ ur x und 2n−i−1 f¨ ur y. Damit enthalten 2n−1 Pfade e, sei Γe die Menge aller dieser Pfade. Nun gilt: 1 1 Q(e) = πw · pww′ ≥ 2−n · und |γxy | = n. · 2 n F¨ ur die Last ρ(Γe ) folgt unmittelbar die Behauptung: ρ(Γe ) = max n

X 1 · πx πy |γxy | Q(e)

≤ 2 2n · 2

n−1

= n2 .

γxy ∈Γe

· 2−n 2−n n

2 Aus Satz 5.44 und Satz 5.45 folgt sofort folgende obere Schranke f¨ ur die Mischzeit (mixing time). Korollar 5.46. F¨ ur alle x ∈ S gilt: 1 1 1 2 2 = n n · ln 2 + ln τx (ε) ≤ n ln −n + ln 2 ε ε Tats¨achlich weiss man, dass die Mischzeit von der Gr¨oßenordnung Θ(n(ln n + ln ε−1 )) ist. Im Beweis vom Satz 5.45 haben wir explizit die Kenntnis der Gr¨oße von πx bzw. |S| benutzt – aber eigentlich nur, um sie anschliessend gegeneinander zu k¨ urzen. Dieser Ansatz funktioniert auch in vielen F¨allen, in denen man die Gr¨ oße des Zustandsraums nicht kennt. Wir skizzieren hier nur kurz das Vorgehen: Seien die Pfade γxy , die Kante e = (w, w′ ) und die Familie Γe wie im Beweis des Satzes 5.45 definiert. Sei weiterhin cp(e) := {(x, y) : γxy ∈ Γe } und die Abbildung ηe : cp(e) → S sei definiert durch ηe (x, y) := u := (u0 , . . . , un−1 ) := (x0 , . . . , xi−1 , wi , yi+1 , . . . , yn−1 ). Die Abbildung ηe ist injektiv auf cp(e), denn wir kennen e und damit i, wi und wi′ . Zu gegebenem u setzen wir also x := (u0 , . . . , ui−1 , wi , wi+1 , . . . , wn−1 ) und y := (w0 , . . . , wi−1 , wi′ , ui+1 , . . . , un−1 ). Somit ist ηe injektiv. Da πx πy = πw πηe (x,y) ist, folgt f¨ ur die Last: ρ(Γe ) = max e

X 1 · πx πy |γxy | Q(e) γxy ∈Γe

X 1 = max · πw πηe (x,y) |γxy | πw pww′ = max n pww′ ≤ 2n2 .

≤

5.4.6

1

pww′

γxy ∈Γe

·

X

πηe (x,y) n

γxy ∈Γe

(Injektivit¨at von ηe )

Z¨ ahlen mit Markov-Ketten

Als letztes Anwendungsbeispiel betrachten wir nun eine Version des Rucksackproblems und werden zeigen, wie dieses mit Hilfe von Markov-Ketten zu l¨osen ist. Gegeben sei ein Gewichtsvektor: a = (a0 , a1 , . . . an−1 ) ∈ Nn und eine Gewichtsschranke b ∈ N. n−1 Pn−1 P ai xi ≤ b, b ≤ j=0 aj existieren. Wir wollen wissen, wieviele Vektoren x ∈ {0, 1}n mit a · x = i=0

81

OBdA sei a0 ≤ a1 ≤ · · · ≤ an−1 . und außerdem Vektoren x. Wir betrachten den naiven Ansatz:

Pn−1 j=0

aj > b. Sei N die gesuchte Anzahl der

1. Ansatz n

W¨ahle gleichverteilt zuf¨ allig einen ( Vektor x ∈ {0, 1} 2n falls a · x ≤ b Setze eine Zufallsvariable Y := 0 sonst Der Erwartungswert von Y ist dann:

E [Y ] = 0 · P [ax > b] + 2n · P [ax ≤ b] = 2n ·

N =N 2n

Das zuf¨allige Ausw¨ ahlen eines Vektors f¨ uhren wir ausreichend oft durch und bilden den Durchschnitt. Diese Strategie versagt jedoch, wenn die Anzahl ,,g¨ ultiger” Vektoren im Verh¨altnis zur Anzahl aller m¨ oglichen Vektoren zu klein ist. n−mal

z }| { Ist z.B. a = (1, . . . , 1) und b = n3 , so ist a · x ≤ b nur, wenn maximal n3 der Komponenten (bzw. Bits) von x gleich 1 sind. Es l¨ aßt sich zeigen, dass die erwartete Anzahl ,,Versuche”, bis wir zum ersten Mal einen ,,g¨ ultigen” Vektor finden, exponentiell in n ist. (Bis dahin ist Y = 0). Das m¨oge ¨ der Leser als Ubungsaufgabe tun. 2. Ansatz Wir setzen b0 := 0 und f¨ ur i ∈ {1, . . . , n}:

  i−1   X aj bi := min b,   j=0

Dann ist bn = b. F¨ ur jede Schranke bi definieren wir die Menge der ,,g¨ ultigen” Vektoren n

S(bi ) := {x ∈ {0, 1} : a · x ≤ bi } . ¨ Auf S(bi ) definieren wir nun eine Markov-Kette M (bi ) mit Uberg¨ angen vom Zustand x zum Zustand y, die wie folgt arbeitet:

(i) Mit Wahrscheinlichkeit

1 2

sei x = y, das heißt, wir bleiben im Zustand x.

(ii) Andernfalls (also ebenfalls mit Wahrscheinlichkeit 21 ) w¨ahlen ein i ∈ [0, n − 1] gleichverteilt zuf¨allig aus. Erhalte den(Zustand y ′ := (x0 , . . . , xi−1 , 1 − xi , xi+1 , . . . , xn−1 ), und gehe in den Folgezuy ′ , wenn a · y ′ ≤ bi stand y := x, sonst Bemerkung 5.47. Wir erhalten so eine symmetrische Markov-Kette auf einem Hyperw¨ urfel, der durch die Hyperebene ax = bi abgeschnitten wird. Diese ist aperiodisch, da wir Schleifen laufen k¨onnen. Ferner ist M irreduzibel, da wir von jedem Zustand zum Nullvektor und von diesem zu jedem anderen Zustand laufen k¨onnen. Folglich konvergiert M gegen die Gleichverteilung auf S(bi ). Es gilt |S(b0 )| = |{0, · · · , 0}| = 1,

|S(bn )| = |S(b)| = |S| = N.

82

und wir k¨onnen |S(b)| aufspalten in: |S(bn )| |S(bn−1 )| |S(b1 )| · ··· · |S(b0 )| |S(bn−1 )| |S(bn−2 )| |S(b0 )| | {z }

|S(b)| = |S(bn )| =

=1

Vorlesung 2.2. Zur weiteren Absch¨ atzung von |S| ben¨ otigen wir folgende Ungleichungskette: |S(bi−1 )| ≤ |S(bi )| ≤ (n + 1) · |S(bi−1 )|. Die erste Ungleichung gilt trivialerweise. Der Nachweis der zweiten ist etwas schwieriger. Man betrachte die Abbildung bei der jedem x ∈ S(bi ) ein x′ zugeordnet wird, das dadruch entsteht, dass die rechteste 1 in x durch eine 0 ersetzt wird. Wir behaupten, dass x′ ∈ S(bi−1 ), woraus die behauptete Ungleichung sofort folgt. Behauptung: x′ ∈ S(bi−1 ). Sei j der Index der Komponente von x′ , die die rechteste 1 enth¨alt. Fall a):

Pi−2

k=0

ak ≤ b. Dann ist l X

bl+1 =

∀l = 1, . . . , i − 2,

ak

k=0

Wenn j ≤ i − 2, dann j ≥ i − 1, dann

Pn−1 k=0

n−1 X k=0

Fall b):

Pi−2

k=0

ak x′k ≤

Pj

k=0

n−1 X

ak x′k ≤ (

k=0

(40)

(40)

ak = bj+1 ≤ bi−1 , also x′ ∈ S(bi−1 ). Und wenn

ak xk ) − aj ≤ bi − ai−1 ≤ bi−1 .

ak > b. Dann ist bi−1 = b = bi und es ist nichts zu zeigen, denn n−1 X k=0

ak x′k ≤

n−1 X k=0

ak xk ≤ bi = b = bi−1 ,

und damit ist der Beweis der Behauptung und der Absch¨atzung abgeschlossen. Nun setzen wir ρi :=

|S(bi−1 )| |S(bi )|

Wir m¨ ussen also, um die |S| bestimmen zu k¨onnen, jeden einzelnen dieser Faktoren ρi approximieren. Dies tun wir folgendermaßen: F¨ ur jedes M (bi ) lassen wir M (bi ) solange laufen, bis Gleichverteilung (ann¨ahernd) erreicht ist und (i) setzen eine Zufallsvariable Yj auf 1, gdw. der erreichte Zustand in S(bi−1 ) enthalten ist. Dies wiederholen wir t-mal und approximieren so das Verh¨altnis zwischen |S(bi )| und |S(bi−1 )|. Wir definieren also f¨ ur jede Ausf¨ uhrung der MK M (bi ), d.h. ∀j ∈ {1, ..., t}, die Zufallsvariable: ( 1, falls die MK in S(bi−1 ) endet. (i) Yj := 0, sonst (d.h. in S(bi )/S(bi−1 )). Der Erwartungswert f¨ ur beliebige j ist: i h |S(bi−1 )| (i) = ρi . = P [M endet in S(bi−1 )] = E Yj |S(bi )| und f¨ ur die Varianz gilt:

h i (i) Var Yj = ρi (1 − ρi ). 83

(i)

Definiert man nun eine Zufallsvariable, die den Durchschnittswert der Yj Xi :=

Pt

(i)

Var [Xi ] = Var

Yj

t

t · ρi = ρi t

E [Xi ] = und wegen Unabh¨ angigkeit der Yj

(i)

j=1

so ist der Erwartungswert:

(f¨ ur ein bi ) bestimmt:

gilt:

" Pt

(i)

j=1

Yj

t

#

=

i ρ (1 − ρ ) h 1 X i i (i) = Var Y j t2 j t

Nun werten wir die Ergebnisse u ¨ ber alle Markov-Ketten M (bi ) in der Zufallsvariable Z: Z :=

n Y

Xi

i=1

Da auch die Xi unabh¨ angig sind, gilt: E [Z] = und Var [Z] =

Y

E [Xi ] =

Y

ρi =

1 . |S|

Y Y Y Y 2 2 2 E [Xi ] + Var [Xi ] − E [Xi ] = ρ2i + Var [Xi ] − ρi .

Setzt man nun t := 17ǫ−2 (n + 1)n, dann ist

Var [Xi ] ρi (1 − ρi ) 1 n+1 ǫ2 = ≤ ≤ = . 2 2 ρi tρi tρi t 17n Damit sch¨atzen wir wie folgt ab: n Y ρ2 Y ǫ2 ǫ2 ǫ2 Var [Z] Y ρ2i + Var [Xi ] i = − 1 = 1 + 1 + − ≤ . − 1 ≤ ρ2i ρ2i 17n 17n 16 E [Z]2

(41)

Die letzte Ungleichung m¨ oge der Leser durch eigenes Nachrechnen u ufen. ¨ berpr¨ Nach Chebyshev (siehe Satz 2.10) gilt nun: Var [Z] δ2 ǫ und mit δ := 2 E [Z] und (41) sch¨ atzen wir den Erwartungswert f¨ ur Z ab: P [E [Z] − δ ≤ Z ≤ E [Z] + δ] ≥ 1 −

i h ǫ Var [Z] ǫ P (1 − )E [Z] ≤ Z ≤ (1 + )E [Z] ≥ 1 − 2 2 2 2 E [Z] · ǫ4 ≥1− =

3 4

ǫ2 · 4 16 · ǫ2

Unter der Annahme, dass die Markov-Ketten M (bi ) sofort“ gegen die Gleichverteilungen kon” vergieren, haben wir nach n · t = O(ǫ−2 n3 ) Versuchen mit Wahrscheinlichkeit ≥ 43 die Gr¨oße 1 E [Z] = |S| durch Z bis auf einen Faktor ǫ approximiert. 84

5.5

SAT-Algorithmen

3-SAT ist das erste Problem, f¨ ur das die NP-Vollst¨andigkeit nachgewiesen wurde. Der zur Zeit beste deterministische Algorithmus hat eine Laufzeit von O(1, 481n ). Ziel dieses Abschnitts ist es, f¨ ur einen randomisierten Algorithmus eine Laufzeit von O(1, 334n ) nachzuweisen. Dazu schauen wir uns erst einmal einen Algorithmus f¨ ur das 2-SAT Problem an. 5.5.1

2-SAT

Bei dem polynomiell l¨ osbaren 2-SAT Problem ist eine Formel F mit n Variablen gegeben, in der jede Klausel genau 2 Variablen enth¨ alt, z.B. (x3 ∨ x1 ) ∧ (x7 ∨ x79 ) ∧ . . . . Gesucht ist eine erf¨ ullende Belegung B, z.B. x1 = 1, . . . , x7 = 0, . . . , xn = 0. Algorithm 15: Randomisiertes 2-Sat Input: Eine 2-SAT Formel Output: erf¨ ullende Belegung oder unerf¨ ullbar rand 2-Sat(F ) (1) w¨ ahle beliebige Startbelegung A (2) while ∃ unerf¨ ullte Klausel“ und kein Stopp-Signal“ ” ” (3) w¨ ahle beliebige unerf¨ ullte Klausel (4) w¨ ahle zuf¨ allig gleichverteilt eine der beiden Variablen (5) negiere ihren Wert in A (6) if kein Stopp-Signal“ ” (7) return A (8) else (9) return unerf¨ ullbar

Der Algorithmus rand 2-Sat stoppt, wenn er eine erf¨ ullende Belegung gefunden hat oder das StoppSignal eintritt. D.h. er kann nur im letzten Fall einen Fehler machen und zwar genau dann, wenn die Formel erf¨ ullbar ist. Wie groß diese Fehlerwahrscheinlichkeit ist, h¨angt davon ab, wieviel Zeit man rand 2-Sat f¨ ur die Suche nach einer erf¨ ullenden Belegung gibt, bevor das Stopp-Signal eintritt. Wir zeigen den Satz 5.48. Ist die 2-SAT Formel F erf¨ ullbar, dann findet rand2-Sat eine erf¨ ullende Belegung B in erwartet ≤ n2 Schritten. Beweis: Sei F eine erf¨ ullende 2-SAT Formel mit n Variablen und B eine erf¨ ullende Belegung f¨ ur F . Seien weiterhin A0 := A, A1 , A2 , . . . die Belegungen, die rand 2-Sat erzeugt und sei fl die Anzahl der Variablen, deren Belegung in Al und B nicht u ¨ bereinstimmen. Da F n Variablen hat, gilt 0 ≤ fl ≤ n. Der Algorithmus stoppt sp¨ atestens dann, wenn fl = 0 ist, weil dann Al = B gilt. Da rand 2-Sat in jedem Schleifendurchlauf die Belegung genau einer Variable negiert, ist fl+1 = fl ± 1. Sei C die Klausel von F , die im (l + 1)-ten Schritt gew¨ahlt wurde. Somit erf¨ ullt die Belegung Al die Klausel C nicht. Daraus folgt, dass sich mindestens eine der beiden Variablen in ihrer Belegung von Al zu B unterscheidet. Es gilt daher: 1 2

P [fl+1 = fl − 1] ≥ Wir betrachten jetzt folgende Markov-Kette: 1 2

1

'!&1"%$#^

'!&0"%$#^ 1 2

1 2

...

1 2

^

1

2 WPnQ V−R U1TS \ 1 2

(/.)n-*+,

1

Dabei entspricht ein Zustand i eine Menge von Belegungen f¨ ur F , die sich in genau i Variablenbelegungen zu B unterscheiden. Also die Belegung Al geh¨ort zum Zustand fl . Wie man leicht sieht, 85

gilt: E [#Runden bis fl = 0] ≤ E [#Schritte von n bis 0]

Wir setzen nun di := E [#Schritte von i bis 0]. Daraus ergibt sich nun folgende Rekursion f¨ ur die di ’s: d0 = 0, 1 1 di = (di−1 + 1) + (di+1 + 1), ∀i ∈ [n − 1], 2 2 dn = dn−1 + 1. ¨ ¨ Ubung 5.49. Uberpr¨ ufen Sie, dass diese Gleichungen di = 2in− i2 f¨ ur alle i = 0, . . . , n impliziert. Damit l¨aßt sich die erwartete Anzahl von Schleifendurchl¨aufen folgendermaßen absch¨atzen: E [#Runden bis fl = 0] ≤ E [#Schritte von n bis 0] = dn = 2n2 − n2 = n2 . 2 Als Folgerung erhalten wir nun das Korollar 5.50. Wenn man rand2-Sat nach 2n2 Runden abbricht, falls er keine erf¨ ullende Belegung gefunden hat und behauptet, dass die Formel unerf¨ ullbar ist, dann gilt f¨ ur die Fehlerwahrscheinlichkeit: 0 , falls F unerf¨ ullbar P [rand2-Sat macht Fehler bei der Formel F ] ≤ 1 , falls F erf¨ u llbar 2 5.5.2

3-SAT

Bei 3-SAT Problem ist eine Formel gegeben, in der jede Klausel genau drei Literale enth¨alt. Wie vorher ist eine erf¨ ullende Belegung gesucht. Durch zwei Modifikationen in rand 2-Sat entsteht unserer rand 3-Sat Algorithmus f¨ ur 3-SAT. Der Hauptunterschied besteht darin, dass die Startbelegung nicht beliebig gew¨ahlt, sondern zuf¨allig gleichverteilt. Und nat¨ urlich w¨ ahlt der Algorithmus nicht mehr aus zwei, sondern aus drei Variablen aus. Algorithm 16: Randomisiertes 3-Sat Input: Eine 3-SAT Formel Output: erf¨ ullende Belegung oder unerf¨ ullbar rand 3-Sat(F ) (1) w¨ ahle zuf¨ allig gleichverteilt eine Startbelegung A (2) while ∃ unerf¨ ullte Klausel“ und kein Stopp-Signal“ ” ” (3) w¨ ahle beliebige unerf¨ ullte Klausel (4) w¨ ahle zuf¨ allig gleichverteilt eine der drei Variablen (5) negiere ihren Wert in A (6) if kein Stopp-Signal“ ” (7) return A (8) else (9) return unerf¨ ullbar

F¨ ur die folgenden Aussagen sei fl wie im Satz 5.48 definiert. Die Markov-Kette sieht dann wie folgt aus: 2 2 2 1 3 3 3 '!&0"%$# '!&1"%$# WPnQ V−R U1TS (/.)n-*+, ... ^ ^ ^ \ 1 1 1 3

3

3

86

1

Als erstes wollen folgende Situation f¨ ur eine 3-SAT Formel F mit n Variablen und einer erf¨ ullenden Belegung B betrachten. Der Algorithmus rand 3-Sat startet mit einer Belegung A, die sich in genau n/4 Belegung der Variablen zu B unterscheidet. In jedem Schritt erwischt“ rand 3-Sat eine dieser ” Variablen und negiert sie, so dass er nach n/4 viele Schritte die erf¨ ullende Belegung B gefunden hat. Mit anderen Worten: er macht in keinen Schritt einen Fehler. Wie groß die Wahrscheinlichkeit dieser Abfolge ist, beantwortet das nachfolgende Lemma. Lemma 5.51. Wenn die 3-SAT Formel F mit n Variablen erf¨ ullbar ist, dann gilt   n n/4 ^ n 2   fi = − i ≥ P 4 3 i=0 .

Beweis: Sei F eine 3-SAT Formel mit n Variablen, der erf¨ ullenden Belegung B und der Startbelegung A.   n/4 h ^ n ni P  fi = − i = P f0 = · P [fi = fi−1 − 1, ∀i ∈ [n − 1]] 4 4 i=0 2 n/4 n 1 1 ≥ · 2 3 n/4 n! = n 3n 2−n 3−n/4 ! 4 4 !

Nach Stirling gilt m! ≈

m m . e

≈

n n/4

nn e−n

3n/4 −3n/4 · 3n e 4 4 n/4+3n/4 −3n/4 −n −n/4

=4 n 2 = 3

e−n/4 3

2

2−n 3−n/4

3

2 Vorlesung 9.2. Wenn wir rand 3-Sat mehr Zeit geben und ihm damit ihm Irrwege“ zugestehen, dann bekommen ” wir ein besseres Resultat. Lemma 5.52. Wenn die 3-SAT Formel F mit n Variablen erf¨ ullbar ist, dann gilt n+4 3 . P [∃i ∈ [3n] : fi = 0] ≥ 4 Beweis: Sei F eine 3-SAT Formel mit n Variablen, der erf¨ ullenden Belegung B und der Startbelegung A. Sei pj := P [f3j = 0| f0 = j] die Wahrscheinlichkeit, dass rand 3-Sat nach h¨ochstens 3j Schritten die Belegung B gefunden hat, wenn die Startbelegung A sich genau in j Variablenbelegungen von B unterscheidet. Um pj nach unten zu beschr¨anken, betrachten wir Wege der L¨ange 2i + j von f0 = j zu f2i+j = 0, die i ≤ j Schritte nach rechts und i + j Schritte nach links machen. ¨ Ubung 5.53. Zeigen Sie: Es gibt genau j + 2i j j + 2i i derartige Wege. 87

Dann ist pj ≥

j X j + 2i i=0

i

j · j + 2i

i i+j 1 2 . 3 3

Die Gesamtschrittzahl f¨ ur eine dieser M¨ oglichkeiten ist 2i + j ≤ 3j. Daraus folgt f¨ ur die Wahrscheinlichkeit, dass rand 3-Sat nach h¨ ochstens 3n Schritten eine erf¨ ullende Belegung gefunden hat: n n n X X n 1 P [f0 = j] pj = · pj P [∃i ∈ [3n] : fi = 0] ≤ j 2 j=0 j=0 ≥

i i+j j n X j n −n X j + 2i 1 2 2 · · i j j + 2i 3 3 i=0 j=0

Da wir eine untere Schranke haben wollen, k¨onnen wir die innere Summe mit den positiven Summanden grob“ durch den letzten Summanden i = j nach unten absch¨atzen. ” j j+j n X 1 2 n −n j + 2j j · 2 · ≥ j + 2j 3 3 j j j=0 n 1 X n 3j 2j = 2−n 3 j=0 j j 33j n 1 X n (3j)! 2j = 2−n 3 j=0 j j!(2j)! 33j n X n (3j)3j e−3j · 2j −n 1 ≈2 (Stirling) 3 j=0 j j j e−j · (2j)2j e−2j · 33j n j 1 1X n = 2−n 3 j=0 j 2 n 1 1 = 2−n · 1 + (Binomischer Lehrsatz) 3 2 n n+4 1 3 3 ≥ . = 3 4 4 2 Wir wissen jetzt, dass rand 3-Sat mit einer Mindestwahrscheinlichkeit von (3/4)n eine erf¨ ullbare Belegung f¨ ur eine erf¨ ullbare 3-SAT Formel mit n Variablen findet, wenn er 3n Schritte machen darf. Die Fehlerwahrscheinlichkeitdes Algorithmus kann verringert werden, indem wir ihm mehrmals f¨ ur eine Formel laufen lassen. Da rand 3-Sat die Startbelegung zuf¨allig gleichverteilt w¨ahlt, ist die Unabh¨angigkeit der einzelnen L¨ aufe garantiert. Korollar 5.54. Wenn rand3-Sat in allen t = t′ · (4/3)n+4 L¨aufen nach 3n Runden abbricht, falls er keine erf¨ ullende Belegung gefunden hat und behauptet, dass die Formel unerf¨ ullbar ist, dann gilt f¨ ur die Fehlerwahrscheinlichkeit: 0 , falls F unerf¨ ullbar ′ P [rand3-Sat macht Fehler bei der Formel F ] ≤ e−t , falls F erf¨ ullbar Beweis: Offenbar kann der Algorithmus nur einen Fehler machen, wenn die Formel erf¨ ullbar ist. Sei F eine eine solche 3-SAT Formel. F¨ ur diese gilt dann: n+4 !t 3 (Lemma 5.52) P [rand3-Sat macht Fehler bei der Formel F ] ≤ 1 − 4 n+4

≤ e −( 4 ) 3

=e

n+4

−( 34 ) ′

= e−t . 88

t

(nach (2.13)) n+4 ′

( ) 4 3

t

2 Wenn man t′ ≪ (4/3)n+4 w¨ ahlt, so hat der randomisierte Algorithmus rand 3-Sat die behauptete Laufzeit O(1, 334n ).

5.6

Ausblick: Randomisiertes Runden (Max-Cut)

F¨ ur einen gegebenen Graph G = (V, E) ist max |{{x, y} ∈ E |x ∈ S, y ∈ V \ S }| S⊆V

gesucht. Dieses Problem ist NP-vollst¨ andig. Proposition 5.55. Es gibt immer einen Cut mit mindestens

1 2

|E| Kanten.

Beweis: [Beweis (probabilistische Methode)]F¨arbe die Knoten zuf¨allig mit Wahrscheinlichkeit 21 mit Farbe +1 (dann geh¨ ore der Knoten zu S) oder −1 (dann geh¨ore der Knoten zu V \ S). Dann definiere den Cut als die Menge der Kanten, die zwischen S und V \ S verlaufen, C = E (S, V \ S) . Sei {x, y} ∈ E beliebig. Dann ist

P [{x, y} ∈ C] =

also

1 , 2

1 E [#C] = |E| · . 2

Es gibt also eine F¨ arbung (d.h. einen Cut) mit mindestens

1 2

|E| Kanten.

2

Gewichtete Variante: F¨ ur einen gegebenen Graph G = (V, E) mit V = [n] und Gewichten wij ∈ R+ ∀i, j ∈ [n] ist   1 X  max wij (1 − yi yj ) y1 , . . . , yn ∈ {−1, +1} (Q) 2  1≤i<j≤n

gesucht. Der Term wij (1 − yi yj ) tr¨ agt zur Summe 2wij bei, wenn sgn (yi ) 6= sgn (yj ) ist, ansonsten ist der Beitrag 0.

Relaxierte Variante: F¨ ur einen gegebenen Graph G = (V, E) mit V = [n] und Gewichten wij ∈ R+ ∀i, j ∈ [n] ist    1 X (R) wi,j 1 − viT vj v1 , . . . , vn ∈ Sn max  2 1≤i<j≤n

gesucht, wobei Sn = { x ∈ Rn | kxk2 = 1}.

Das Problem (Q) entspricht dann dem Problem (R), indem man die vi auf (±1, 0, . . . , 0) einschr¨ankt. Also ist Opt (Q) ≤ Opt (P ) . Tats¨achlich kann man (R) effizient optimal mit Semidefiniter Programmierung k¨onnen. Wie hilft uns das f¨ ur die L¨ osung von (Q)?. (i) L¨ose (R) optimal. (ii) W¨ahle zuf¨ allig r ∈ Sn . (iii) Setze S := i ∈ [n] viT r ≥ 0 . 89

Satz 5.56. Sei W das Gewicht des erzielten Cuts, E [W ] der entsprechende Erwartungswert, Opt (Q) das Gewicht des optimalen Cuts in Q. Dann gilt E [W ] ≥ 0.87856 . . . Opt (Q) Beweis: Erinnerung: Zu v, w ∈ Sn ist v T w = kvk · kwk · cos (∢ (v, w)) . | {z } =1

Also u ¨berlegt man sich, dass sgn viT r 6= sgn vjT r , genau dann eintritt, wenn vi und vj auf verschiedenen Seiten der Hyperebene liegen, die senkrecht zu r steht. Wir k¨onnen also E [W ] wie folgt absch¨atzen: (i) F¨ ur einen zuf¨ alligen Vektor r ∈ Sn ist

∢ (vi , vj ) arccos viT vj = . P sgn viT r 6= sgn vjT r = π π

(ii) Dann ist X

E [W ] =

1≤i<j≤n

X

=

1≤i<j≤n

X

=

wi,j P [(i ∈ S, j 6∈ S) ∨ (i 6∈ S, j ∈ S)] wi,j P sgn viT r 6= sgn vjT r wi,j

1≤i<j≤n

arccos viT vj π

(iii) Setze nun α := min

0≤β≤π

Schreibe dann y := cos β und erhalte

β 2 > 0.87856 . . . π 1 − cos β 2 arccos y , −1≤y≤1 π 1 − y

α = min d.h. es ist

1 arccos y (1 − y) α ≤ 2 π

∀y ∈ [−1, 1] .

(iv) Setze dies in (2) ein und erhalte E [W ] ≥ =

(v) Also ist E [W ] ≥ Opt (Q)

α 2

P

i<j

X

1≤i<j≤n

α 2

X

1≤i<j≤n

wi,j 1 − viT vj

Opt (Q)

1 1 − viT vj α 2 wi,j 1 − viT vj .

wi,j

=α

Opt (P ) Opt (P ) ≥α = α. Opt (Q) Opt (P ) 2

90

Das folgende Thema werden wir in der Vorlesung leider nicht behandeln k¨onnen und verlagern ¨ es daher in die Ubungen.

5.7

Routing

Gegeben sei ein gerichteter Graph G = ([n], A) mit der Knotenmenge [n] = {1, . . . , n} und der Kantenmenge A ⊆ [n] × [n] sowie ein Auftrag“ in Form einer Permutation σ = (σ1 , . . . , σn ) ∈ Sn . ” Habe ferner zu Beginn jeder Knoten i ∈ [n] das Paket vi , welches zum Knoten σi = σ(i) transportiert werden soll. Das Routing Problem besteht darin Algorithmen zu finden, die diesen Transport in m¨oglichst kurzer Zeit realisieren und dabei folgende Regeln beachten: • In jeder Runde schickt jeder Knoten h¨ochstens ein Paket pro ausgehender Kante an jeden seiner Nachbarn. Weitere Pakete in die gleicher Richtung warten in einer FIFO-Warteschlange (jeweils eine pro Kante). • Das Verschicken eines Pakets vi am Knoten j darf nur von σi (und von j sowie der Netzstruktur) abh¨ angen, nicht aber von den anderen σk . (Diese Eigenschaft eines Routing-Algorithmus wollen wir Naivit¨ at“ nennen (engl: oblivious) – die einzelnen Knoten wissen nichts u ¨ber die ” Pakete im Rest des Netzwerkes.) Im folgenden schr¨ anken wir das Problem ein und untersuchen das Routing-Problem f¨ ur spezielle Graphen, die sogenannten Hyperw¨ urfeln. d

Definition 5.57. Den Graphen Qd mit Knotenmenge V = {0, 1} und Kantenmenge A = (x, y) ∈ V 2 | dist(x, y) = 1

nennen wir den d-dimensionalen Hyperw¨ urfel. (Man beachte, dass jeder Knoten d ausgehende und d eingehende Kanten besitzt.) Dabei ist f¨ ur (x, y) ∈ V 2 , x = (x1 , . . . , xd ), y = (y1 , . . . , yd ) dist(x, y) :=

d X i=1

|xi − yi |

die Hamming-Distanz. 5.7.1

Bit-Fixing-Strategie

Betrachten wir als Grundlage die naive Bit-Fixing-Strategie f¨ ur das Routing Problem im Hyperw¨ urfel. Diese verschickt das Paket vi vom Knoten i zu seinem Ziel σi nach folgendem Prinzip: • Vergleiche die Zieladresse σi mit dem Knoten j, bei dem vi sich gerade befindet. Falls diese nicht u ¨ bereinstimmen, so ,,flippe” das linkeste Bit von j, an dem sie sich unterscheiden und erhalte so die Adresse f¨ ur die n¨achste Station f¨ ur vi . M¨ochte man beispielsweise das Paket vom Knoten (0000) nach (1101) versenden, so muss es u ¨ber die Zwischenstationen (1000), (1100) versendet werden. ¨ Ubung 5.58. Finden Sie eine Permutation, f¨ ur die Bit-Fixing mindestens

5.7.2

2d/2 d/2

Runden braucht.

Randomisiertes Routing

Nun stellen wir den den Algorithmus Random Routing vor, welcher die Pakete zun¨achst an ein zuf¨alliges Ziel verschickt, um m¨ ogliche B¨osartigkeiten der gegebenen Permution zu entsch¨arfen, 91

und anschliessend die oben beschriebene Bit-Fixing-Strategie verfolgt. Es l¨aßt sich zeigen, dass dieser Algorithmus mit diesem einfachen Zusatz das schlechte Abschneiden der deterministischen Router relativiert. Algorithm 17: Random Routing Input: Permutation σ der Knoten des d-dimensionalen Hyperw¨ urfels Output: Ein Routing Protokoll (1) W¨ ahle zu jedem i ∈ V ein Zwischenziel ri ∈ V gleichverteilt und unabh¨ angig. (2) Route das Paket vi von i zu ri mittels Bit-Fixing. (3) Route das Paket vi von ri zu σi mittels Bit-Fixing.

Wir werden im folgenden zeigen, dass Random Routing mit gr¨oßter Wahrscheinlichkeit schnell terminiert - pr¨ aziser formuliert : Mit der Wahrscheinlichkeit von mindestens 1 − 21d erreicht jedes Paket sein Ziel in 8d Runden. Zur Analyse von Random Routing gen¨ ugt es, Phase (1) zu betrachten, da Phase (2) im wesentlichen mit Phase (1) u ¨ bereinstimmt. Sei dazu ρi = (e1 , ..., ek ) die Route des Pakets vi , die dieses gem¨aß (1) durchlaufen muss. Dann ist klar, dass die Anzahl Runden, die vi dazu ben¨otigt, durch time(vi ) = L¨ ange(ρi ) + delay(vi ) gegeben ist, wobei delay(vi ) angibt, wieviele Runden vi warten muss und L¨ ange(ρi ) durch d beschr¨ankt ist. Die schlechte Laufzeit kann also nur wegen langem Warten zustande kommen. Es gilt daher, delay(vi ) gut abzusch¨ atzen. Dazu ben¨otigen wir die folgenden Aussagen. ¨ Ubung 5.59. Zwei Routen, die sich treffen und dann wieder trennen, treffen sich nie wieder. ¨ Ubung 5.60. Sei ρi = (e1 , ..., ek ) die Route von vi und S die Menge aller Paketen außer vi , die mindestens eine Kante aus ρi benutzen. Dann gilt: delay(vi ) ≤ |S|. Setze

Hi,j :=

Aus 5.60 folgt delay(vi ) ≤

(

1 , falls ρi und ρj eine Kante gemeinsam haben 0 , sonst

Pn

j=1

Hi,j .

¨ Ubung 5.61. Da die ri unabh¨angig gew¨ahlt sind, sind die Hi,j auch unabh¨angig. Die Unabh¨angigkeit der Zufallsvariablen Hi,j ist f¨ ur uns wichtig, da wir die Chernoff-Absch¨atzung 3.3 (24) benutzen wollen. (Man beachte, dass die T (e angig sind.) Wir wenden uns nun l ) nicht unabh¨ i hP n der Absch¨atzung von E j=1 Hi,j zu.

Lemma 5.62. Sei i ∈ [n] ein beliebiger, fester Index. Dann gilt:   n X d Hi,j  ≤ . E 2 j=1

Beweis: Wir definieren die Zufallsvariable T (e), die f¨ ur eine beliebige Kante e die Anzahl Routen durch e angibt. Mit ρi = (e1 , ..., ek ) erhalten wir:



E

n X j=1

n X j=1

Hi,j 

≤

Hi,j  ≤

k X

T (el ) und demzufolge auch

l=1

  k X E T (el ). j=1

92

F¨ ur jede Kante e gilt nun E [Te ] = 1/2. Dies folgt aus   " n # X X d Te  = E n · d · E [Te ] = E  Laenge(ρl) = n · . 2 l=1

e∈E(Qn )

Dabei haben wir bei der ersten Gleichheit ausgenutzt, dass aufgrund der Symmetrie des Hyperw¨ ur alle Kanten e, f gilt und dass der Hyperw¨ urfel n · d Kanten besitzt. P urfels E [Te ] = E [Tf ] f¨ T ergibt offensichtlich die Gesamtl¨ a nge aller Routen, was die zweite Gleichung reche e∈E(Qn ) fertigt, w¨ahrend bei der letzten Gleichung die Linearit¨at des Erwartungswertes und die Tatsache, dass die durchschnittliche Routenl¨ ange d2 betr¨agt, auschlaggebend sind. Daraus erhalten wir:   " k # k n X X X d k µ := E  Hi,j  ≤ E T (el ) = E [T (el )] = ≤ . 2 2 j=1 l=1

l=1

2

Zur Anwendung der Chernoff-Absch¨ atzung 3.3 (24) setzen wir t = 3d, so dass 2eµ < 3d = t erf¨ ullt ist. Somit erhalten wir   n X P [delay(vi ) > 3d] ≤ P  Hi,j > 3d ≤ 2−3d . j=1

Daraus folgt:

P [jedes Paket kommt nach h¨ochstens d + 3d Runden an] ≥ 1 − P [Es gibt ein vi mit delay(vi ) > 3d] n X ≥1− P [delay(vi ) > 3d] i=1

≥ 1 − n · 2−3d = 1 − 2d · 2−3d = 1 − 2−2d .

Diese Analyse gilt wie erw¨ ahnt auch f¨ ur Phase (2) von Random Routing. Man erh¨alt als Gesamtfehlerwahrscheinlichkeit: P [∃vi mit time(vi ) > d + 3d in Phase (1)]+P [∃vi mit time(vi ) > d + 3d in Phase 2] ≤ 2·2−2d <

1 . 2d

Damit erhalten wir den Satz 5.63. Die Wahrscheinlichkeit, dass jedes Paket nach 8d Runden sein Ziel erreicht, ist mindestens 1 − 21d .

Literatur [1] N. Alon, J. Spencer, The Probabilistic Method, Wiley, 2000. [2] B. Bollob´ as, Random Graphs, Cambridge University Press, 2001. [3] Th. Cormen, Ch. Leiserson, R. Rivest, C. Stein Introduction to Algorithms, MIT Press, 2001. [4] R. Diestel, Graph Theory, Springer, 2000.

93

[5] Th. Emden-Weinert et al, Einf¨ uhrung in Graphen und Algorithmen, 1996. Zu erhalten unter http://www.informatik.hu-berlin.de/Institut/struktur/algorithmen/ga/ [6] R. Motwani, P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995. [7] Th. Schickinger, A. Steger, Diskrete Strukturen 2, Springer, 2001.

94