Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

So, herzlich willkommen zur heutigen Vorlesung. Inhaltlich hat man uns letzte Woche mit dem Max-Flo Problem beschäftigt

und haben dafür auch schon einen ersten Algorithmus kennengelernt, die Grundversion von Ford-Fulkerson,

wo wir gesagt haben, also die Idee ist, also die entscheidende Idee war das Konzept von augmentierenden

Wegen, ja einfach entlang von gerichteten Wegen Fluss zu schicken, das reicht, da hat man ein kleines

Beispiel gesehen, deshalb das Konzept von augmentierenden Wegen, wo man sich entlang eines

Weges die Bögen anschaut, die in Vorwärtsrichtung schauen und noch Luft nach oben haben und in

Rückwärtsrichtung gucken, Luft nach unten haben und dann hat man gesehen, da haben wir eine

Charakterisierung gefunden, dass nämlich ein Fluss genau dann maximal ist, wenn es keine augmentierten

Wege mehr gibt. Ja und das war das zentrale Resultat und damit konnte man automatisch auch gleich

einen Algorithmus angeben, der ständig nach augmentierenden Wegen sucht, bis er keine mehr

findet, dann wissen wir, sind wir optimal. So da haben wir gestern, also letzte Woche die Grundversion

bewiesen, dass die korrekt ist und das einzige, wo wir jetzt noch so einen kleinen Makel, das heißt

klein oder größeren Makel dran haben, dass die Laufzeit exponentiell ist. Das noch mal zur Erinnerung,

m mal mu, wenn wir mu durch n mal maximale Kapazität abschätzen, dann steht da m mal n mal

maximale Kapazität ist exponentiell in der Eingabellänge. Deswegen brauchen wir da noch

was anderes und das ist das, was wir uns heute angucken, nämlich wenn wir entlang von kürzersten

augmentierenden Wegen, kürzersten bezüglich der Anzahl Bögen augmentieren, dann wird das Ding

automatisch polynomial. Das wird uns ein bisschen Zeit kosten, also sind ein paar, zwei, drei technische

Schwierigkeiten drin, die wir da beweisen müssen und dann, was man jetzt umgekehrt gesagt sozusagen

vielleicht sowieso automatisch macht, also am kürzesten, wenn ich nur die Anzahl Bögen sozusagen

zähle, keine Gewichte habe, dann reicht mir was für ein Algorithmus, brauche ich dann unbedingt

ein Dijkstra oder so. Wenn ich nur zähle, die Anzahl Kanten, dann reicht auch, Tiefensuche

braucht man, bei Tiefensuche kann es sein, wir verirren uns, je nachdem welchen Bogen man zuerst wählt,

kann auch lange Wege rauskommen, aber wenn wir Breitensuche machen, kriegen wir automatisch einen

kürzersten bezüglich Anzahl Bögen sozusagen und Breitensuche geht in linearer Zeit und typischerweise,

wenn ich einen Weg suche in einem Grafen, ist das der erste Algorithmus, den man versucht, wenn ich

nur einen Weg suche, das heißt, ohne dass man das vorher wusste, hat man automatisch immer schon die

polynomiale Variante implementiert, dass es tatsächlich so ist, das wollen wir uns heute

beweisen und dann fangen wir noch einen komplett alternativen Ansatz an, um maximale Flüsse zu

bestimmen und zwar schauen wir uns, also wenn wir gucken, wie wir es bislang gemacht haben, da haben

wir einfach gesagt, wir schauen, dass wir einen zulässigen Fluss kriegen, den kriegen wir relativ

einfach, nämlich x gleich Null ist zulässig und dann versuchen wir sozusagen, den so lange zu

bearbeiten, bis wir optimal sind und eine andere Idee ist zu sagen, wir sind immer optimal und

basteln an dem Fluss so lange herum, bis er zulässig wird, also ein Stück weit, wenn man so möchte,

ein komplett anderer Zugang, den werden wir in der Optimierung öfters finden, nachher auch bei der

linearen Programmierung werden wir sehen, dass es auch diesen Zugang gibt, Optimalität zu erhalten

und dann auf Zulässigkeit sozusagen zu iterieren und dann umgekehrt immer zulässig zu sein und auf

Optimalität zu gehen. Ein Stück weit zwei grundsätzlich verschiedene Ansätze, die

unterschiedlich gut funktionieren können und wir werden hier sehen, wenn man diesen zweiten

Ansatz wählen, kriegen wir sogar noch eine bessere Laufzeit hin, als mit dem Verfahren immer mit der

zulässigen Lösung zu starten. Wie das dann genau aussieht, das schauen wir uns heute dann an. Gut,

also das erste erstmal, wie kriegen wir Polynomialität hin? So und dazu der zentrale

Satz, das ist der Satz 8, 11, wird so in Schritt 3, also wo man augmentierenden Wegsuchen, ein kürzester,

also bezüglich Bogenanzahl augmentierender Weg bestimmt.

So sind nur oder höchstens n mal m Augmentierungen notwendig.

Okay und damit haben wir, also wenn wir das bewiesen haben, dann haben wir nämlich auch sofort eine

Polynomiale Laufzeit, also das heißt wir müssen höchstens n mal m augmentieren. Jetzt gucken wir uns

unter der Hauptschleife rein, was war das übelste Ding, was wir machen mussten. Bestimmen wir einen

augmentierten Weg, das haben wir gesagt, das machen wir mit dem Residualgraph. Suche da einfach einen