Operations Research und Wirtschaftsinformatik Prof. Dr. P. Recht // Dipl. Wirt.-Math. Eva-Maria Sprengel DOOR Graphen- und Netzwerkoptimierung: Operations Research II b Übungsblatt 12 Aufgabe 40 Betrachten Sie bitte erneut den Graphen aus Aufgabe 39 und das darin bereits durch fette Kanten angegebene Matching. 2 1 5 3 4 7 6 10 9 8 11 12 13 Wenden Sie die Ungarische Methode auf den Graphen an, wobei als Knoten v0 im ersten Schritt zunächst der Knoten 1 dienen soll. Führen Sie das Verfahren auf Grundlage des gegebenen Matchings durch (auch wenn dieses nicht gesättigt ist). (2 Punkte) Lösungsvorschlag: G ist bipartit mit der Aufteilung: V1 = {1, 4, 6, 9, 11, 13} V2 = {2, 3, 5, 7, 8, 10, 12} und dem gegebenen Matching M = {(3, 4), (6, 7), (11, 12), (10, 13)} Schritt 1 V (M ) = {3, 4, 6, 7, 10, 11, 12, 13} V (M ) ∩ V1 = {4, 6, 11, 13} ⊂ V1 S := {1} I := ∅ V (T ) := {1} E(T ) := ∅ Sei w = 5 und e = (1, 5) Schritt 2 N (S) = {3, 5, 7} Schritt 3 b) M {(3, 4), (6, 7), (11, 12), (10, 13), (1, 5)} Schritt 1 V (M ) = {1, 3, 4, 5, 6, 7, 10, 11, 12, 13} V (M ) ∩ V1 = {1, 4, 6, 11, 13} ⊂ V1 S := {9} Schritt 2 N (S) = {2, 7, 10} I := ∅ V (T ) := {9} E(T ) := ∅ Sei w = 7 und e = (7, 9) Schritt 3 a) S = {6, 9} I = {7} Schritt 2 N (S) = {2, 3, 7, 8, 10, 12} V (T ) = {6, 7, 9} E(T ) = {(7, 9), (6, 7)} Sei w = 2 und e = (2, 9) Schritt 3 b) M {(3, 4), (6, 7), (11, 12), (10, 13), (1, 5), (2, 9)} Schritt 1 V (M ) = {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13} V (M ) ∩ V1 = {1, 4, 6, 9, 11, 13} = V1 M ist maximal. Aufgabe 41 a) Warum funktioniert der Matchingalgorithmus (die Ungarische Methode) nicht bei allgemeinen Graphen? b) Geben Sie bitte einen Graphen an, bei dem dieses Problem deutlich wird. c) Wie kann man für einen allgemeinen Graphen ein maximales Matching finden? Erläutern Sie Ihr Verfahren ausführlich. (6 Punkte) Lösungsvorschlag: a) Bipartite Graphen sind dadurch gekennzeichnet, dass sie keine Kreise ungerader Länge beinhalten. Bei Anwendung der Ungarischen Methode ist es also möglich, jeden Knoten eindeutig den Mengen S und I zuzuordnen. Dabei gibt es zu allen Knoten aus I einen Weg ungerader Länger von der Wurzel aus und zu allen Knoten aus S einen Weg gerader Länge. Man kann also jeder Kante und jedem Knoten einen Wert „gerade“ bzw. „ungerade“ zuordnen. Dies ist bei beliebigen Graphen nicht möglich! b) Als Beispiel sei der folgende Graph gegeben: v2 v5 v3 v4 v6 v1 Es ist sofort zu sehen, dass der Graph einen Kreis ungerader Länge enthält. Des weiteren sind die Kanten des gesättigten Matchings M = {(2, 5), (3, 4)} im Graphen rot markiert. Nachfolgend wird analog zur Ungarischen Methode ein Wurzelbaum mit Wurzel v1 konstruiert. Im ersten Schritt gilt S = {v1 }, N (S) = {v2 , v3 } und I = ∅. Es wird der Knoten v2 ∈ N (S) gewählt. Da dieser inzident zu einer Matchingkante ist, werden die Knoten v2 und v5 in den Wurzelbaum mit den entsprechenden Kanten aufgenommen. Es folgt N = {v1 , v5 }, N (S) = {v2 , v3 , v4 , v6 } und I = {v2 }. S I v2 S v5 v0 = v1 Als nächstes wird v3 ∈ N (S) gewählt. Auch dieser Knoten ist inzident zu einer Matchingkante. Es ergibt sich N = {v1 , v5 , v4 }, N (S) = {v2 , v3 , v4 , v5 , v6 } und I = {v2 , v3 }. S I v2 S v5 v3 v4 v0 = v1 Nun ist es Möglich v5 ∈ N (S) zu wählen. Dieser Knoten ist inzident zu der Matchingkante (2, 5). Es ergibt sich N = {v1 , v5 , v4 , v2 }, N (S) = {v1 , v2 , v3 , v4 , v5 , v6 } und I = {v2 , v3 , v5 }. S I/S v2 S/I v5 v3 v4 I S v0 = v1 Damit die Zuordnung der Knoten v2 und v5 zu N bzw. S nicht mehr eindeutig. c) Um ein maximales Matching in einem allgemeinen Graphen zu finden, betrachte man folgenden Algorithmus von Edmonds. Edmond’s Blossom-Algorithmus Gegeben sei ein Graph G = (V, E). Initialisierung: M beliebiges Matching von G; Schritt 1: Setze: V := V und E := E V (M ) := {v | v ist mit einer Kante von M inzident} Falls V (M ) ∩ V = V : STOP – M ist maximales Matching. (Sonst kann M möglicherweise vergrößert werden.) Wähle dann v0 ∈ V \ V (M ) und setze: S := {v0 } Schritt 2: Schritt 3: I := ∅ V (T ) := {v0 } E(T ) := ∅ Setze N (S) := {w | w ist adjazent zu einem Knoten aus S}. Falls I = N (S), setze V := V \ {v0 } und gehe zu Schritt 1. (Es gibt keinen M -zunehmenden Weg in T .) Falls I 6= N (S), wähle w ∈ N (S) \ I und eine Kante e = (u, w) mit u ∈ V (T ) und gehe zu Schritt 3. (i) Falls w mit einer Kante aus M inzident ist und w ∈ / V (T ), dann gibt es eine Kante l ∈ M mit l = (w, s) und s 6∈ V (T ). Dann setze S := S ∪ {s}, I := I ∪ {w}. Erweitere (den M alternierenden Wurzelbaum) T durch die Knoten w, s und durch die Kanten e und l, d. h. V (T ) := V (T ) ∪ {w, s} E(T ) := E(T ) ∪ {e, l} und gehe zu Schritt 2. (ii) Falls w nicht mit M inzident ist und w ∈ / V (T ), so ist der im Baum T eindeutig bestimmte Weg von v0 nach u zusammen mit dem Knoten w und der Kante e = (u, w) ein M -zunehmender Weg W in G. Setze dann M := (M \ W ) ∪ (W \ M ). Löse alle Blossoms in umgekehrter Reihenfolge, in der sie entstanden sind, wieder auf und erweitere M entsprechend. Gehe zu Schritt 1. (iii) Falls w ∈ V (T ), so ist ein Kreis ungerader Länge gefunden (Blossom B Knotenmenge V(B) und Kantenmenge E(B)). Schrumpfe B zu vB . Setze: E1 = {alle Kanten, die mit einem Knoten aus B inzident sind, aber nicht zu E(B) gehören} E2 = {(v, vB )|v ∈ V \V (B) und ∃z ∈ V (B) mit (v, z) ∈ E1 } E3 = {alle Kanten, die in T mit einem Knoten aus B inzident sind, aber nicht zu E(B) gehören} E4 = {(v, vB )|v ∈ V (T )\V (B) und ∃z ∈ V (B) mit (v, z) ∈ E(T )} Dann gilt: V := (V \V (B)) ∪ vB E := ((E\E(B))\E1 ) ∪ E2 V (T ) := (V (T )\V (B)) ∪ vB E(T ) := ((E(T )\E(B))\E3 ) ∪ E4 M := M \E(B) ∩ M E = E ohne Mehrfachkanten Gehe zu Schritt 2. Der Algorithmus von Edmonds beruht auf folgenden Überlegungen. Ein „Stem“ (Stengel) ist eine alternierende Kantenfolge gerader Länge und beginnend bei einem „Nicht-Matchingknoten“ v. (Bei der Bildung des M -alternierenden Wurzelbaumes entspricht v der Wurzel des Baumes.) Ein „Blossom“ (Blüte) ist ein Kreis ungerader Länge, welcher ein maximales Matching beinhaltet, wobei ein Knoten b zu keiner Matchingkante inzidiert. Eine „Flower“ (Blume) besteht aus einem Stengel und einer Blüte. Es gilt das folgende einfache aber wichtige Resultat: In einem Kreis ungerader Länge gibt es zu jedem ausgewählten Knoten b ein maximales Matching, so dass alle anderen Knoten mit einer Matchingkante inzidieren und b nicht! b b Diese Eigenschaft macht sich Edmonds zunutze und entwickelt einen Algorithmus, der – wie die Ungarische Methode – in einem M -alternierenden Wurzelbaum einen M -zunehmenden Weg sucht. v4 v5 v2 v3 v1 Wird dabei im Laufe der Iteration (die abläuft wie die Ungarische Methode) ein Kreis ungerader Länge entdeckt – etwa dadurch, dass eine Nichtmatchingkante an den Baum angehängt wird, die zu einer weiteren Matchingkante des Baumes benachbart ist –, so wird der gesamte Kreis durch einen neuen „Pseudoknoten“ b ersetzt. Dabei besitzt b alle Knoten als Nachbarn, die zuvor mit wenigstens einem der Knoten des Kreises benachbart waren. b Der neue Knoten b ist dann potentieller Anfangsknoten einer Nichtmatchingkante – würde also in der Ungarischen Methode in die Knotenmenge S fallen. Natürlich kann es zu mehreren Kreisen ungerader Länge kommen, so dass eventuell ein Pseudoknoten b mit anderen Knoten zu einem weiteren Pseudoknoten ˜b zusammengefasst wird. Dies ist durchaus möglich! (Man merkt sich in diesem Fall lediglich, welche Knoten zu einem Pseudoknoten b zusammengefasst wurden – ggf. kommen in dieser Knotenmenge bereits Pseudoknoten vor.) b Wird nun in dem „zusammengefassten“ Baum ein M -zunehmender Weg gefunden, so existiert zunächst einmal ein Matching in dem zugrundeliegenden „zusammengefassten“ Graphen, welches eine Kante mehr beinhaltet (vgl. Ungarische Methode). b Im Anschluss sind die Pseudoknoten sukzessive, beginnend mit dem zuletzt gebildeten wieder aufzulösen und in den Kreisen ungerader Länge die „entsprechenden“ maximalen Matchings zu bilden. Der Pseudoknoten war im „zusammengefassten“ Graphen zu lediglich einer Kante des Matchings inzident. Diese Kante inzidiert nach Auflösung des Pseudoknotens mit genau einem Knoten des Kreises ungerader Länge. Für diesen Knoten können zwei Fälle eintreten: Fall 1: Der Knoten ist nicht inzident zu einer Matchingkante. Das Matching, das vor Bildung des Pseudoknotens vorlag, ist weiterhin gültig. v4 v5 v2 v3 v1 Fall 2: Der Knoten inzidiert mit einer Matchingkante. Man finde ein maximales Matching, dass zu allen Knoten außer dem betrachteten Knoten inzident ist. Ein solches Matching existiert stets in einem Kreis ungerader Länge (vgl. obige Überlegungen). v4 v5 v2 v3 v1 Aufgabe 42 Bitte wenden Sie Ihren allgemeinen Matchingalgorithmus aus Aufgabe 41 auf folgenden Graphen an: v7 v6 v5 v3 v1 v4 v2 v8 (Bitte wenden Sie den allgemeinen Matchingalgorithmus so an, dass zu erkennen ist, an welcher Stelle die Ungarische Methode versagt.) (2 Punkte) Lösungsvorschlag: Man starte mit folgendem gesättigten Matching M = {(v1 , v2 ), (v4 , v8 ), (v6 , v7 )}. Die Matchingkanten sind in der nachfolgenden Abbildung rot markiert. v7 v6 v5 v3 v1 v4 v2 v8 Erzeuge einen Wurzelbaum mit v0 = v3 . Es gilt S = {v3 }, N (S) = {v1 , v2 } und I = ∅. Wähle v2 ∈ N (S). Der Knoten ist inzident zu einer Matchingkante. Damit folgt S = {v1 , v3 }, N (S) = {v1 , v2 , v3 , v5 , v7 } und I = {v2 }. S I v2 S v1 v0 = v3 Wähle v3 ∈ N (S). Man erhält eine Blüte. Erzeuge einen Pseudoknoten b1 und aktualisiere S = {b1 }, N (S) = {v4 , v5 , v7 , v8 } und I = ∅ S I S v1 v2 S b1 v0 = v3 Wähle v4 ∈ N (S). Der Knoten ist inzident zu einer Matchingkante. Dann gilt S = {b1 , v8 }, N (S) = {b1 , v4 , v5 , v7 , v8 } und I = {v4 }. I S v4 S v8 v 0 = b1 Wähle b1 ∈ N (S). Man erhält eine Blüte. Erzeuge einen Pseudoknoten b2 und aktualisiere S = {b2 }, N (S) = {v5 , v6 , v7 } und I = ∅ S I v4 v 0 = b1 S S v8 b2 Wähle v5 ∈ N (S). Der Knoten ist zu keiner Matchingkante inzident. Man erhält das maximale Matching M = {(v1 , v3 ), (v2 , v8 ), (v4 , v5 ), (v6 , v7 )} durch sukzessives Auflösen der Pseudoknoten. v5 S v5 v4 v8 v 0 = b2 v 0 = b1 v5 v4 v8 v 0 = b1 v5 v4 v8 v2 v1 v0 = v3 v5 v4 v8 v2 v1 v0 = v3 Aufgabe 43 Gegeben sei ein bipartiter Graph G = (V, E) mit V = A ∪ B. Zeigen Sie bitte folgende Behauptung: Gilt |N (S)| ≥ |S| − d für alle S ⊆ A und ein festes d ∈ N mit d ≤ |A|, so enthält G ein Matching der Mächtigkeit |A| − d. (1 Punkt) Lösungsvorschlag: Setze B = B∪{w1 , . . . , wd } und füge alle Kanten (wi , u) hinzu mit u ∈ A. Dadurch wurde die Anzahl der Nachbarn |N (S)| für jede Teilmenge S ⊆ A um exakt d erhöht, so dass die Voraussetzungen des Heiratssatzes erfüllt sind. Im erweiterten Graphen existiert also ein Matching der Mächtigkeit |A|. Im diesem können von zusätzlichen Knoten keiner bis hin zu allen gematcht sein, so dass aber in jedem Fall nach Entfernung der zusätzlichen Knoten und Kanten ein Matching von mindestens der Mächtigkeit |A|−d erhalten bleibt. (Sollte die Mächtigkeit des entstehenden Matchings echt größer sein als |A|−d, so entferne man die überflüssigen Matchingkanten.)