präsentiert von Open Learnware, die Plattform für Lernmaterialien an der TU Darmstadt. So, hallo allerseits, wir sind wieder zusammen hier, wir sind zusammengekommen, um uns wieder dem Thema der Flussalgorithmen zu widmen. Was wir beim letzten Mal begonnen haben,

Sie erinnern sich, diese Folie haben wir beim letzten Mal gesehen, das ist die allgemeine Problemstellung. Wir wollen in einen statischen Fluss, wir wollen nur statische Flüsse betrachten, dynamische Flüsse, die sich über die Zeit verändern, Methoden dafür, die basieren auf Methoden für statische Flüsse,

wir werden es aber hier in der Vorlesung bei statischen Flüssen belassen. Das heißt also, dass der Fluss, der über eine Kante im gerichteten Grafen geht, nicht von der Zeit abhängig ist, nicht in der Zeit variiert, sondern einfach zeitunabhängig da ist, als eine Variable, die nur mit der Kante von I nach J indiziert ist.

Das sind die Flusserhaltungsbedingungen hier, dass für jeden einzelnen Knoten die Summe der rausgehenden Flüsse minus der Summe der reingehenden Flüsse, das kann man sich immer gut visuell vorstellen, wenn man für so einen Knoten

die Kanten, die reingehen, vielleicht auf diese Seite malt und die Kanten, die rausgehen, auf diese Seite malt, was natürlich im Allgemeinen wird man das nicht so platzieren oder nicht platzieren können, dass das alles so in dieser Reihenfolge ist, sondern nur, das denken wir uns mal einen Knoten herausgegriffen, und die Summe der Flusswerte, die Summe der Kantenwerte X auf den reingehenden Kanten

betrachten wir und die Summe auf den rausgehenden Kanten jeweils für sich, und wir ziehen diese Summe von dieser Summe ab, und was rauskommen soll, ist ein spezieller Wert, nämlich für diesen Knoten ein Balancewert Bi. Wir haben darüber gesprochen, Knoten, bei denen dieser Balancewert positiv ist,

das sind die, bei denen etwas in das System sozusagen Quellen, bei denen in das ganze System irgendetwas hineinfließt, und Knoten, bei denen dieser B-Wert, dieser Balancewert negativ ist, sind Senken,

bei denen irgendwie Fluss aus dem Netzwerk abgegriffen wird, und Knoten, bei denen dieser Balancewert Null ist, das sind Transferknoten, die dienen nur dazu, damit Fluss da durchfließt, gebündelt wird und dann wieder verteilt wird. So kann man sich das vorstellen. Wir haben allgemein natürlich obere Schranken, Kapazitäten,

der Fluss darf eine gewisse Kapazität nicht überschreiten, die durch die Kante technisch vorgegeben ist. Wir betrachten aber auch immer auch den allgemeineren Fall dabei, dass es auch untere Schranken gibt, dass also der Fluss ein Mindestmaß an Wert auf jeder Kante,

kantenspezifisch, haben soll. Das ist in den meisten Anwendungen nicht relevant, in manchen schon, deshalb nehmen wir das mit. Aber oft genug betrachten wir den Fall, dass die unteren Schranken alle Null sind, wie es in den meisten Anwendungen ja der Fall ist. So, und dass diese beiden Sätze von Bedingungen, diese beiden Mengen von Bedingungen,

definieren, was ein zulässiger Fluss ist, und unter allen zulässigen Flüssen wollen wir jetzt einen finden, so wie wir unter allen Faden einen Kürzesten finden wollen, wollen wir hier unter allen zulässigen Flüssen einen finden,

der die Kosten minimiert. Was sind die Kosten? Für jede Kante haben wir so etwas wie einen Einheitskostenwert. Wenn wir eine Einheit Fluss über die Kante von I nach J schicken, dann kostet uns diese Einheit Fluss C I J an Wert, an Euro oder in Stromverbrauch oder was immer jetzt die relevante Kostendimension ist.

Und wenn ich also X I J Einheiten insgesamt über die Kante I J schicke, dann heißt das, was es mich kostet, diese X I J Einheiten über diese Kante I J zu schicken, ist gerade C I J mal X I J. C I J die Kosten pro Einheit mal X I J Einheiten ergibt Gesamtkosten für die Kante

und das aufsummiert über alle Kanten ergibt uns die Gesamtkosten des Flusses im ganzen Netzwerk. So, das haben wir beim letzten Mal schon betrachtet. Wir sind auch ein Stück weiter gegangen. Diese Punkte brauchen wir nicht noch mal zu betrachten.

Wir haben das noch nicht begonnen. Den Restgrafen oder im Englischen vielleicht ein bisschen vornehmen Residualgrafen. Also man redet auch im Deutschen vom Residualgrafen, manchmal auch vom Restgrafen. Also irgendwie klingt Residualgraf besser, nicht? Belassen wir es dabei. So, was ist das?

Wir haben jetzt einen Grafen mit einem Fluss drin und wir betrachten uns eine einzelne Kante von irgendeinem Knoten, wie sind die hier genannt? Noch gar nicht. Noch haben wir gar keinen Namen.

Von I nach J. So, das ist der Knoten I und das ist der Knoten J. Wir haben da drauf drei Werte. Wir haben die untere Schranke als feste konstante Wert. Wir haben die obere Schranke als festen konstanten Wert,

die Input sind für das Problem. Und wir haben jetzt einen Fluss, den wir hier bisher immer mit XIJ abgekürzt haben. Kürzen wir jetzt auch ab. Ja, diese drei Werte haben wir jetzt da drauf. Wir haben als Input LJ und UIJ. Und wir haben jetzt irgendwo her, fällt vom Himmel her, irgendein Flusswert XIJ.

Das Ganze ist jetzt ein, das ist natürlich nicht nur für diese Kante, sondern für alle Kanten. So, was der Residualgraf jetzt daraus macht oder was wieder definiert ist, ist, die Idee vom Residualgrafen ist jetzt zu modellieren, wie viel Flusswert,

wie viel kann ich das XIJ noch nach oben treiben? Um wie viele Einheiten kann ich noch mehr hin schicken? Oder wie viele Einheiten kann ich wieder zurücknehmen? Das ist natürlich klar, wie viel das sind. Ich kann UIJ minus XIJ-Einheiten mehr drauf packen. Und ich kann XIJ minus LJ-Einheiten weniger drauf packen.

Und im Residualgraf haben Sie dieselben Knoten. Sie haben also auch wieder ein I und ein J. Diese Kante natürlich nur stellvertretend für alle anderen Kanten im Grafen, für dieselbe Operation gilt. Und Sie ersetzen diese eine gerichtete Kante durch zwei gerichtete Kanten mit neuen Kapazitäten.

Untere Kapazität 0. Und wichtig ist die obere Kapazität UIJ minus XIJ. Und hier drauf setzen Sie die Kapazität XIJ minus LIJ.

Schauen wir mal nach, das sollte jetzt genau das sein, was hier auch irgendwo gleich steht. Die Kosten sind dieselben. Hier sehen Sie hier UIJ minus XIJ und XIJ minus LIJ.

Das sind die beiden residualen Kapazitäten. Restkapazitäten, die übrig sind. Und die Idee dabei ist, wir sind mittendrin in einem Algorithmus. Das ist der Grund, warum wir das betrachten. Sie erinnern sich, wir haben immer mal wieder,

wenn wir Algorithmen betrachtet haben, mittendrin im Algorithmus. Was ist da los? Mittendrin im Algorithmus haben wir solche Flusswerte XIJ. Die Werte im Resuallgrafen, wenn wir jetzt auf zum Resuallgrafen übergehen, wenn wir gar nicht mehr im ursprünglichen Grafen arbeiten, sondern im Resuallgrafen arbeiten,

machen wir uns das Leben insofern einfacher. Wir können hier Flusseinheiten UIJ minus XIJ noch dazu packen, ohne die Kapazitäten zu verletzen. Oder wir können weniger Flusseinheiten, als wir jetzt Flusseinheiten reduzieren,

was wir dadurch ausdrücken können, dass wir eben bis zu XIJ minus LIJ Flusseinheiten den Weg zurücknehmen lassen. Die Idee ist, die Flusseinheiten XIJ hier zu reduzieren, zu einem neuen Fluss zu kommen, von diesem Fluss XIJ,

den abzudaten zu einem neuen, vielleicht besseren Fluss. Nicht indem wir hier damit arbeiten, Flusswert hoch und runter zu setzen, sondern hier Flusswert zu erhöhen, sodass bis zu dieser oberen Schranke, bis zu dieser Resuallkapazität,

können wir das machen. Oder hier Fluss zu erhöhen, bis zu dieser Schranke. Was bedeutet, dass wir hier im ursprünglichen Graphen den Flusswert reduzieren, dass wir sozusagen Fluss zurückschicken auf diese Art und Weise. Das ist ein Modell, das sieht vielleicht am Anfang erstmal ein bisschen komisch aus,

aber wenn man es nicht erstmal dran gewöhnt hat, ist das sehr, sehr praktisch. So, jetzt müssen wir uns noch über die Kosten dabei unterhalten. Am Ende geht es immer um die Kosten. Auf der Vorwärtskante haben Sie die Kosten. Wir haben hier noch, habe ich nicht dazugeschrieben, den Kostenwert natürlich.

Hier haben Sie den Kostenwert Cij und hier haben Sie den Kostenwert minus Cij. Das bedeutet, wenn Sie hier einen Einheitfluss rüberschicken, kostet Sie das Cij. Das passt, weil zurück ins ursprüngliche Modell bedeutet das auch hier Erhöhung um 1.

Wenn Sie hier eine Fluss Einheit hingegen auf diesem Rückwärtskante rüberschicken, kostet Sie das minus Cij, das heißt Sie gewinnen Cij. Passt, weil das Rüberschicken, das Zurückschicken von J nach I von Fluss-Einheiten entspricht gerade dem Zurücknehmen von Fluss und damit dem Zurücknehmen von Kosten hier auf der Seite.

Also es ist eine 1 zu 1 Korrespondenz zwischen den zwei Modellen. Wenn Sie den Fluss auf diese Art und Weise hier geändert haben, das hier übertragen, müssen Sie natürlich den Visualgraf entsprechend updaten, weil die X-Werte sich dadurch geändert haben. Sie dürfen natürlich nicht damit den alten X-Werten weiterrechnen, das passt nicht.

So, jetzt möchte ich dazu noch einen Punkt ansprechen, nämlich wir kriegen hier offensichtlich parallele Kanten rein, hatten aber immer gesagt, wir wollen keine parallelen Kanten haben, bzw. das stand in den Folien und ich habe gesagt,

mir ist es wurscht, ob parallele Kanten drin sind oder nicht. Warum ist mir das wurscht? Gehen wir mal zurück zu einem anderen Problem, was wir letztens betrachtet haben, kürzeste Wege.

Was ist hier mit parallelen Kanten? Naja, wenn wir an kürzesten Wegen interessiert sind, gucken wir uns an, wie lang ist die Kante, wie lang ist die Kante, und je länger von beiden schmeißen wir raus. Können wir uns leisten. Und wenn beide gleich lang sind, schmeißen wir eine von den beiden Kanten raus,

es ist egal welche. Auf diese Art und Weise können wir ohne beschränkende Allgemeinheit davon ausgehen, dass wir keine parallelen Kanten haben. Hier kriegen wir natürlich, wenn Sie einen Visualgraf bauen, wenn wir das Bild von eben hernehmen, wenn Sie schon eine Hin- und eine Rückwärtskante hatten im ursprünglichen Graphen zwischen E und J,

dann kriegen Sie jetzt natürlich zwei parallele Kanten jeweils raus mit dieser Konstruktion.

Was ist hier zu sagen? Naja, wir gucken uns beide Kapazitäten an und addieren die beiden. Wenn Sie zwei parallele Rohre haben, die jeweils eine gewisse Kapazität für Wasser haben,

dann können Sie die beiden einfach gedanklich abstrakt betrachten als ein Rohr, dessen virtuelle Kapazität die Summe der realen Kapazitäten ist. Also können wir auch hier mit parallelen Kanten umgehen.

Ah, das ist dieser Punkt, dieser Visualgraf kann parallele Kanten haben, aber wir ignorieren das. Wir können es ignorieren, indem wir den Schritt machen, die beiden Kanten zu einer zu vereinigen,

Kapazitäten zu addieren oder einfach zu tun, als ob uns das Problem gar nichts anginge hier. Wenn Sie es implementieren, müssen Sie natürlich damit irgendwie klarkommen. Das ist klar, aber solange wir es nicht implementieren, solange wir nur darüber nachdenken, solange können wir es so tun, als ob das mit den parallelen Kanten uns alles nichts angeht. Okay, Kanten, die risuell Kapazitäten gleich Null haben, also wo beispielsweise der Fluss am oberen Anschlag ist,

dann ist das hier Null, können wir vergessen, wo wir keinen Fluss drüber schicken können, zusätzlich Fluss drüber schicken können, was sollen wir das noch betrachten? Und genauso hier, wenn X am unteren Anschlag ist, XJ gleich LJ, dann ist hier risuelle Kapazität Null,

können wir auch diese Kante vergessen, was sollen wir uns damit abplagen? Das ist das, was diese Note hier besagt. So, hier ist ein Beispiel, die Zahlen sind leider nicht so besonders groß,

aber ich hoffe Sie können es trotzdem lesen oder wenn Sie es vielleicht ausgedruckt oder auf dem Rechner vor Augen haben, können Sie reinzoomen. Das ist ein Netzwerk, hier sind nur obere Kapazitäten aufgetragen,

untere Kapazitäten sind alle Null, die unteren Schranken sind alle Null, deshalb haben wir an jeder einzelnen Kante nur eine Zahl, nur eine schwarze Zahl, und Sie sehen hier alle Knoten, das sehen Sie nicht, sondern das sage ich Ihnen,

die Knoten haben alle Balance Null, das heißt also, es sind reine Transmittennotes, da geht nur Fluss durch, hier haben Sie eine Balance von Plus 5, hier haben Sie eine Balance von Minus 5, das heißt also, in diesem ganzen Netzwerk macht ein zulässiger Fluss das eine, dass er fünf Einheiten von diesem Knoten, ganz links zu diesem Knoten, ganz rechts durchschickt,

in irgendeiner Art und Weise. Sie erinnern sich, wir haben beim letzten Mal gesehen, die Balancewerte müssen, damit ein zulässiger Fluss überhaupt möglich ist, müssen die Balancewerte aller Knoten sich zu Null aufaddieren, was in diesem Fall wirklich der Fall ist, auch, die sind alle Null,

Plus 5, Plus Minus 5 ergibt Null, passt. So und Sie sehen, das ist ein relativ einfaches Beispiel, wir haben fünf Einheiten auf einem einzigen Fahrt durchgeschickt, hätte natürlich auch ein bisschen komplizierter sein können, das durchschicken, aber das reicht hoffentlich, um das Beispiel zu illustrieren.

So, jetzt schauen Sie mal zum Beispiel auf diese Kante hier, 10 ist die oberen Kapazität, Null ist, ohne dass es hingeschrieben steht, die untere Kapazität, fünf Einheiten werden rübergeschickt, das heißt die risuelle Kapazität in die eine, wie in die andere Richtung ist fünf, oder hier wird es vielleicht noch ein bisschen deutlicher, weil es unterschiedliche Kapazitäten dabei herauskommen, diese Kante hier mit Gewicht 12, oder diese Kante mit Gewicht 12 hat, auch da werden fünf Einheiten Anfluss rübergeschickt,

das heißt die risuelle Kapazität, was noch mehr sein kann, was man noch mehr Anfluss rüber schicken kann, über diese Kante sind sieben Einheiten, das ist die risuelle Kapazität im Risualgrafen,

und um wie viel kann man einen Fluss der Größe fünf mit fünf Fluss-Einheiten reduzieren, natürlich um maximal fünf, wenn die Unterschranke Null ist, also hat diese Rückwärtskante hier die risuelle Kapazität fünf, so viel Fluss können wir, um so viel können wir den Fluss hier reduzieren,

beziehungsweise im Risualgrafen, um so viel können wir den Fluss der Einheiten zurückschicken, und Sie sehen vielleicht hier noch als interessantes Beispiel, hier auf diesen beiden Kanten geht jeweils, ist der Fluss jeweils am Anschlag, das heißt also, es ist keine, diese Kante selber als Vorwärtskante,

ist im Risualgrafen nicht drin, weil sie wäre mit Risualkapazität Null drin, macht keinen Sinn, damit kann man nichts anfangen, sie ist aber als Rückwärtskante drin, weil wir eben diese fünf Einheiten, die darüber gehen, jederzeit, um die können wir es reduzieren, so viel können wir zurückschicken,

deshalb, wenn Sie sich jetzt irgendeine Kante ansehen, auf der gar kein Fluss drauf ist, dann ändert sich auf der nichts, denn Sie können weiterhin, nehmen wir diese Kante hier, oder diese hier mit Kapazität 10, Sie können 10 Einheiten, so viel wie diese Kapazität ist,

können Sie 10 Einheiten rüberschicken, also haben Sie diese Kante als Vorwärtskante im Risualgrafen, da der Fluss da drauf Null ist, können Sie nichts zurückschicken, untere Schranke ist ja auch Null, also gibt es keine Rückwärtskante. So, das ist das Konzept des Risualgrafen, ich denke,

also von der Motivationslage ist es vielleicht eher momentan noch dürftig, wozu man das Ganze braucht, aber ich glaube vom Verständnis her, was das eigentlich ist und wie das funktioniert und wie die Korrespondenz ist, sollte hoffentlich schon ein erstes Lichtlein da sein. So, wir betrachten, der erste Satz sagt das,

Flüsse sind Attribute der Kanten, Zahlenattribute auf den Kanten, die die Flusserhaltungsbedingungen und die Kapazitätsbedingungen einhalten müssen. Wir werden es aber jetzt sehen,

ich mache das mal gleich voll und ganz, dass wir zwei komplementäre Sichtweisen dazu haben, einerseits diese Sichtweise, wie wir sie bisher haben, es gibt einen Flusswert pro Kante, eine dazu komplementäre Sichtweise ist, wir haben eine gewisse Menge von Pfaden und Zykel im Grafen

und jeder dieser Pfade und jeder dieser Zykel hat seinen eigenen Flusswert, X von P für den Pfad P und X von C für den Zykel C und diese beiden Sichtweisen sind identisch, sind eins zu eins, wir werden jetzt in den nächsten Minuten sehen,

dass man das ineinander überführen kann, beziehungsweise die eine Richtung steht schon hier, nämlich, wir gehen nachher gleich nochmal hier rauf zurück, ich glaube das Ganze wird deutlicher,

wenn wir die andere Richtung uns mal betrachten, gehen wir so dahin.

Ignorieren Sie erstmal den ersten Satz, der bezieht sich auf das, was wir eben übersprungen haben, nehmen Sie den zweiten Satz, der mit Conversely beginnt, jeder nicht negative Upflow, also das, was wir bisher betrachtet haben, gehen wir ein paar Bilder zurück, da, das ist ein relativ primitiver,

nicht negativer Kantenfluss, sehr primitiv, als es eigentlich nur ein Pfad mit 5 Fluss-Einheiten ist, aber die Definition, wo ist die Definition, hier, die Definition erlaubt natürlich beliebig komplizierte

Konstruktionen, Flusswerte x auf allen Kanten, solange nur diese Bedingungen erfüllt sind, so, davon reden wir, als Arcflow, wir kommen da noch hin, jeder solche, was wir so kennengelernt haben,

als Fluss x, kann dargestellt werden, durch eine Menge von Pfaden und Zyklen, die,

sodass jeder Pfad und jeder Zyklus einen gewissen Flusswert trägt, also was ein Pfad und ein Zyklus ist, brauchen wir jetzt nicht nochmal zu sagen, aber was das heißt, dass er einen Flusswert trägt,

vielleicht ein einfaches Beispiel dazu, so, sie haben hier, sehr einfaches Beispiel,

Balancewert plus 3, Balancewert minus 3, hier haben sie 0, hier haben sie 0, und jetzt wäre natürlich farbige Kreide nicht schlecht, ja, 3 Farben für 3 Pfade, passt,

so, vielleicht machen wir es ein bisschen komplizierter, nicht Wert 3, sondern Wert 6,

und sie haben einen Pfad, dem ordnen sie eine Flusseinheit zu, sie haben einen zweiten Pfad,

so, dem ordnen sie zwei Flusseinheiten zu, ja, auf allen Kanten, die dieser Pfad enthält, trägt er zwei Flusseinheiten bei, und sie haben noch einen dritten Pfad,

der 3 Flusseinheiten, dem wir 3 Flusseinheiten zuordnen, so, und was wir sagen können ist, der Gesamtfluss über jede Kante ist hier 1, ein Pfad, der rote oder was das sein soll,

dieser rötliche, dem eine Flusseinheit zugeordnet wird, hier, auf der Kante, ist nur der gelbe Pfad, zwei Einheiten, also diese Kante hat hier Flusswert 2, diese Kante hat Flusswert 3, weil da zwei Pfade drauf sind, einer mit Wert 1 und einer mit Wert 2,

die hier hat auch Flusswert 3, und die hier hat Flusswert 5, und wenn sie das mal anschauen, dann stellen sie fest, dass an jedem Knoten die Flusserhaltungsbedingung erfüllt ist, ja, gucken sie sich die beiden mittleren Knoten an, eine rote Einheit, zwei gelbe Einheiten gehen rein,

eine rote Einheit, zwei gelbe Einheiten gehen raus, kann gar nicht anders sein, als dass es erfüllt ist, genauso hier, zwei gelbe, drei grüne Einheiten gehen rein, zwei gelbe, drei grüne Einheiten geben raus, und hier, so habe ich das Beispiel gerade gezeichnet, sechs Einheiten gehen raus, eine, zwei und drei,

und genau die kommen hier auch wieder an, ja, das gibt Ihnen zunächst mal Eindruck, wovon hier überhaupt die Rede ist, dass wir auf der einen Seite können wir natürlich einen Fluss so komponieren, wie ich das jetzt eben gesagt habe, das ist das, was wir, was ich jetzt erst einmal übersprungen hatte,

da, da, ja, Sie haben, Sie haben erst einmal hier, wir haben eine Menge von Pfaden, jeden dieser Pfade haben Sie einen Flusswert zugeordnet,

das waren unsere Werte eins, zwei, drei auf dem roten, gelben und grünen Pfad, Sie haben hier die Inzidenzwert, also wenn eine Kante J auf dem Pfad P ist, dann steht hier eine 1, Kronecker-Symbol, und wenn Sie, wenn die Kante J nicht in P ist, dann steht hier eine 0,

das heißt also, was hier steht, vergessen Sie mal diesen rechten Summanden hier, erst einmal diesen linken Summanden hier, was hier steht, ist das, was ich versucht habe hier zeichnerisch darzustellen, der rote, der gelbe gehen über diese Kante, aber nicht der grüne, das heißt also,

dieses Delta, das Kronecker-Symbol ist 1 für die beiden, das heißt die 1 und die 2 werden für diese Kante gezählt, und 0 für diese Kante, die 3 wird nicht gezählt, so kommt das hier zustande mit diesen Pfaden,

die Flusswerte, die 1, 2, 3, Kronecker-Symbol 0 oder 1, sie nachdem, ob der Pfad über die Kante geht oder ob er nicht darüber geht. So, jetzt haben wir hier aber noch die Zykel, warum das denn? Wir haben doch jetzt eben gesehen, das lässt sich doch wunderbar so hier darstellen, ja, das ist aber natürlich nur eine einfache, schöne,

suggestive Situation, die ich hier gezeichnet habe, wir müssen uns natürlich bewusst sein, dass die Situation auch ein bisschen komplizierter sein kann, malen wir die Situation ein klein wenig,

komplizierter, so, jetzt haben wir hier, wir können uns das Leben einfach machen, wir haben auf jeder einzelnen Kante ein Flusswert von 1, was bedeutet das in Pfaden?

Ne, halt, das stimmt nicht, das passt nicht, hier muss natürlich ein Flusswert von 2 sein, so einfach geht das jetzt auch nicht, hier muss ein Flusswert von 3 sein, hier muss jetzt ein Flusswert von 2 sein, jetzt müsste es aufgehen, oder? Jetzt passt das, hier gehen 3 rein, 3 raus, 3 rein, 3 raus, 2 rein, 2 raus, 2 raus, 2 rein

und jetzt haben wir hier einen Pfad von links nach rechts mit dem Wert 1,

wir haben noch einen Pfad von links nach rechts, der kann hier nicht mehr weitergehen, das ist schon, der Fluss ist schon erledigt, ebenfalls mit dem Wert 1, und was ist jetzt mit dem Rest? Hier ist Rest, hier ist Rest, hier, das ist, so sieht das aus,

wenn man enthusiastisch seine Vorlesung hält, ne? So, hier ist Rest, hier ist Rest und Sie sehen, das Grüne, was sich da schließt, ist ein Zykel, ebenfalls mit zugeordneten Wert 1, ja, also wir haben ja, Sie sehen,

wenn wir nur die Bedingung hernehmen, wie Flüsse definiert sind für Seidungsbedingungen, dann sind solche Situationen natürlich absolut korrekt, ja, und Sie sehen, das kann man nicht in Pfade allein zerlegen, sondern da bleibt ein Zykel übrig,

kann man sich drehen, wenn Sie wie Sie wollen, ist auch durchaus möglicherweise erzwungen, durch die unteren Schranken, wenn die positiv sind, machen wir das selbe Bild wieder,

wenn hier zum Beispiel die L-Werte alle positiv sind, 1 zum Beispiel, dann werden, was immer ein zulässiger Fluss ist, er wird einen Zykel enthalten müssen, geht gar nicht anders,

weil dann muss Flusswert hier über diese Kante gehen und das konstituiert auf alle Fälle einen Zykel, Sie können sich hinstellen, wie Sie wollen, es wird nicht ohne Zykel abgehen. So, deshalb haben wir hier diesen zweiten Sommanten, der genauso strukturiert ist, wir haben eine Menge von Pfaden und eine Menge von Zykeln, die zusammen für jede Kante den Flusswert ergeben,

also wenn wir solche Menge von Pfaden und Zykeln haben, wie ich das etwa hier dargestellt habe, in diesem Beispiel, dann konstituiert das einen Artflow, einen Fluss, wie wir ihn ursprünglich definiert haben,

so wie wir das eben gesagt haben, wir zählen einfach alle Flusswerte zusammen, die grüne 1 und die gelbe 2 hier ergibt Flusswert 3 und so weiter, aber das Spannende ist jetzt das Umgekehrte. Bevor wir dahin kommen, hier ist nochmal ein Beispiel dazu, wir haben jetzt ein Beispiel an der Tafel gesehen,

wir brauchen dieses Beispiel jetzt nicht nochmal durchziehen, das muss ich später gut, da muss ich später gut die Tastatur reinigen, bei weißer Kreide sieht man die Kreidespur nicht so, aber bei D-Kreide, das ist doch hoffentlich nicht aggressiv, ich hoffe mal sehr, das ist nicht aggressiv.

So, kommen wir noch dazu, das Spannende ist jetzt die Umgekehrte-Aussage, abconversely, wir haben jetzt gesehen, wenn wir so eine Menge von Pfaden und Zykeln haben,

dann ergibt sich daraus automatisch ein Fluss auf jeder Kante, das ist das Umgekehrte, wenn wir einen Arcflow haben, einen Fluss auf jeder Kante, einen Flusswert, der die Flusserhaltungsbedingungen erfüllt, dann können wir den dekomponieren und darum geht es hier in diesem kurzen Abschnitt,

wir können diesen Fluss dekomponieren in so einer Kombination aus einer Menge von Pfaden und einer Menge von Zykeln und wir können noch mehr dazu sagen, nämlich wir können die Anzahl der Pfaden und Zykeln beschränken, die Behauptung ist erst einmal, es ist nur eine Behauptung bisher,

die Behauptung ist, dass es höchstens M plus N Pfaden und Zykeln gibt, M die Anzahl der Kanten, N die Anzahl der Knoten, wie immer, also dass wir jeden beliebigen Fluss aus höchstens M plus N Pfaden und Zykeln kombinieren können

und von diesen M plus N Pfaden und Zykeln sind es höchstens M Zyklen, die dabei mitspielen. Das sieht ein bisschen kompliziert aus, diese Formulierung unter B, aber diese Formulierung existiert schon seit den 60er Jahren so,

bis jetzt hat noch keiner eine Idee gefunden, das zu verkürzen, zu vereinfachen, das geht wahrscheinlich auch nicht. Machen Sie sich klar, was hier genau steht,

die Anzahl der Pfade plus Zykel zusammen kann irgendwo zwischen 0 und M plus N sein, aber egal wo sie zwischen 0 und M plus N ist, die Zahl der Zykel alleine muss zwischen 0 und M sein, also es kann durchaus sein, dass wir M plus N Pfade haben, dann haben wir 0 Zyklen,

zwangsläufig, weil wir M plus N Pfade und Zykel maximal haben. Wenn wir hingegen weniger als N Nordpolpfade haben,

dann wissen wir, es können nicht mehr M plus N Pfade und Zykel geben, weil die Zykel, die hinzukommen können, sind höchstens M. Ja, wenn Sie zum Beispiel N halbe Pfade nur noch haben, dann kann die Gesamtsumme der Pfade und Zykel höchstens noch M plus N halbe sein. Ja, das ist die zahlmäßige Logik dahinter.

So, ich will versuchen Ihnen das jetzt nicht Schritt für Schritt anhand der einzelnen Sätze zu erklären, sondern zeichnerisch zu erklären, was da vor sich geht, also anschaulich.

Sie fangen mit irgendeiner Kante an, von I nach J, mit einem Flusswert größer 0.

Ja, Kanten mit Flusswert 0 sind praktisch gar nicht im Spiel, interessiert Sie nicht. So, jetzt gibt es an diesem Knoten hier zwei Möglichkeiten.

Entweder Sie haben hier eine Senke oder nicht. Was haben Sie erwartet, wenn ich so anfange? So, wenn es keine Senke ist, dann wissen Sie, es muss auch mindestens eine weitere Kante rausgehen mit größer 0.

Flusserhaltungsbedingung. Bei einer Senke kann es sein, muss es nicht sein. Genauso Argument hier. Entweder es ist eine Quelle. Jetzt raten Sie, was ich sage. Oder nicht. Wenn es keine Quelle ist, dann muss es hier auch wieder eine Kante reingehen wegen der Flusserhaltungsbedingung,

die größer 0 Flusswert hat. Und so können Sie sie fortsetzen, bis Sie hier zu einer Senke kommen.

Oder bis Sie hier zu einer Quelle kommen. Solange gilt die Argumentation auf jeden Fall. Wenn Sie das jetzt gefunden haben, hier ist überall größer 0, dann gucken Sie sich an, welcher von denen hat den kleinsten XIJ-Wert.

Das muss nicht die Kante sein, mit der Sie angefangen haben. Das kann irgendeine andere sein. Zum Beispiel die hier. Das ist die Kante von K nach L. Und die hat den kleinsten Flusswert aktuell. Was Sie jetzt machen ist, für jede einzelne Kante,

reduzieren Sie den aktuellen Flusswert um diesen minimalen Flusswert. Und das ist Ihr Pfad.

Ihr nächster Pfad P. Ihr erster Pfad P, den Sie gefunden haben. Sie reduzieren den ganzen Fluss, wie er gerade ist, um diesen Wert. Und der Flusswert von P, den setzen Sie auf dieses XKL. Sie haben Ihren ersten Pfad mit seinem zugeordneten Wert gefunden.

Und das machen Sie so weiter. Nachdem Sie diesen ersten Pfad gefunden haben, von irgendeiner Quelle zu irgendeiner Senke, reduzieren Sie den Flusswert um das Minimum aller aktuellen Flusswerte.

Und machen man mit dem Restfluss, der noch im Gesamtnetzwerk übrig bleibt. Wir reden ja nicht nur von diesem Pfad. Das ist ja nur ein kleiner Pfad in einem großen Netzwerk. Machen dasselbe nochmal.

Und finden so einen Pfad nach dem anderen. Sodass deren Summe dann für jede Kante, den seinen Flusswert ergibt. Warum terminiert das irgendwann? Warum ist das irgendwann zu Ende?

Beachten Sie, dass ich hier mindestens eine Kante den Flusswert auf Null reduziert habe. Das heißt, in jedem einzelnen Iteration, wo ich so einen Pfad konstruiere, bekommt eine Kante am Ende Flusswert Null. Das kann mit jeder Kante nur einmal passieren.

Das heißt, insgesamt kann es nur Anzahl Kanten, oft überhaupt diese Operation passieren. So, ist das Bild soweit erstmal klar? Oder ist es Ihnen noch nicht so klar? Diejenigen, die noch wach sind.

Wem ist es noch nicht so richtig klar? Aha, dann wenn Ihnen das nicht klar ist, dann müssten Sie aber alle aufschreien. Es gibt zwei Lügen in diesem Bild. Also bisher gesagt nicht im Bild, sondern in dem, was ich dazu gesagt habe.

Zwei sagen wir mal etwas vornehmer. Wir müssen an zwei Stellen noch das Modell etwas erweitern. Ich weiß nicht, wer von Ihnen jetzt zuerst? Okay, das ist der erste Punkt. Irgendwo müssen ja mal die Zyklen jetzt ins Spiel kommen.

Wenn Sie, so wie wir jetzt eben gesagt haben,

mit irgendeiner Kante J beginnen und Sie gehen voran, dann kann es sein, dass Sie nie auf eine Senke stoßen, sondern dass es immer weiter und weiter und weiter und weiter geht, je nachdem, wie Sie Gott zufällig gegangen sind.

Aber da der Graf endlich ist, wenn es immer weiter und weiter und weiter geht, dann muss das irgendwo zyklen. Das kann so aussehen, dass wir wieder bei I ankommen. Es kann aber auch anders aussehen,

mal ich das ein bisschen weiter nach links, von I nach J. So, es kann so aussehen, dass wir hier innen drin zu einem Zyklus kommen.

Also die Ursprungskante muss nicht in dem Zyklus enthalten sein. Aber dann haben wir wieder einen Zyklus gefunden mit derselben Eigenschaften. Wir können auf allen Kanten um denselben Wert reduzieren.

Das ist unser Zyklus C jetzt. Hier ist das Minimum vielleicht wieder bei der Kante von K nach L. Und wir setzen den Wert des Zyklus auf XKL und reduzieren den Fluss entlang dieses Zyklus um das Ganze und machen wieder weiter. So kommen die Zyklen dabei ins Spiel.

Auch hier wieder das Argument, das kann nicht beliebig häufig sein, weil wir jedes Mal mindestens auf einer Kante den Fluss auf Null runter drücken, nämlich da, wo dieses Minimum angenommen wird. So, das war die erste Lüge, die wir jetzt aufgelöst haben.

Also Vornehmer, die erste Modellerweiterung, die wir machen mussten. Was ist jetzt das zweite? Die Balancewerte müssen auch noch beachtet werden. Es kann sein, dass hier, oder sagen wir so der Balancewert,

es kann sein, dass hier das, was aus der Quelle mehr rauskommt als reingeht, oder auch hier bei der Senke, was mehr reinkommt als rausgeht, dass es kleiner ist als der minimale Wert eines Flusses hier,

dann sollten wir natürlich nur so viel reduzieren, dass diese Quelle oder diese Senke, dass da die Balance Null wird. Mehr sollten wir das nicht reduzieren. Brauchen wir auch nicht. So, und wenn wir das jetzt noch mal zusammensammeln,

wie oft kann es uns passieren mit diesem Bild, wie oft kann es uns passieren, dass wir einen Zykkel finden und entlang dieses Zykkels den Fluss reduzieren. Maximal so häufig, wie es Kanten gibt, denn jedes Mal, wenn wir so einen Zykkel finden,

dann reduzieren wir auf jeden Fall eine solche Kante auf Null, den Flusswert. Und damit ist schon das hier gesehen. Out of these, at most, M cycles have non-zero flow. Wir können höchstens M mal, Anzahl der Kanten mal, häufig auf einem Zykkel diese Operation durchführen. So, und wenn wir das jetzt hier alles zusammenrechnen,

jedes Mal, jedes Mal, wenn wir diese Operation durchführen, egal ob es zu einem Zykkel oder zu einem Pfad führt, entweder geht der Flusswert einer Kante auf Null oder einer der beiden Endknoten, dessen Balance geht auf Null.

Wie häufig kann eine Kante auf Null gehen? Also, jede Kante geht nur einmal auf Null. Wie häufig kann das passieren? So oft, wie es Kanten gibt, also M mal, M wie Mata. Wie häufig kann es passieren, dass die Balance bei einem Knoten auf Null geht? Na, dass es bei jedem Knoten nur einmal passieren kann.

Wir sind da ja vorsichtig. So wie wir ein Knoten in Balance ist, betreffen wir den eben nicht mehr als Quellen oder Senke. Das kann höchstens oft passieren, wie es Knoten gibt. N wie Nordpol mal. Und damit haben wir es. Höchstens M plus N mal können wir eine dieser beiden Operationen ausführen. Und wir haben gesehen, höchstens M mal kann diese Operation ausführen.

Was hinter dem Beweis steckt, ist natürlich eine relativ einfache, vollständige Induktion. Eine vollständige Induktion über die Anzahl der Kanten, die positiven Flusswert tragen, plus die Anzahl der Knoten, die Quellen oder Senken sind. Eine von diesen beiden Zahlen reduzieren wir in jedem Schritt.

Mindestens eine von diesen beiden Zahlen. Und damit ist die Induktionsvoraussetzung anwendbar. Wir können davon ausgehen, dass der Rest, nachdem wir diesen Pfad oder diesen Zykel da rausgenommen haben, dass der Rest sich ebenfalls so in Pfade und Zykel dekomponieren lässt. Das ist die mathematische Beweisstruktur dahinter.

Ist doch nicht so schwer, oder? Ich finde es anschaulich. Aber gut, ich habe schon seit 20 Jahren damit zu tun. Irgendwann sollte ich es mal anschaulich finden. Okay, also das ist das, was hier so wortreich formuliert worden ist.

Im Grunde nichts anderes als das, was ich da gesagt habe. So, Flussdekomposition kann man in dieser Zeit tun. Warum? Naja, wir gehen hier davon aus, dass der Graf zusammenhängt.

Das heißt, M wie Marta, die Anzahl der Kanten ist mindestens so groß wie N wie Nordpol. Asymptotisch, die Anzahl der Knoten. So, wir können höchstens, also M, was hier letztendlich steht, ist etwas komplizierter,

aber dafür präziser gefasst, seit 23 Jahren.

O von N mal M plus N steht hier eigentlich. Aber wenn der Graf zusammenhängt ist, dann ist, wissen Sie, M mindestens N minus 1. Dann ist mindestens ein spannender Baum drin.

Sodass also das dann gleich ist, O von N mal M, das, was hier oben steht. So, warum ist das so? Wir können M plus N mal diesen Schritt tun, einen Pfad oder einen Zykl identifizieren. Wie viel Aufwand kostet uns das pro Operation?

Naja, was kostet es uns, so einen Pfad oder so einen Zykl zu finden? Na, wir gehen von irgendwo durch. Und wenn wir das erste Mal wieder einen Knoten gefunden haben, den wir schon mal berührt haben,

können wir aufhören, wir haben einen Zykl gefunden. Das heißt also, in dieser Operation, egal ob es am Ende auf einen Zykl oder auf so einen Pfad hinausläuft, fassen wir jeden einzelnen Knoten nur einmal an. Wir fangen irgendwo beliebig an. Der erste Knoten in der Liste oder die erste Kante in irgendeiner Liste von Kanten mit Flusswert größer 0.

Und von der gehen wir immer weiter. Das kann höchstens nach N-Schritten, asymptotisch, haben wir die Situation geklärt. Sind wir auf beiden Seiten meiner Quelle auf der Senke oder haben wir einen Zykl geschlossen? Daher kommt der erste Faktor, das N, da hinein.

Das hier ist auch eine unmittelbare Folgerung. Sie erinnern sich, was eine Strömung ist, eine Circulation. Das ist der Fall, wenn der Balancewert überall 0 ist. Das heißt also, jeder Knoten ist ein Durchgangsnoten.

Für jeden Knoten gilt, reingehend der Fluss ist gleich rausgehend im Fluss, es gibt keine Quellen und keine Senken. Das heißt also, die Situation, wie wir sie hier hatten, dass wir ausgehend von irgendeiner Kante rückwärts zu einer Quelle und vorwärts zu einer Senke kommen, kann gar nicht auftreten.

Das heißt also, es kann nur die andere Situation auftreten, dass wir in einen Zykl reinlaufen. Und deshalb ist eine Strömung nicht repräsentiert durch Pfade und Zykl, sondern nur durch Zykl. Da habe ich jetzt noch mal in der Vorbereitung nachgedacht.

Keine Sorge, ich bin der Meinung, in diesem Fall das Corolla stimmt. Ich bin mir aber nicht sicher, ob man das wirklich als Corolla aus dem bisherigen Gesagten folgern kann. Sondern ich will Ihnen sagen, wie ich es folgern würde und Ihnen sagen, warum, an welcher Stelle meine Folgerung jetzt eben über das, was wir jetzt gesagt haben, hinausgeht.

Vielleicht finden Sie auch wieder, vielleicht können Sie auch wieder meinen Job machen. Meinen Gehalt nicht beziehen, aber meinen Job machen und mir zeigen, dass es doch tatsächlich eine Folgerung aus dem bisher Gesagten ist, dass ich da irgendeine Möglichkeit übersehen habe. So, was steht hier erst einmal?

Die Kostenfunktion, glaube ich, brauchen gar nicht, die brauchen gar nicht integral zu sein. Nee, ich bin mir sicher, die brauchen nicht integral zu sein. Aber wenn die Kapazitäten, die oben und unten schranken, ganzzahlig sind, dann gibt es sogar

einen minimalen Kostenfluss, der ebenfalls ganzzahlig ist, dessen x-Werte auf jeder Kante ganzzahlig ist. Das ist insofern ganz praktisch, wenn Sie wissen, dass in Ihrer Anwendung die Impuls alle ganzzahlig sind. Ja, Sie haben ganzzahlige Kapazitäten in diskreten Einheiten irgendwie gemessen.

Dann brauchen Sie keinen Double zu reservieren für die Flusswerte, sondern Sie können int reservieren für die Flusswerte und wissen, das wird klappen. So, warum gilt das?

Ich glaube, was hier eingestehen sollte ist, falls die Kapazitäten und die Balancewerte, dann geht es nämlich auf. Die Balancewerte müssen ganzzahlig sein. Die Kosten müssen nicht ganzzahlig sein.

So, das zeige ich Ihnen jetzt, warum ich dieser Meinung bin. So, Sie haben jetzt eine Kante, deren Flusswert, also von i nach j, deren Flusswert xij ist nicht ganzzahlig.

Irgendwas Gebrochenes, hat irgendwelche Nachkommastellen.

So, die oberen und unteren Schranken und die Balancewerte sind aber alle ganzzahlig. So, wenn hier bj ganzzahlig ist, dann heißt das doch, dass diese Nicht-Ganzzahligkeit, dass

das nicht die einzige Kante ist am Knoten j, der ihren Flusswert nicht ganzzahlig ist. Ja, das geht nicht. Sämtliche anderen Kanten, die reingehen und sämtliche anderen Kanten, die rausgehen, wenn die alle ganzzahlige Flusswerte hätten und der eine nicht, und der Balancewert ist ganzzahlig, das geht nicht, das passt nicht.

Es muss also mindestens eine weitere Kante geben, die rausgeht oder die reingeht, die einen nicht ganzzahligen Wert hat. Zum Beispiel eine rausgehende, also hier sollte ein Nicht sein, sorry, warum meldet sich keiner?

Ja, ist doch egal, jetzt wir haben was. Es könnte zum Beispiel eine weitere rausgehende Kante sein, die nicht ganzzahlig ist. Machen wir mal diesen einfachen Fall durch. Das ist analog zu dem, was wir jetzt bisher betrachtet haben.

Auch hier wieder selber Argument und so weiter, bis wir vielleicht zu einer Senke kommen. Und hier dasselbe Argument, bis wir zu einer Quelle kommen.

Hier ist Nicht aus Z, alles nicht ganzzahlig. Ja, wir können argumentieren. Es gibt immer eine Kante an diesem Knoten, deren Flusswert ebenfalls nicht ganzzahlig ist. So, was wir jetzt in diesem einfachen Mal machen können, ist mal ein bisschen an den Werten zu rütteln.

Mal Plusepsilon überall raufsetzen, auf jeder dieser Kante, oder mal Minusepsilon rauf. Nee, in dem einfachen Fall, Entschuldigung, da bin ich jetzt schon einen Schritt weiter.

In dem einfachen Fall ist es sogar noch einfacher, als ich das jetzt vorhatte allgemein zu betrachten. In dem einfachen Fall setzen wir überall ein genügend kleines Epsilon runter, auf jeder dieser Kanten,

und haben die Kosten reduziert für den Gesamtfluss. Weil wir haben den jetzt, warten Sie mal, halt, halt, halt, so.

Das kann ja auch nicht sein, das Argument geht ja noch weiter. Entschuldigung, wir kommen gar nicht bis zu einer Senke und bis zu einer Quelle, sondern wir kommen immer, es schließt sich garantiert ein Zykel.

Entschuldigung, da habe ich jetzt zu kurz geschlossen. Wenn Sie hier eine Kante haben, nicht aus Z, dann können Sie immer weiter und immer weiter gehen,

bis sich ein Zykel schließt, der diese Kante enthält, oder wie wir es eben gesehen hatten, der vielleicht eher so aussieht, dass Sie hier beginnen und dort irgendwo schließt sich der Zykel. Aber betrachten wir mal die Situation. Hier ist überall ein Nichtelement aus Z und so weiter, ja?

So, die Kostenwerte können größer oder kleiner Null sein. Deshalb machen wir Folgendes. Wir erhöhen überall mal den Flusswert um Epsilon.

Das ist ein alternativer Fluss, den wir rauskriegen. So, das und das ist ein alternatives Epsilon. Und einmal vermindern wir überall den Flusswert um Epsilon, ausreichend klein.

So, wenn jetzt die Summe der Kostenwerte größer Null ist, dann ist dieser zweite Fluss, wo wir um Epsilon verringert haben, besser als der Ausgangsluss.

Es kann also Ausgangsluss kein minimaler Kostenfluss gewesen sein, Widerspruch. Wenn hingegen die Summe der Kostenwerte auf diesen Kanten hier insgesamt kleiner Null ist,

dann kriegen wir einen besseren Fluss raus, indem wir hier überall Plus-Epsilon raufsetzen. Den gesamten Fluss auf diesem Zykel um Epsilon erhöhen. Es kann also der Ausgangsluss wieder kein minimaler Kostenfluss gewesen sein, Widerspruch. Wenn hingegen die Summe der Kostenwerte, dritter Fall,

wenn hingegen die Summe der Kostenwerte Null ist auf diesem Zykel, die Kostenwerte der einzelnen Kanten, dann können wir mit Plus-Epsilon oder Minus-Epsilon nichts ändern am Gesamtkostenwert des Flusses,

egal um welches Epsilon wir erhöhen oder um welches Epsilon wir vermindern. Dadurch, dass dieser Zykel sozusagen kostenneutral ist, ändert sich nichts daran. In dem Fall können wir aber das Epsilon so groß setzen,

Das sind ja alles Werte, es sind endlich viele Werte, die nicht ganz zahlig sind und bei endlich vielen Werten, die nicht ganz zahlig sind, können wir das epsilon so groß setzen, gerade so groß setzen, dass der erste dieser Werte ganz zahlig wird. Und damit ist die Anzahl, selbe Argumentation wie eben, die Anzahl der Kanten, deren Flusswerte nicht ganz zahlig ist,

ist um eins vermindert worden. Und das ersetzen wir dann fort. Ist ein bisschen starker Tobak vielleicht, aber dafür nehmen wir das Ganze ja auf, dass sie sich das Ganze nochmal nachträglich,

wie ich mir sagen habe lassen, in eine anderthalbfache Geschwindigkeit bin ich erträglich, dass sie sich das nachträglich nochmal dann versuchen durch den Kopf gehen zu lassen. Auf die Art und Weise, wenn wir setzen das epsilon so groß, gerade so groß, dass die Kante, deren Flusswert am nächsten zur Ganzzahligkeit ist,

gerade ganz zahlig wird. Und die ist dann ganz zahlig, die taucht dann in weiteren Operationen dieser Art in den nächsten Schritten nicht mehr auf.

So, warum habe ich jetzt gesagt, dieses Korrelar, bin ich mir nicht sicher, ob es wirklich ein Korrelar daraus ist. Warum? Weil ich die ganze Zeit hier mit einer vereinfachten Situation gearbeitet habe. Es kann ja auch Folgendes sein. Sie fangen an mit einer Kante, deren Flusswert nicht ganz zahlig ist,

stellen fest vielleicht eine rausgehende Kante hier ist auch nicht ganz zahlig, aber stellen fest plötzlich alle rausgehenden Kanten haben ganz zahlige Werte.

Wie das? Die Balance ist ganz zahlig, das kann dann nur sein, dass eine der reingehenden Kanten nicht ganz zahligen Wert hat.

Jetzt geht es rückwärts, vielleicht noch mal einen Schritt rückwärts, stellen fest, alle reingehenden Kanten in diesem Knoten haben ganz zahlige Werte. Selbe Situation nochmal, dann muss eine andere rausgehende Kante nicht ganz zahligen Wert haben und so weiter und so fort.

Hier haben wir wieder die Situation. Sie sehen also, wir haben es nicht mehr mit einem

Zykel im eigentlichen Sinne zu tun, sondern mit einem Zykel, der Vorwärts- und Rückwärtskanten enthalten kann. Was machen wir hier? Die selbe Operation wie eben, nur plus minus Epsilon, plus minus Epsilon, hier minus plus Epsilon.

Hier wieder plus minus Epsilon, ist das jetzt richtig? Ja. Und hier minus plus Epsilon, also genau umgedreht.

Wenn wir auf diesen Kanten den Fluss um Epsilon erhöhen, vermindern wir hier um Epsilon und dann erhöhen wir ihn wieder hier und vermindern ihn hier. Wenn wir das so machen, dann bleibt die Flusserhaltungsbedingung bestehen, denn wenn Sie sich die vier verschiedenen Fälle mal angucken, was da passieren kann,

Sie haben den ersten Fall zwei Vorwärtskanten, wo Sie jeweils um Epsilon erhöhen. Alle anderen Kanten, die diesen Knoten berühren, bleiben gleich. Wenn vorher die Flusserhaltungsbedingung gegolten hat, gilt sie hinterher auch. Die Summe der

rausgehenden erhöht sich um Epsilon, die Summe der rausgehenden erhöht sich um Epsilon, bleibt die Balance an diesem Knoten bestehen. Das selbe, wenn Sie rückwärts gehen, hier um Epsilon vermindern, hier um Epsilon vermindern, bleibt das gleiche.

Wenn Sie jetzt diese Situation haben, um Epsilon erhöhen und übergehend zu einer Rückwärtskante um Epsilon vermindern, dann ändert sich an der Summe der rausgehenden Flüsse gar nichts, weil die gar nicht hier berührt sind durch diese Operation und bei der Summe der reingehenden Flüsse ändert sich auch nichts,

weil die Summe der reingehenden Flüsse wird einmal um Epsilon erhöht und einmal um Epsilon vermindert, bleibt gleich. Und genau dasselbe in der letzten Situation. Hier haben wir ein Minusepsilon, hier haben wir ein Plusepsilon. Die Summe der reingehenden Kantenflüsse ändert sich nicht,

weil sie gar nicht berührt werden. Es wird keine einzige reingehende Kante berührt bei diesem Knoten hier und die Summe der rausgehenden Flüsse ändert sich auch nicht, weil die Summe der rausgehenden Flüsse hier um Epsilon erhöht wird und hier um Epsilon vermindert wird. Die Flusserhaltungsbedingung bleibt bei allen diesen Operationen, egal wie genau die Konstellation

ist, an jedem dieser Knoten enthalten und damit entlang des Zykles auch enthalten. Bleibt sie erhalten. So und jetzt selber Argumentation. Jetzt zählen wir die Summe der Kosten ein bisschen anders, nämlich für die Vorwärtskanten auf diesem Zykel zählen wir die Kosten positiv und für die Rückwärtskanten zählen wir sie negativ.

So, jetzt können wir den Fluss, einmal die obere Leiste, hier plus plus plus minus minus plus plus minus minus.

Fluss erhöhen hier auf den Vorwärtskanten, Fluss vermindern auf den Rückwärtskanten, das ist die Zyklerichtung, Fluss vermindern auf den Rückwärtskanten.

Wenn die Gesamtkostenwerte so gerechnet, auf Vorwärtskanten positiv gerechnet, auf Rückwärtskanten negiert, wenn diese Summe negativ ist, hat sich dadurch, dass wir das Ganze um einem Epsilon erhöhen, der Kostenwert verbessert, verringert, Widerspruch, dann war das, womit wir gestartet sind, kein minimaler Kostenfluss.

Genau so umgekehrt, jetzt nehmen wir das untere Vorzeichen, auf den Vorwärtskanten vermindern wir den Fluss, auf den Rückwärtskanten erhöhen wir den Fluss,

wenn die Summe der Kostenwerte aller Kanten auf diesem Zykel so gerechnet, Vorwärtskanten positiv gerechnet, Rückwärtskanten negativ gerechnet, wenn die, was kommt jetzt, wenn die, was hatten wir eben, wenn die negativ war, wenn sie positiv ist, dann ergibt das so einen besseren Fluss,

in dieser zweiten Version wieder ein Widerspruch, völlig spiegelsymmetrisch zum ersten Fall. Der dritte Fall ist wieder, dass dieser Fluss, dass dieser Zykel kostenneutral ist, ja also ich kann hier die Summe der Kostenwerte Vorwärtskanten,

die Kostenwerte positiv gerechnet, Rückwärtskanten, die Kostenwerte negativ gerechnet und alles zusammen addiert, ergibt Null, dann kann ich um Epsilon den Fluss in die eine Richtung, wie die in die andere Richtung verändern, es ändert sich nichts an dem Kostenwert des Gesamtkostenflusses, dann kann ich wieder, wie eben, den Flusswert um so ein Epsilon verändern,

dass gerade so eben eine, irgendeine dieser Kanten, dass deren Flusswert ganzzahlig wird. Dann ist diese Kante aus dem Spiel raus und ich kann mit dem Restfluss, der übrig geblieben ist, weitermachen,

kann einen Zykel nach dem anderen einsetzen, solange bis alle ganzzahlig sind und habe immer kostenneutral geändert, wenn ich nicht in Widerspruch laufe, ist hier diese Änderung kostenneutral, das heißt, ich habe am Ende einen minimalen Kostenfluss, der nicht ganzzahlige Kantenflüsse enthält,

überführt in einen minimalen Kostenfluss, der nur ganzzahlige Kantenflüsse enthält, weil ich in jedem einzelnen dieser Schritte einen Zykel identifizieren, Fluss darauf verändern, in jedem dieser Schritte habe ich eine Kante mit

nicht ganz zahlen Kantenfluss zu einer Kante mit ganz zahlen Kantenfluss gemacht und gucke sie in den weiteren Iterationen nicht mehr an, weil ich immer nur mir Kanten angucke, deren Kantenflüsse nicht ganz zahlig sind. So, und wegen dieser Vorwärts- und Rückwärtsgeschichte, sagen wir mal so, ist es gewagt, finde ich, von einem Korrelar zu dem bisherigen zu sprechen.

Sie sehen, wie lange das jetzt gedauert hat, das zu argumentieren. Und wie weit ich da über diese Flugdecomposition hinausgegangen bin. Die Frage war, wie wählen Sie das Epsilon genau? Ich wiederhole die Fragen immer, damit das auch auf dem Band ist.

Sie wählen das Epsilon gerade so. Machen wir es mal ganz konkret. Nehmen wir doch mal ein ganz konkretes Beispiel. Vielleicht wird es dann irgendwie klarer. Machen wir mal ein ganz kurzes Beispiel nur.

So, und die Flusswerte hier drauf sind zum Beispiel 0,9, 0,2, 0,8, 0,3.

So, wenn das die Richtung des Zügels ist, also die beiden horizontalen sind die Vorwärtskanten und die beiden verticalen sind zwei Rückwärtskanten. Und dann wäre Plus 0,1 die richtige Wahl, dass Sie den Fluss hier entlang erhöhen.

Dann wird nämlich diese Kante ganz zahlig, wenn Sie hier auf den beiden Vorwärtskanten, also Plus 0,1, Plus 0,1, Minus 0,1 und hier auch Minus 0,1.

Dann wird diese Kante hier oben ganz zahlig und sonst bleibt alles so in seinem Bereich. Oder Sie sagen Minus 0,2, das heißt also Sie ziehen hier 0,2 ab, Sie ziehen hier

0,2 ab, Sie ziehen hier 0,2 ab und hier 0,2, dann wird diese Kante ganz zahlig.

Also Sie nehmen, wenn Sie sich dafür entscheiden zu addieren, dann gucken Sie sich, welche dieser Werte ist nach oben sozusagen, die hat die geringste Aufrundung nötig, um ganz zahlig zu kommen.

Und wenn Sie Fluss reduzieren, dann gucken Sie sich an, welche Kante hat die geringste Abrundung nötig, um ganz zahlig zu werden. Gute Frage. Die Frage war, für das Protokoll, was passiert, wenn Sie den Fluss nicht reduzieren dürfen, weil die oberen Nutten und Schannen das nicht zulassen.

Dafür steht diese Vorbedingung, the capacities are integral. Wenn die Kapazitäten, die lj und die uj integral sind, ganz zahlig sind und der Flusswert darauf ist nicht ganz zahlig, ist er weder am oberen noch am unteren Anschlag.

Ja, also hier, dass ich die Existenz eines epsilon größer 0 angenommen habe, was ich Ihnen untergeschoben habe, bis jetzt endlich mal jemand gefragt hat, das resultiert aus dieser Vorbedingung, dass die Kapazitäten ganz zahlig sind.

Also wie gesagt, die Kostenfunktionen müssen nicht ganz zahlig sein. Die Balancewerte müssen auch ganz zahlig sein, sonst lässt sich das natürlich nicht realisieren. Wenn die Balancewerte nicht ganz zahlig sind, dann können Sie mit dem ganz zahligen Fluss nicht alle Knoten in Balance bringen. Das geht nicht.

So, gut, warum ist das jetzt hier an dieser Stelle?

Haben wir den St-Fluss schon eingeführt? Gehen wir nochmal zurück, dass wir jetzt nichts überspringen an Notationen. Haben wir den vorher schon mal eingeführt? Hier fangen wir an, hier führen wir einen Fluss ein.

St-Fluss sollte nicht vor Fluss eingeführt worden sein. Hier nicht, hier nicht, hier nicht, ne.

Ein St-Fluss wurde früher mal eingeführt, aber warum wurde jetzt noch mal ein Fluss eingeführt? Das verstehe ich nicht. Ist egal, vergessen Sie das, wir kommen jetzt sowieso zum Thema hin. Maximale Flüsse. Maximale Flüsse. So, jetzt reicht es. Hier. Maximale Flüsse kennen Sie vielleicht aus der GD2?

Das ist ein Spezialfall davon. Die Situation ist die, ich suche mal nach einem Bild. War da nicht ein Bild? Natürlich nicht. Okay, kein Bild.

Maximale Flüsse. Was ist das? Sie sind von mir gewohnt, dass ich Grafen so als große Kreise zeichne. Davon werde ich jetzt abweichen beim Thema maximale Flüsse.

Von jetzt an sind Grafen solche spitz zu laufenden Pflaumen. So, S und T. Sie können es auch als was anderes interpretieren.

Ich bitte nur um stubenreine Interpretation. So, muss natürlich nicht so aussehen. Sie können sich vorstellen, dass es in Wirklichkeit so aussieht. Sie haben irgendwie einen Grafen platziert und irgendwo ist das S und irgendwo ist das T. Aber es ist natürlich bequem, das so zu zeichnen, dass S und T an den beiden Rändern des Bildes liegen.

Und was Sie jetzt wollen, ist Fluss von hier nach hier durch das Netzwerk durchzuschicken. Alle Knoten hier drin haben Balancewert Null.

Sind also reine Transferknoten. Hier wollen Sie maximal viel Fluss durchschicken. Raus aus dieser Quelle rausschicken, der dann hier entsprechend mit demselben Wert ankommt. Ja, wir werden noch sehen, dass das tatsächlich so ist, dass das, was Sie hier rausschicken, auch hier ankommen wird.

Zwangsläufig. So, also mir fallen jetzt eine Menge nicht stubenreiner Interpretationen ein, aber das lassen wir mal lieber.

So, also die Situation ist erst einmal klar, hoffe ich. Der Balancewert ist Null für jeden Knoten, der nicht S und nicht T ist. Der Summe raus minus Summe rein, das heißt der Nettoflusswert, der bei S rausgeht, soll möglichst groß werden.

Und dasselbe soll bei S bei T reingehen. Wir werden sehen, dass das automatisch immer so ist. Was bei S rausgeht, geht bei T rein und umgekehrt. Und diesen Flusswert, der bei S rausgeht und bei T reingeht, wollen wir maximieren. Und wir wollen jetzt untere Schranken Null haben, der Einfachheit halber, und Oberschranken ue hat irgendwelche Werte.

So, jetzt wird hier behauptet, observe, also eine einfache Beobachtung, dass maximale Flüsse ein Spezialfall von Minimum-Kostflüsse sind. Das ist auch tatsächlich nur eine relativ einfache Observation. Dazu zeichne ich das Ganze vielleicht noch mal ein klein bisschen exzentrischer.

Warum ist dieses maximale Flussproblem, dass Sie vielleicht aus GDE2 kennengelernt haben? Haben Sie es in GDE2 kennengelernt?

Wer von Ihnen hat es kennengelernt? Ok, so ungefähr die Hälfte. Macht nichts, wenn Sie es nicht kennengelernt haben. So, ich mache das Ganze ein bisschen exzentrischer. Das ist jetzt der Graph mit S hier und T hier. Hier soll der Fluss durchgeschickt werden.

Warum ist das ein Minimal-Kostenfluss-Problem? Weil Sie können es auf einfache Art und Weise reduzieren darauf. Sie fuegen hier eine Kante ein von T nach S zurück und sagen, diese Kante hat Kostenwert minus eins.

Alle anderen Kanten hier drin haben Kostenwert gleich Null. Und die Balancewerte von S und von T sind auch gleich Null.

Von denen hier drin sowieso. So, das bedeutet, das was Sie hier durchschicken, von S nach T, beides haben Balancewert Null, geht jetzt alles über diese Kante wieder zurück.

Wir haben eine Strömung geschlossen. Und je mehr über diese rote Kante fließt, weil der Kostenwert negativ ist, je mehr über diese rote Kante fließt, umso besser ist der Kostenwert.

Wer sagt denn, dass Kosten immer negativ sein müssen? Wir jedenfalls hier nicht. Deshalb lässt sich das Problem reduzieren auf ein Minimal-Kostenfluss-Problem. Das heißt, jeder Algorithmus für Minimal-Kostenfluss, für die Problemstellung, für die allgemeine

Problemstellung, die wir bisher betrachtet haben, kann auch gleichzeitig das Max-Low-Problem lösen. Was insofern mit Kanonen auf Spatzen schießen heißt, weil es effizientere Algorithmen speziell für Max-Low gibt. Aber falls Sie einen Minimal-Kostenfluss-Algorithmus zur Hand haben und Sie sind zufolum da was anderes zu implementieren oder eben will die Zeit, dann hauen Sie einfach mit dem Minimal-Kostenfluss-Algorithmus drauf und fertig.

In dem Sie die Kante einfügen und dann eben den Minimal-Kostenfluss-Algorithmus anwenden. Ok, hier ist noch eine Annahme. Was besagt diese Annahme?

Wir hatten gegen Ende des letzten Males gesagt, manchmal ist es zweckmäßig auch Kanten unendliche Kapazität zu geben. Ja, um auszudrücken, dass auf diesen Kanten keine Kapazitätsbeschränkung ist, dass da so viel rüberfließen kann, wie man halt will.

Aber wenn wir jetzt eine Fahrt haben von S irgendwie durch den Grafen hindurch nach T und da ist überall die obere Kapazität unendlich, es ist ganz natürlich witzlos.

Ja, dann ist unendlich der Flusswert, der optimale Flusswert. Also diese Instanz ist unbeschränkt, unbounded, unbeschränkt.

Gut, wir können das natürlich vorher schnell feststellen, ob es so eine Fahrt gibt, indem wir von S aus Kanten betrachten. Wir gucken von S aus, zu welchen anderen Knoten kommen wir, wenn wir nur Kanten hernehmen, die die unbeschränkte Kapazität haben. Und wenn T zu den Knoten gehört, die wir damit erreicht haben, dann gibt es so eine Fahrt, und wenn T nicht dazu gehört, dann gibt es keine Fahrt.

Das lässt sich in linearer Zeit eine Anzahl der Knoten sofort finden. Na gut, wenn man die Kanten wirklich durchgehen muss, um diejenigen Kanten mit unendlicher Kapazität zu finden, wenn man die nicht gleich zur Verfügung hat für jeden Knoten, gleich zur

Hand hat, welche Kanten davon unendliche Kapazität haben, die von diesen Knoten ausgehen, dann ist es vielleicht etwas voreilig zu sagen, das ist ein O von N. Auf jeden Fall linear in der Anzahl der Knoten und Kanten ist es garantiert. So, Netflow. Das Wort Netz heißt ja im Englischen nicht Net, sondern Network.

Net, weiß jemand was das heißt? Das ist das deutsche Lienwort Netto. Sie kennen das Netproduct.

Wissen Sie dann auch zufällig noch, was Brutto heißt auf Englisch? Na, wer war schon mal auf dem Austauschjahr oder sowas?

Gross Income, Gross Product oder sowas Brutto. Ist jetzt nicht weiter wichtig. So, wir haben jetzt nicht mehr viel Zeit. Wir gehen jetzt hier vielleicht ein bisschen darüber.

Worum geht es? Ich sage Ihnen jetzt einfach mal nur, worum es das Ganze jetzt geht.

Worauf das Ganze hinauslaufen wird. Und in die Details steigen wir beim nächsten Mal dann wieder ein.

So, wir haben S, wir haben jetzt wieder unseren Grafen. Und was uns interessiert sind jetzt solche Gebilde. Die nennen sich Cut, Schnitt, wo Kanten rübergehen. Also eine Menge von Knoten hier und eine andere Menge von Knoten hier.

Die eine Menge enthält S, die andere Menge enthält T. Und wo wir feststellen, Netto, was hier Netto rübergeht von links nach rechts.

Netto heißt, das was wirklich an Flusswerten von links nach rechts rübergeht, minus das was über Rückwärtskanten zurückfließt. In dem Sinne Netto. Deshalb reden wir von Netto. Das ist egal welchen Schnitt wir hier ziehen.

Immer dieser Flusswert F, der aus S rausgeht. Hier ist ja auch ein Schnitt. Mit den Kanten die incident zu S sind. Und hier ist ja auch ein Schnitt mit den Kanten die incident zu T sind. Über jeden einzelnen Schnitt ist das der Flusswert. Und geht der Flusswert insgesamt als Netto, Fluss von links nach rechts durch.

Und das wiederum wird uns dazu führen, am Ende, dass das was maximal rüberfließen kann von S nach T durch das Netzwerk durch, beschränkt ist und zwar exakt beschränkt ist durch die kleinste Durchlässigkeit, durch die kleinste Kapazität eines solchen Schnittes.

Und exakt heißt, dass der maximale Flusswert tatsächlich identisch ist mit der minimalen Kapazität von allen diesen Schnitten, die hier drin sind.

Sodass wir also, was vor allem praktisch bedeutet, wenn wir werden Flussalgorithmen kennenlernen, diese Problem lösen. Und damit kriegen wir dann auch automatisch mit ein bisschen Zusatzarbeit, aber mit überschaubarer Zusatzarbeit, auch einen minimalen Schnitt raus.

Sozusagen ein Bottleneck, ein Flaschenhals. So, damit sind wir für heute am Ende. Die Details, wie gesagt, dann beim nächsten Mal. Für heute möchte ich mich bedanken.