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

Herzlich willkommen. Heute fangen wir ein neues Kapitel an sozusagen für Grafen und

Algorithmen. Wir haben uns letzte Woche mit dem Max-Flow-Problem beschäftigt und es auch

abgeschlossen. Wir haben einen sozusagen den zentralen Satz da kennengelernt, dass der maximale

Fluss gleich der minimalen Schnitt ist und wir haben im Wesentlichen zwei unterschiedliche

Herangehensweisen, Algorithmen kennengelernt, um das Max-Flow-Problem zu lösen. Das eine

über augmentierende Wege, Algorithmen von zulässigen Fluss starten und den sukzessive

verbessern bis optimalität erreicht ist und eben Preflow-Push-Algorithmen, die mit einem

unzulässigen sogenannten Pseudofluss beginnen, der aber die Optimalitätsbedingungen erfüllt

und wir sukzessive zur Zulässigkeit uns bewegen. Und wir haben gesehen, dass sogar

die letztere Variante, die vielleicht nicht die intuitive ist, sozusagen insgesamt zu

einer Laufzeit führt, die nochmal besser ist als das, was man über die augmentierende

Wege-Algorithmen erreicht, nämlich n² mal m. Bevor wir jetzt da in das neue Thema einsteigen,

gibt es da zu letzter Woche noch Nachfragen, Unglarheiten, die offen geblieben sind.

Gut, wenn das nicht der Fall ist, dann schauen wir uns heute, je nachdem, wie man das sehen

möchte, eine gewisse Erweiterung an oder eine Verallgemeinerung des maximalen Flussproblems,

nämlich das eines Minimalkostenflusses oder Mincostflow im Englischen. Meistens verwendet

man das auch im Deutschen Mincostflow, weil Mincostflow einfach kürzer ist als Minimalkostenfluss

zu sprechen. Es geht eigentlich darum, dass wir jetzt, was wir beim maximalen Flussproblem

ja gemacht haben, haben wir gesagt, wir haben eine Quelle, wir haben eine Senke, wir versuchen

möglichst viel durch dieses Netzwerk zu pushen oder durchzudrücken, so viel halt die Kapazität

des Netzes hergibt. Was wir jetzt machen, sagen wir wollen eine ganz bestimmte Menge

durch dieses Netzwerk schieben und das auf kostengünstigste Art und Weise. Und damit,

wenn man so möchte, eine Verallgemeinerung, weil wir sozusagen, ja, gute Frage, ist es

tatsächlich eine Verallgemeinerung, das werden wir gleich noch sehen, kann man also mit dem

Mincostflow-Problem tatsächlich, könnte man auch das Maxflow-Problem damit lösen? Wenn

wir sehen, dass das gleich geht und wir werden sehen, dass wir auch Konzepte, die wir vorher

verwendet haben, da durchaus wiederverwenden können und wiedersehen, die wir bislang sowohl

bei Kürzesten Wege als auch bei Maxflow-Geschichten uns angeguckt haben. Aber mit der Fragestellung

an sich, erstmal mit einer vorgegebenen Größe durch zu pushen, stellen sich natürlich zwei

Fragen. Einmal A, geht es denn tatsächlich? Also kann ich denn wirklich auch die vorgegebene

Menge durchpushen? Es könnte ja sein, jemand gibt mir was vor, was größer ist als der minimale

Schnitt, dann geht es nicht. Also die Algorithmen müssen das natürlich auch feststellen können

und wenn es dann geht, also wenn es dann zulässige Lösungen gibt, wie sieht denn dann unter den

gegebenen Gewichtsfunktionen eine minimale aus? Genau dieses Problem wollen wir uns angucken.

Wir werden dann sehen, dass es unterschiedliche Optimalitätskriterien gibt. Also wir gehen

wieder vor wie in den anderen Kapiteln auch, dass wir uns erstmal überlegen, was sind

denn Optimalitätskriterien, um nachzuweisen, dass eine Lösung optimal ist und es wird uns

auch hier wieder gelingen, solche Optimalitätsbedingungen anzugeben. Ich hatte ja schon angedeutet,

dann später in der diskreten Optimierung wird uns das in aller Regel nicht mehr gelingen,

hier noch in den Anführungszeichen einfachen Fällen schon und so wird es auch bei MinCostFlow-Problem

sein und dann darauf basierend zwei Algorithmen kennenlernen, die wieder unterschiedlicher

Herangehensweise sind, aber die eben basierend auf diesen zwei unterschiedlichen Optimalitätskriterien

sozusagen darauf aufsetzend an jeweils ein Vorgehen entwickeln, wo wir dann auch zeigen,

dass sie funktionieren. Also so ist grob der Plan. Das wird uns heute und mit Sicherheit

auch die nächste Stunde beschäftigen. Also schauen wir uns das an. Überschrift heißt

das Minimalkosten-Fluss-Problem, Kosten-Fluss-Problem oder im Englischen MinCostFlow-Problem.

MinCostFlow oder manchmal auch einfach MCF abgekürzt. So, was ist die Ausgangssituation?

Wir haben wieder ein D-Graf, ein D gleich V, E, wieder ein D-Graf. Wir haben wieder Kapazitäten,

V von A, die größer als Null sind für alle A in A. Das sind unsere Kapazitäten. Also