Hallo, wir wollen uns jetzt noch ein weiteres Clustering-Verfahren anschauen, das auf Flussnetzwerken basiert.

Lassen wir uns zuerst mal besprechen, was Flussnetzwerke überhaupt sind.

Die beste Interpretation ist eigentlich, wir sprechen erst mal über diesen Absatz hier.

Man hat Knoten und diese Knoten sind jetzt, das hier könnte jetzt hier eine Fabrik sein.

Und hier ist das Lager und Warenseil von der Fabrik zum Lager.

Und das geschieht hier über Verbindungen, über gerichtete Kanten.

Also wir können über diese Knoten hier gehen, das ist hier Zwischenlager vielleicht.

Oder das ist ein Straßennetzwerk.

Und es gibt hier verschiedene Möglichkeiten zum Lager zu kommen.

Das Problem dabei ist aber, dass diese Kanten Kapazitäten haben.

Das ist hier diese Fabrik, die heißt Quelle.

Und dieses Lager ist eine Senke, im Sinne von etwas verschwindet.

Und diese Kanten sind erstens gerichtet und zweitens gewichtet.

Also zum Beispiel haben wir jetzt hier Kapazitäten 3 und 1 und 4, 1, 3, 2 und 1.

Also wenn wir das hier vorstellen, als wir stellen diese Fabrik irgendwas her, zum Beispiel Autos mal deswegen.

Und diese Transportwege hier, diese Transportstrecken, die haben Kapazitäten wie diese Zahlen an Zahlen.

Also kann diese Strecke hier 3 Autos pro Tag transportieren.

Also das ist vielleicht eine Logistikverbindung hier von diesem Knoten zu diesem Knoten.

Und das Ziel ist jetzt hier natürlich, den Fluss von der Quelle zur Senke zu optimieren.

Jetzt haben wir noch ein paar explizite Bedingungen an so einem Flussnetzwerk.

Erstens, die Kantenmenge ist so beschaffen, dass es keine antiparallelen Kanten gibt.

Also es darf nicht so etwas hier existieren.

Das ist verboten. Wir dürfen keine antiparallenen Kanten haben.

Also wenn UV bereits existiert, dann darf VU nicht auch eine Kante in diesem Netzwerk sein.

Und es gibt auch keine Selbstschleifen. Das hier ist auch verboten, hier sowas zu haben.

Und außerdem muss jeder Knoten in diesem Flussnetzwerk, also in diesem gerichteten Grafen, auf irgendeinem gerichteten Pfad von S nach T liegen.

Also das hier ist die Quelle, die heißt S und die Senke heißt T.

Also es gibt sehr viele Anwendungen für dieses Setting. Das kann jetzt eben wie gesagt ein Logistikproblem sein.

Ein Gasnetzwerk, also Erdgas, das man in Deutschland über Pipelines verschieben möchte.

Das ist ein Straßennetz mit verschiedenen Qualitäten, also weitere Straßen mit Mehrspuren oder kleinere Straßen mit weniger Spuren

mit verschiedenen Geschwindigkeitsbegrenzungen, Stromnetzwerke, wo die Kanten lighter sind mit unterschiedlichen Belastbarkeiten mit dem Strom usw.

Und wir möchten hier einen maximalen, optimalen Fluss erzeugen.

Und Fluss bedeutet in diesem Kontext folgendes, das ist eine Funktion von Ecke und Ecke, also auf Kanten.

Also eine Funktion auf Kanten nach R, wobei gilt, dass f von uv immer positiv ist oder 0 und kleiner gleich c von uv ist.

Wobei c die Gewichte der Kanten sind. Also hier heißen die Gewichte jetzt nicht w, sondern c für Capacity.

Das heißt, wenn dieser Punkt x heißt, dann ist das hier c von s,x.

Und ein Fluss hat die Eigenschaft, dass er nur positiv ist, also tatsächlich nur in die richtige Richtung geht, die dieser Fall hier vorgibt.

Und zweitens, dass er nicht stärker sein kann, als die Kapazität dieses Flussnetzwerkes auf dieser Kante, was er hier ergibt.

Also diese erste Eigenschaft ist eine Kompatibilitätsbedingung für dieses Flussnetzwerk.

Und das zweite ist die sogenannte Flusserhaltung.

Das bedeutet, dass jeder Knoten außer dem Senken und dem Quellknoten hat die Eigenschaft, dass, ich schau mal das mal an, das ist jetzt hier u,

jetzt fließt hier von irgendwelchen Knoten irgendwas rein, das ist jetzt f von x und das y, f von xu, das ist f von yu.

Das heißt, rein fließt f von xu plus f von u, das ist die linke Seite hier schon.

Es gibt keine weiteren Karten, die nach u rein zeigen.

Und dann hat es vielleicht drei ausgehende Kanten nach a, b und c.

Und das ist hier f von ua, f von ub und f von uc.

Und die Summe, f von ua plus f von ub plus f von uc, das ist das, was alles rausfließt.

Und diese Balancebedingung hier, die heißt Flusserhaltung, weil sie besagt, der Gesamtfluss, der nach u reinkommt, ist vielleicht der Gesamtfluss, der aus u rauskommt.

Also es kann kein Material in irgendwelchen Knoten gespeichert werden, das sind keine Zwischenlager oder sowas,

sondern das sind wirklich nur Knotenpunkte, in denen quasi die Möglichkeit besteht, dass man einen anderen Weg einschlägt, aber es ist kein Lager.