Prof. Dr. R. Laue                                                                            WS0001                                 Graphentheoretische Optimierung
                                Übungsblatt 9
                                Abgabe: 22.12 vor der Vorlesung

Aufgabe 18 Netzwerk - (6 Punkte)

Führen Sie den Ford Fulkerson Algorithmus anhand des folgenden Beispiels vor. Gesucht ist der maximale Fluss vom Knoten A zum Knoten G. Die Kantenmarkierung ist die Kapazität. Definieren Sie Datentypen zum Speichern der benötigten Variablen. Geben Sie die Belegung der Variablen nach den einzelnen Schritten an.

Aufgabe 19 (Beweis Ford Fulkerson) (4 Punkte)

Man zeige, dass das beim Beweis des Hilfssatzes zum Satz von Ford Fulkerson zu g > f definierte f^~ ein zulässiger Fluss auf G^~(f) ist.