Herzlich willkommen zu Algorithmen 2 diese Woche.
Genau, also wie machen wir heute weiter?
Im Prinzip machen wir wie immer eigentlich eine Wiederholung von dem,
was wir demnächst gemacht haben, bis auf die Einführung.
Die wiederhole ich heute nicht.
Das hat ja der Professor gemacht.
Genau, und nachdem wir eben letzte Woche wiederholt haben, also letzte
Woche haben wir starke Zusammenhangskomponenten gemacht und einen
Algorithmus gesehen, der das in Linearzeit kann.
Linear heißt hier n plus m.
Nachdem wir das gemacht haben, behandeln wir im Prinzip Flüsse in
Netzwerken und gucken uns an, wie hängen Flüsse in Netzwerken mit
Schnitten zusammen?
Und gleichzeitig ist das der Punkt in der Vorlesung, wo wir vom im
Prinzip von den Sachen, die im Buch sind, auf das Skript wechseln.
Also wir haben jetzt das erste Ding, was tatsächlich in diesem Skript
hier drin ist.
Und die ganzen anderen Sachen, die wir vorher hatten, waren alle im
Prinzip im Buch und sind im Buch nachzulesen.
Genau, also gucken wir uns nochmal an.
Im Prinzip jetzt das dritte Mal, dass ich diese Definition hier zeige.
Ja, was ist eine starke Zusammenhangskomponente?
Na gut, starke Zusammenhangskomponente.
Dafür definiert man erst mal diese Relation hier und zwei Knoten
stehen in dieser Relation, wenn eben ein Pfad von u nach v existiert
und gleichzeitig ein Pfad von v nach u.
Das heißt, ich kann sowohl von u, v erreichen, als auch v von u.
Und dann nennt man eben die Äquivalenzklassen bezüglich dieser
Relation hier starke Zusammenhangskomponenten.
Genau, und jetzt sieht man hier zum Beispiel auf der linken Seite
einen Graphen und stellt fest, okay, hier existiert jedenfalls mal ein
Kreis.
Und dadurch, dass hier ein Kreis existiert, heißt das implizit schon
mal sowieso, dass diese Knoten in der gleichen Zusammenhangskomponente
sein müssen.
Und dann hatten wir dazu definiert einen Schrumpfgrafen, der eben alle
Knoten, die in derselben Zusammenhangskomponente sind, im Prinzip
kontrahiert.
Und wenn gerichtete Kanten zwischen diesen Komponenten im
Originalgrafen existieren, dann sind die eben auch in diesem
Schrumpfgrafen.
Okay, dann hatten wir einen abstrakten Algorithmus definiert.
Der im Prinzip folgendes macht.
Wir haben einen Graphen gc.
Der hat die Knoten vom Originalgrafen und eine Kantenmenge, die Stück
für Stück immer wieder weiter erweitert wird.
Und dann haben wir hier so eine Invariante, die sagt, okay, die
starken Zusammenhangskomponenten von diesem Grafen gc sind bekannt.
Und dann erweitere ich Stück für Stück für alle Kanten im
Originalgrafen diese Kantenmenge hier und mache irgendwelche
Berechnungen, sodass ich eben die SCCs in dem Grafen kenne.
Genau, da hatte ich schon mal bemerkt, okay, für beliebige
Kantenreihenfolgen gibt es da nichts, was effizient ist.
Wir wollen ja am Ende einen effizienten Algorithmus haben.
Das heißt, was wir gemacht haben, ist, wir haben uns überlegt, wir
wollen die Kanten hier im Prinzip in der Reihenfolge hinzufügen, wie
sie bei einem Tiefensuchschema durchlaufen werden.
Genau, hier nochmal die Definition von dem Schrumpfgrafen.
Genau, dann hatten wir uns überlegt, okay, was passiert eigentlich,
wenn man jetzt so eine neue Kante zu GC hinzufügt?
Da gab es im Prinzip drei Fälle.
Der erste Fall ist ja, okay, die Kante ist innerhalb einer SCC, also
zum Beispiel diese Kante hier, dann ändert sich nichts an der
aktuellen Repräsentation der SCCs.
Und die anderen beiden Fälle sind, die neue hinzugefügte Kante führt
zu keinem Kreis.
Auch da ändern sich die SCCs nicht.
Genau, da ändern sich die SCCs nicht.
Was allerdings passiert ist, dass eine Kante in dem Schrumpfgrafen
hinzukommt.
Und der dritte Punkt war, okay, wir schließen einen Kreis.
Und das heißt, das ist der spannende Fall, dass man die SCCs, die auf
diesem Kreis liegen, dass man die kollabieren muss.
So, dann hatten wir Notationen eingeführt, haben gesagt, okay, wir
haben jetzt VC, das sind die markierten Knoten.
Wir haben eine Kantenmenge EC, das sind bisher explorierte Kanten.
Das sind eben genau die, die wir Stück für Stück hinzufügen.
Und dann haben wir gesagt, es gibt aktive Knoten, die sind markiert,
aber nicht finisht in diesem Tiefensuchschema.
Wir haben, wir haben Nomenklatur eingeführt für SCCs, nämlich nicht
erreichte SCCs, das sind genau die unmarkierten Knoten.
Offene SCCs, das sind SCCs, die aktive Knoten enthalten.
Abgeschlossene SCCs sind SCCs, in denen alle Knoten gefinisht sind.
Und wenn das der Fall ist, dann gibt dieses Array-Component, was wir
da sehen, für einen Knoten den Repräsentanten ein.
Ups, das war der falsche Knopf.
So, und was wir als nächstes gemacht haben,
was wir als nächstes gemacht haben in der...
So, kann man das noch lesen?
Okay, ist sehr, sehr klein, ein bisschen näher ran hier.
Okay, also was wir als nächstes gemacht haben, ist im Prinzip, wir
haben uns dieses Tiefensuchschema nochmal angeschaut.
Das ist in der Tat ja nichts Neues für euch.
Tiefensuchschema ist einfach, ich habe, ich habe einen Graphen und was
das macht im Kontrast zu Breitensuche ist, es sucht halt immer erst
mal in die Tiefe und geht dann weiter.
So, und dieses Tiefensuchschema haben wir jetzt genommen und uns diese
speziellen Funktionen angeschaut, diese Template-Funktion, die in
diesem Tiefensuchschema hier enthalten sind, nämlich diese Init, Root,
TraverseNonTreeEdge, TraverseTreeEdge und BackTrack.
Jetzt haben wir diese Funktion genommen und haben im Prinzip diese
Funktion instanziiert mit speziellen Methoden und haben dann
nachgerechnet oder gezeigt, dass durch die speziellen Instanzierung,
die wir da haben, wir am Ende die starken Zusammenhangskomponenten vom
Original -Graph berechnen.
Genau, wie war das?
Wir haben im Prinzip gesagt, okay, wir haben jetzt zwei Stacks.
Ein Stack für die offenen Repräsentanten und ein Stack für die offenen
Knoten.
Die sind in der Innenfunktion, werden die einfach initialisiert.
Ja, also dieses Komponenten-Array ist einfach ein neues Array.
Offene Repräsentanten ist einfach ein Stack, offene Knoten ist
ebenfalls ein Stack.
Und dann haben wir, das muss ich auch noch dazu sagen, für jede dieser
Funktionen haben wir nachgerechnet, dass die In-Varianten, die ich
jetzt hier oben rechts habe, dass die immer erfüllt sind.
Und mit diesen In-Varianten haben wir ein Theorem gezeigt, dass die
abgeschlossenen SCCs in GC genau schon die entsprechenden SCCs im
Original -Graphen sind.
Das heißt insbesondere, dass wenn ich alle Kanten hinzugefügt habe und
alle SCCs abgeschlossen sind, dass die SCCs nachher die SCCs im
Original -Graphen sind.
So, also dann haben wir diese Init-Funktion hier hinzugefügt, haben
nachgerechnet, die In-Varianten hier sind erfüllt.
Und als nächstes haben wir uns angeschaut, was macht man hier mit
dieser Root-Funktion?
Das heißt, wenn man tatsächlich von einem Knoten auf eine neue
Tiefensuche startet.
Na gut, dann fügen wir zu unseren offenen Repräsentanten den Knoten S
hinzu, zu unseren offenen Knoten fügen wir ebenfalls den Knoten S
hinzu und haben dann gesagt, okay, der Knoten S ist die einzige offene
Komponente.
Und damit, oh Wunder, bleiben diese ganzen In-Varianten hier wieder
erhalten.
Also nochmal, In-Variante 1 heißt, Kanten von abgeschlossenen Knoten
gehen zu abgeschlossenen Knoten.
Okay, wir haben hier nur eine offene Komponente.
Das heißt, das Ding hier ist sicher erfüllt.
Zweitens, offene Komponenten bilden einen Pfad in GCS.
Dadurch, dass wir eben nur einen Knoten haben, ist diese In-Variante
auch erfüllt.
Repräsentanten partitionieren die offenen Komponenten bezüglich ihrer
DFS -Nummer offensichtlich auch erfüllt, also nichts zu tun für diese
Funktion.
So, die
zweite Funktion, die wir uns angeschaut haben, war TraverseTreeEdge.
Das heißt, was passiert, wenn man in dieser Tiefensuche jetzt eine
TreeEdge sich anschaut?
Na gut, wenn man eine TreeEdge sich anschaut, dann macht man einfach
wieder den Endpunkt der Kante wird einfach auf unsere offenen
Repräsentanten hinzugefügt, ebenfalls auf unsere offenen Knoten und
wir sagen, dass der Knoten, den wir da gerade hinzugefügt haben, eine
neue offene Komponente ist und dann wieder nachrechnen.
Ja, die ganzen In-Varianten hier gelten alle.
Kein Wunder, also die abgeschlossenen Knoten haben wir nicht
verändert.
Die offenen Komponenten wurden um einen Knoten erweitert, dessen DFS
-Nummer eben größer ist als alle anderen.
Das heißt, die zweite In-Variante gilt auch und die dritte In-Variante
gilt auch, weil die neue hinzugefügte Komponente eben genau aus einem
Knoten besteht.
So, die dritte Funktion, die wir uns angeschaut haben, war
TraverseNonTreeEdge.
Genau, und hier passiert im Prinzip die ganze Magie.
Ja, also wenn ich eine Nicht-Baumkante habe, dann heißt es im Prinzip,
ich habe einen Kreis gefunden und da muss ich genau die ganzen SCCs
kollabieren, die auf dem Kreis liegen.
Das heißt, was macht diese Funktion?
Also erstmal, das ist der Pfad, den ich in GC hier habe.
Das ist der aktuelle Knoten V und jetzt habe ich diese blaue Kante,
die eine Nicht-Baumkante ist.
Oh, okay, Entschuldigung.
So, also hier ist der Knoten V, hier ist der Pfad von der Tiefensuche.
Die blaue Kante hier ist eben die Nicht-Baumkante.
Und die trifft auf dem Knoten W.
Als allererstes haben wir schon festgestellt, okay, das hier oben ist
eine SCC.
Das heißt, der Knoten W, für den Knoten W existiert ein Pfad zu dem
Knoten R I.
R I existiert offensichtlich ein Pfad zu Knoten V.
Das ist eben genau der Baumpfad und wir haben ja die Kante von V nach
W.
Das heißt, insgesamt haben wir hier schon mal einen Kreis und das Ding
schließt tatsächlich auch einen Kreis.
Das heißt, wie gesagt, wir müssen diese SCCs auf diesem Pfad hier
kontrahieren.
So, wie macht man das?
Na gut, wir wissen, die ganzen offenen Repräsentanten hier, die liegen
alle auf dem Stack O-Reps, also auf dem Stack der offenen
Repräsentanten.
Das heißt, was ich jetzt im Prinzip machen muss, ist, genau diese
Repräsentanten hier, diese Repräsentanten hier einfach von dem Stack
der offenen Repräsentanten runternehmen.
Das heißt, dieser Repräsentant hier steht am Ende ganz oben und ist
der Repräsentant für alle offenen Knoten, die danach kommen.
Und das ist schon die Merge-Operation.
Das ist auch genau das, was dieser Pseudocode hier macht.
Alle offenen Repräsentanten, die eine DFS-Nummer haben, die größer ist
als dieser Repräsentant hier, werden von diesem Stack der offenen
Repräsentanten entfernt.
So, die letzte Funktion, die wir uns angeschaut haben, ist eben diese
Backtrack -Funktion.
Da war die Hauptfrage, wann schließe ich überhaupt eine Komponente ab?
Na gut, man schließt eine Komponente ab, im Prinzip genau dann, wenn
die Kante auf dem Repräsentanten, also wenn die Kante, die in diesen
Repräsentanten hier reinführt, wenn da drauf das Backtrack ausgeführt
wird.
Und wenn, das sieht man eben, weil diese Kante nachher ganz oben steht
auf dem Stack der offenen Repräsentanten.
Und danach, also erst mal am Anfang dieser Funktion wissen wir, diese
ganzen offenen Knoten sind alle noch auf dem Stack der offenen Knoten.
Das heißt, ich kann die alle runter poppen von meinem Stack, kann dem
den Repräsentanten zuweisen und habe dann diese Komponente
abgeschlossen.
Okay, genau.
Gibt es noch Fragen dazu?
Das war jetzt nochmal im Prinzip Speedy Gonzales für SCCs in O von N
plus M.
Okay.
Okay, genau, also die nächste Sache, die wir uns anschauen im Sinne
von Stoff der Vorlesung sind jetzt genau diese Maximum Flows und
Matchings in Graphen.
Die Folien sind jetzt auf Englisch.
Gleichzeitig ist es so, dass der Aufschrieb, den ich da habe, dass der
teilweise auf Deutsch, teilweise auf Englisch ist.
Ich hoffe, das irritiert euch nicht.
Damit kommt ja, glaube ich, klar.
Es sei denn, ich entscheide mich dazu, das spontan zu übersetzen, was
ich da aufgeschrieben habe.
Genau, dann gibt es ein Buch von Kurt Mehlhorn und dem Herrn Neher,
die Lederplattform.
Das ist im Prinzip sowas ähnliches oder ein bisschen was Allgemeineres
wie dieses KHelp-Werkzeug, was wir haben.
Es gibt eine ganze Menge von Primitiven, mit denen man im Prinzip
einfach Graph-Algorithmen implementieren kann.
Und gleichzeitig stellt das Buch eben Fluss-Algorithmen dar.
Das heißt, da kann man auch nochmal den Stoff nachlesen, den wir hier
machen.
Auch ein sehr spannendes Buch ist das von Ahuja, Network Flows,
ungefähr so dick, aber hat irgendwie zahlreiche Algorithmen, die alle
extrem spannend sind.
Und was auch nochmal wichtig ist, was wir auch im Laufe der Vorlesung
noch sehen werden, sind Zusammenhänge, die jetzt hier auftauchen mit
diesen Flüssen.
Zum einen werden wir sehen, Flüsse hängen mit Schnitten zusammen.
Auf der anderen Seite werden wir sehen, wir wollen oder können im
Prinzip kürzeste Wege-Algorithmen benutzen, um Flüsse zu berechnen.
Und dann kommen auch noch Matchings dazu, wo man mit Flüssen eben
Matchings berechnen kann.
Das heißt, alles ist irgendwie wunderbar verwoben miteinander und
alles gehört irgendwie zusammen, aber es ist doch irgendwie alles was
anderes.
Okay, also erst mal definiere ich jetzt, was meine ich überhaupt mit
einem Flussnetzwerk?
Normalerweise ist es so, dass wir eine Quelle S gegeben haben, S und
eine Senke T.
Und in diesem Problem wollen wir oder in diesem Grafen, den wir hier
sehen, wollen wir im Prinzip so viel wie möglich Fluss, können wir uns
vorstellen als Flüssigkeit, von S nach T transportieren.
Jetzt haben wir natürlich Einschränkungen.
Diese Einschränkungen sagen uns, für eine bestimmte Kante kann ich
maximal so und so viel Fluss über diese Kante senden.
Das nennt man dann Kapazitäten.
Also wir sehen hier in dem Beispiel, dass man hier höchstens zehn
Einheiten Fluss rüber schicken kann.
Auf dieser Kante höchstens vier, auf dieser Kante höchstens acht.
Ja, und dann haben wir für jede Kante in dem Netzwerk haben wir eine
Kapazität, die uns sagt, wie viel Fluss kann ich da maximal
drüberschieben?
Genau, und diese Kapazität ist offensichtlich nicht negativ, weil
negativen Fluss kann man da nicht drüberschieben.
Genau.
So, jetzt definieren wir, was ich überhaupt meine mit Fluss.
Na gut, also ein Fluss ist nichts anderes als eine Funktion auf den
Kanten, wobei null kleiner gleicht eben dieser Flusswert ist, kleiner
gleicht der Kapazität.
Und das hier im Speziellen für jede Kante.
Also für jede Kante haben wir eine Kapazität definiert und der Fluss
sagt uns dann, okay, der muss immer kleiner gleich der Kapazität sein.
Ja, sonst ist halt kein gültiger Fluss für dieses Netzwerk.
Dann haben wir eine Invariante, die uns sagt, für jeden Knoten in dem
Netzwerk außer S und T ist der eingehende Fluss gleich der ausgehende
Fluss.
Das heißt, wenn ich mir wieder eine Flüssigkeit vorstelle, dann heißt
das im Prinzip, dass wenn ich eine bestimmte Menge an Flüssigkeit in
den Knoten reinstecke, dann muss die halt auch wieder rausfließen
irgendwohin.
Sonst ist es halt kein gültiger Fluss.
So, dann definieren wir uns den Wert eines Flusses.
Im einfachsten Fall können wir jetzt sagen, okay, das ist nichts
anderes als die Gesamtmenge von Fluss oder Flüssigkeit oder was auch
immer, die aus dem Knoten S herausfließt.
Also in dem Fall stellen wir erst mal fest, also in dem Beispiel
stellen wir erst mal fest, das ist ein gültiger Fluss, weil alle
Flusswerte hier in hellblau dargestellt sind kleiner gleich der
Kapazität, das sind die schwarzen Werte.
Und der Wert des Flusses hier ist 10 plus 8, das heißt 18, weil ja,
weil in dem konkreten Beispiel eben genau 18 Einheiten aus dem
Quellknoten da hinaus fließen.
Genau, gleichzeitig, das habe ich ja auch gesagt, ist der Wert des
Flusses in T hinein, 12 plus 6 ist also auch 18.
Das heißt, wir können sowohl hier vorne schauen als auch hier hinten.
So im Laufe der Vorlesung werden wir dann sehen, dass wenn ich jetzt
irgendeinen Schnitt mir nehme, was auch immer ein Schnitt ist, das
definiere ich gleich noch genau,
dann ist im Prinzip der Wert des Flusses dadurch gegeben, was aus
diesem Schnitt rausfließt, minus das, was in diesem...
Moment, was aus diesem Schnitt rausfließt, minus das, was in diesen
Schnitt reinfließt.
Sondern das Hauptziel, was wir jetzt haben bei diesem Flussproblem,
ist immer, einen maximalen Fluss zu finden.
Ich will möglichst viel Flüssigkeit, Ware oder was auch immer, von S
nach T schicken.
Genau, was man sich jetzt zum Beispiel auch gut vorstellen könnte,
ist, ich habe zwei Lager, S und T, und ich möchte möglichst viel von
dem einen Lager an das andere transportieren.
Und jetzt könnte ich zum Beispiel dafür das Straßennetzwerk benutzen,
um dann eben genauso Flüsse zu berechnen.
Genau, so als nächstes, das hatte ich eben schon gesagt, definiere ich
Schnitte oder auch minimale Schnitte.
Genau, also hier definieren wir im Speziellen ST-Schnitte.
Also ein ST-Cut ist nichts anderes als eine Partition von V in S und
T, wobei S jetzt in der Menge S ist und T in der Menge T.
Und Partition heißt hier wieder, okay, S vereinigt T, ist wieder die
ganze Knotenmenge.
Und wenn ich S mit T schneide, dann ist es gerade die leere Menge.
Das heißt, kein Knoten kann in beiden Mengen sein.
Und gleichzeitig müssen aber alle Knoten in einer von den beiden
Mengen sein.
So, dazu definieren wir uns jetzt die Kapazität.
Die Kapazität von so einem Schnitt, das ist eben genau die
Kapazitäten, die von der Menge, die Kapazitäten der Kanten, die von
der Menge S in die Menge T hineingehen.
Also hier sehen wir die Menge S in Rot dargestellt, die ersten beiden
Knoten unten links und die Menge T als der ganze Rest.
Und da ist die Kapazität eben genau die diese ganzen schwarzen Zahlen
hier aufverliert.
Das heißt 4 plus 4 plus 10.
Das heißt, die Kapazität von diesem Schnitt ist 18.
Genau so genau.
Und dann werden wir später sehen im Laufe der Vorlesung, dass der Wert
eines maximalen Flusses eben genau die Kapazität von einem minimalen
ST -Schnitt ist.
Und das ist ein super Ergebnis.
Also jetzt haben wir auf einmal Flüsse mit mit minimalen Schnitten in
den Graphen in Zusammenhang gebracht.
Und wie gesagt, später beweisen wir das.
Hier haben wir erst mal ein Beispiel.
Wir haben ja diesen Schnitt, den ich gerade eben definiert habe.
Dieser Schnitt hat Kapazität 18, 4, 4, 10 und gleichzeitig fließt hier
10, 4, 4 drüber.
Ja, und über alle diese Kanten kann ich nicht mehr Fluss drüber
senden.
Also alle Kanten sind irgendwie ausgereizt, was den Fluss angeht.
Und das ist eben was sehr Spezielles.
Und da werden wir gleich nachrechnen.
Okay, das führt dazu, dass genau eben der Wert eines maximalen ST
-Flusses die minimale Kapazität von einem ST-Schnitt ist.
So, also wo braucht man das?
Es gibt unzählige Mengen von Anwendungen dafür.
Zum Beispiel eben Traffic Flows und Highways zu berechnen im Image
Processing.
Also wir stellen uns mal vor, wir wollen dieses Kindchen hier von dem
Hintergrundbild trennen.
Da kann man auch wieder einen Graphen definieren und Unterschiede in
den Pixelwerten und dann kann man eben genau dieses Minimum Cut
Problem lösen, um genau diese Grenzen hier zu finden und dann dieses
Kind dort raus zu segmentieren.
Genau, was wir auch machen können ist Disc Machine oder Tanker
Scheduling, wobei ich da auch kein Experte bin.
Ja, ich kenne die Anwendung auch nicht genau oder Matrix Rounding oder
was auch immer.
Also für Details einfach mal ins Skript reinschauen.
So, jetzt gibt es hier verschiedene Anwendungen in unserer Gruppe, zum
Beispiel Multicasting using Network Encoding oder Balance K
Partitioning und dadurch, dass ich eben Balance K Partitioning mache,
zeige ich euch jetzt die Anwendung vom Balance K Partitioning.
Okay, also ich wiederhole gerade noch mal, also X-Kurs.
Balanced.
Also ich mache jetzt für euch im Prinzip Balance By Partitioning.
Wir lassen dieses K mal weg und machen uns das ein bisschen einfacher.
Balance By Partitioning.
Okay, also was haben wir noch mal für ein Problem?
Balanced Graph Partitioning sagt, okay, wir haben einen Graphen V E
mit einer Kostenfunktion auf den Knoten und einer Kostenfunktion auf
den Kanten.
Und dann haben wir gegeben eine Zahl K, also im Moment K gleich zwei.
Das ist die Anzahl Teilen, die wir diesen Graphen aufteilen wollen.
Und wir haben den Inballons Parameter gegeben, Epsilon größer Null,
wobei hier Epsilon auch eine reelle Zahl ist.
So, das Ziel von dem Problem
finde V1, V2 mit, also V1 vereinigt, V2 ist V und V1 geschnitten, V2
ist die leere Menge.
Das heißt, wir wollen eine Partition finden in V1 und V2.
Und zwar so, dass die Kosten von dem V E hier kleiner sind als 1 plus
Epsilon mal die Gesamtkosten durch zwei.
Das heißt, was hier steht, ist, dass die aufsummierten Gewichte von
beiden Blöcken im Prinzip ungefähr gleich groß sein sollen.
Und dieses Epsilon gibt eben die Abweichung vom Mittelwert ab.
So, wie kommen jetzt hier Flüsse ins Spiel?
Also das Ziel, also die Zielfunktion, die wir optimieren wollen,
minimiere die Anzahl Kanten
zwischen V1 und V2.
Das ist unsere Zielfunktion.
Und kann man auch noch mal ein Bild zumalen.
Wir haben hier einen Grafen, haben irgendwie einen Schnitt.
Das ist V1, das ist V2 und genau diese Kanten, die zwischen diesen
Blöcken verlaufen, die sollen minimiert werden unter den
Nebenbedingungen, dass eben diese beiden Blöcke gleich groß bleiben.
So das Problem ist jetzt erst mal ähnlich zu dem, was wir gerade
hatten.
Also vorher war dieses Minimum Cut Problem, wo ich einen kleinen
Schnitt, einen kleinen ST-Schnitt finden möchte.
Allerdings haben wir hier noch das Problem, dass wir tatsächlich
balancierte Blöcke haben wollen.
Das heißt, diese Balance, diese Balanziertheit steckt in diesem
normalen ST-Problem gar nicht drin.
Aber was man tatsächlich machen kann, ist, wir bauen jetzt für dieses
Problem, um eben die Anzahl Kanten zu minimieren.
Bauen wir ein Plus Problem auf, was dazu führt, dass wir kleinere
Schnitte finden können und diese Nebenbedingungen erhalten bleibt.
Das heißt, was können wir machen?
Habe ich hier nochmal ein Bild?
Sieht man das?
Ja.
So, das heißt, wir haben hier unsere Partition in V1, V2.
Wir haben hier Randknoten.
So, was machen wir?
Wir nehmen diese ganzen Knoten hier und führen im Prinzip eine
Breitensuche aus in diese Richtung.
So, dann nehmen wir diese Knoten hier, führen eine Breitensuche aus in
diese Richtung.
So, und diese Breitensuchen werden genau dann gestoppt, wenn der Worst
Case, nämlich dass alle diese Knoten hier zu dem anderen Block
hinzugefügt werden nachher, wenn der im Prinzip erreicht wird.
So, jetzt definieren wir dazu ein Plus Problem, wir fügen den Knoten S
ein, verbinden den mit allen Knoten in der linken Seite, hier
Kapazität und endlich für den Knoten T ein, verbinden den mit allen
Knoten, die hier sind, auf der rechten Seite Kapazität und endlich.
Und jetzt habe ich ein Plus Problem definiert, was ich im Prinzip
durch diese Dualität, die wir eben gesehen haben, lösen kann, indem
ich ein Max-ST-Flow berechne.
Dadurch kriege ich einen minimalen Schnitt und habe dann eine Methode
gefunden, mit der ich wunderbar Schnitte finden kann, die balanciert
sind.
Das heißt, ich habe auf einmal Balance-Partitioning mit irgendwas, was
vorher nicht balanciert war.
Genau, gucken wir uns noch ein Beispiel an, warum das, warum das
funktioniert.
Also hier nochmal die Konstruktion.
Ich habe es ja eben schon im Detail erklärt.
So, also stellen wir uns mal vor, wir haben jetzt hier irgendwie
diesen Grit-Graphen und wir möchten offensichtlich die Schnittkanten,
die wir hier sehen, verbessern.
Das ist offensichtlich keine gute Partition, wir haben hier Kurven
drin und so.
Die Anzahl der Schnittkanten, die man da hat, ist sicherlich nicht
gut.
Also bauen wir uns ein Plus Problem zusammen, indem wir eben
Breitensuchungen ausführen, einmal in die linke Seite, das ist der
grüne Bereich, einmal in die rechte Seite, das ist der rote Bereich.
Wir führen zwei Knoten S und T ein, lösen dieses Max-Flow-Min-Cut
-Problem, finden also einen besseren Cut und haben damit einen
besseren Cut für das Originalproblem.
Okay, das ist also eine dieser Anwendungen für Max-Flow-Min-Cut.
Die Frage war, wann bricht die Breitensuche ab?
Die Breitensuche bricht ab, wenn im Prinzip in dem Beispiel her,
wenn...
Moment, da in dem Beispiel hier die Breitensuche in den linken Bereich
bricht ab, wenn der Worst-Case eben, also der Worst-Case ist ja, alle
diese grünen Knoten werden zu dem rechten Block hinzugefügt.
Okay, weil im schlimmsten Fall läuft dieser minimale Schnitt genau auf
dieser Grenze auf der linken Grenze und die Breitensuche bricht ab,
wenn dieser Worst-Case-Fall im Prinzip zu einer imbalancierten Lösung
führen würde.
Das heißt, mit größerem Epsilon werden diese Flussprobleme größer, mit
kleinerem Epsilon werden die Flussprobleme kleiner.
Okay, Frage beantwortet?
Okay.
Genau, so.
Okay, die nächste Frage ist, wie löst man diese Flussprobleme?
Jetzt haben wir schon mal gesehen, okay, es gibt eine Million
Anwendungen für diese Flussprobleme.
Das heißt, als Algorithm-Engineer sind wir irgendwie in der Situation,
dass wir die Flüsse tatsächlich berechnen müssen, um eben kleine
Schnitte zu finden oder eben um speziell Flussprobleme zu finden.
So die erste Idee, die man hat, wenn man schon mal Integer-Linear
-Programming gemacht hat, ist, ich schreibe ein lineares Programm.
Dieses lineare Programm sagt jetzt, ich habe Flussvariablen x, xe für
jede Kante e.
Die gibt mir jetzt an, wie viel Fluss läuft über diese Kante.
Dann habe ich ein Constraint, was mir sagt, wie viel Fluss darf ich
auf jeder Kante maximal haben?
Ich habe dieses Constraint, für jeden Knoten muss der eingehende Fluss
gleich der ausgehende Fluss sein.
Und meine Zielfunktion sagt, maximiere den ausgehenden Fluss vom
Startknoten.
So, schreiben wir das auch noch mal hin, dass wir es vollständig
haben.
Also...
Linear -Programming...
Also, maximiere Summe e gleich sv in e, xe, sodass die Summe...
Also wir haben jetzt erstmal hier die Zielfunktion geschrieben.
Die sagt nichts anderes als, maximiere den Fluss, der aus dem Knoten s
herausgeht.
Jetzt haben wir Constraints.
Das erste Constraint sagt, für alle Kanten u, v in e, xe ist das das
gleiche wie für alle Kanten v, w, x, e und zwar für alle v in v ohne s
und t.
Das ist genau diese Flusserhaltung, die wir jetzt hier haben.
Für jeden Knoten v soll der eingehende Fluss, deswegen steht hier v
auf der rechten Seite dieser Kante, gleich der ausgehende Fluss gehen.
Deswegen steht hier das v auf der linken Seite dieser Kante.
Das ist genau dieses Fluss-Constraint.
Und dann soll natürlich gelten fe kleiner gleich ce für alle xe, für
alle e in e und dieses xe ist größer gleich 0 für alle e in e.
So wie es da steht, kann ich es eins zu eins in den Solver
reinstecken, der mir dieses Problem löst.
Das Hauptproblem ist, dass es langsam ist.
Ja, also ich kann durch spezielle Algorithmen für dieses Problem
einfach die Lösungen, die Lösungen für das Problem viel schneller
finden.
Und deswegen machen wir den ganzen Kram hier.
Genau, also nochmal, ja, ich hebe es nochmal vor.
Wir können tatsächlich besser, wir können tatsächlich bessere Lösungen
für das Problem finden.
So, also das heißt, was ist im Laufe der Geschichte passiert?
Im Laufe der Geschichte gab es ziemlich viele Algorithmen, die das
Problem behandelt haben und die im Laufe der Zeit immer besser wurden
und immer im Prinzip schneller wurden, was algorithmische Komplexität
angeht.
Das heißt, hier im Jahre 1956 gibt es den Ford-Falckerson-Algorithmus.
Das ist genau der Algorithmus, den wir uns gleich als erstes anschauen
werden.
Der läuft in Zeit von m mal n mal u, wobei u hier der Wert des Flusses
ist.
Genau, dann gibt es den Dynics-Algorithmus.
Das ist jetzt unabhängig von dem Wert des Flusses, m mal n Quadrat.
Und dann gibt es unzählige andere Algorithmen, wobei hier u steht als
largest capacity.
Und dann gibt es unzählige andere Algorithmen, die im Prinzip immer
besser wurden.
Und dann hier 1986 gibt es noch einen wichtigen Algorithmus, den
werden wir auch im Laufe der Vorlesung sehen.
Das ist der Algorithmus von Goldberg und Tarjan, der sogenannte Push
-Relabel -Algorithmus.
Alle diese Algorithmen werden wir im Prinzip noch einzeln motivieren
und werden dann sehen, dass dieser Goldberg-Tarjan-Algorithmus
ziemlich gut in der Praxis funktioniert.
Genau, übrigens sowohl Andrew Goldberg als auch Robert Tarjan, die
leben beide noch.
Die trifft man regelmäßig auf Konferenzen und die sind beide auch
ziemlich cool drauf.
Also ja.
So, fangen wir mal an mit Ford Falkassen.
Ford Falkassen hat im Wesentlichen eine Idee.
Die Idee heißt, finde einen Pfad von S nach T, der noch Kapazitäten
frei hat und dann reize diesen Pfad, also schicke einfach mehr Fluss
entlang diesem Pfades.
Und zwar so, dass die kleinste Kapazität, die es auf diesem Pfad gibt,
danach ausgereizt ist.
Das heißt, es existiert nach dem Erhöhen des Pfades, existiert eine
Kante, die halt ausgereizt ist.
Das heißt, der Pfad existiert danach nicht mehr so, wie er war in dem
entsprechenden Netzwerk.
Genau, danach werden die Kapazitäten angepasst und ein Konzept des
sogenannten Residual Grafs.
Ja, genau dieser Graf wird dann eben aufgebaut.
So und dieser Residual Graf, das ist das, was ich glaube, ich als
nächstes erkläre, nachdem wir mit dem Beispiel durch sind.
Also hier nochmal das Beispiel vom Anfang, was wir jetzt machen ist,
wir suchen uns einen Pfad, in dem Fall hier oben der Pfad, der noch
Kapazität frei hat.
Jetzt erhöhen wir den Fluss entlang des Pfades um die höchste
Kapazität, die noch frei ist.
Das heißt hier, wenn wir uns anschauen, diese Kante hat 10 frei, diese
Kante hat 10 frei, diese Kante hat 12 frei.
Das heißt, wir können hier maximal über diesen Pfad 10 rüberschieben.
Das ist genau das, was der Algorithmus macht.
Das macht er auch mit dem nächsten Pfad hier.
Hier können wir maximal 4 rüberschieben.
Kapazitäten werden danach übrigens angepasst, bis halt nichts mehr
geht.
Und am Ende haben wir eben dann diesen Fluss berechnet.
Also ich mache das so lange, bis eben kein augmentierender Pfad mehr
existiert.
Und dann haben wir am Ende einen maximalen Fluss berechnet.
So, was wir jetzt brauchen, ist im Prinzip eine Notation, die nennt
sich Residualgraph.
In diesem Residualgraph existieren Kanten, genau dann, wenn ich von
dem einen Knoten auf den anderen Knoten Fluss schieben kann.
Okay, jetzt könnte man argumentieren, als allererstes mal, okay, das
kann ich ja in dem Originalgraphen schon machen, wenn ich einfach die
Kapazitäten ändere.
Der springende Punkt ist hier, dass wenn ich über eine Kante Fluss
hinüberschiebe, dass zum Beispiel, keine Ahnung, im Wert von S von
diesem Knoten zu diesem Knoten hier 4 Fluss rüberschiebe, dann kann
ich sie danach in der anderen Richtung ja eigentlich auch wieder
zurückschieben.
Deswegen haben wir dieses Konzept von Residualgraph, was eben genau
dann Kanten hat, wenn ich in eine bestimmte Richtung Fluss schieben
kann.
So, das heißt zu einem Graphen G und einem Fluss F definieren wir eben
genau dieses Residualnetzwerk G, F, V mit einer Kantenmenge E, F und
C, F, sodass für jede Kante haben wir erstens die Kante selber in dem
Residualnetzwerk, wenn der Fluss auf dieser Kante kleiner ist als die
Kapazität.
Ja, weil dann kann ich ja immer noch Fluss drüberschieben.
Und die Kapazität dieser Kante ist eben genau die Restkapazität, die
Residualkapazität.
Gleichzeitig füge ich die Rückwärtskante in dem Netzwerk zu dem
Residualgraph hinzu, wenn auf der Originalkante Fluss besteht.
Ja, weil das ist genau der Fluss, den ich quasi wieder in die
Rückrichtung schieben kann.
Und das ist genau auch dann die Kapazität von dieser Kante.
Genau, also hier sehen wir ein relativ kompliziertes Beispiel.
Mal einfach mal ein einfaches Beispiel.
Also stellen wir uns mal vor, ich habe wirklich nur einen kleinen
Graphen S, Knoten T.
Ich habe hier eine Kante mit Kapazität 5 und C gleich 5.
Und der Fluss auf dieser Kante sei jetzt mal 3.
Jetzt malen wir dazu das Residualnetzwerk.
Na gut, es hat offensichtlich immer noch beide Knoten.
Die Vorwärtskante mit Residualkapazität 2 und die Rückwärtskante hier
mit Residualkapazität 3.
Ja, weil auf der Vorwärtskante ist eben genau ein Fluss des Wertes 3.
Das heißt, die Rückwärtskante hier, ich kann ja über diese Kante 3
Fluss rüberschieben.
Das heißt, die Rückwärtskante existiert dort.
Und diese Kante hier hat noch eine Restkapazität von 5 minus 3.
Das heißt, das ist auch die Kapazität der Vorwärtskante im
Residualgraph.
Also super einfaches Beispiel.
Prima.
Genau.
So, was dieser augmentierende Pfadalgorithmus jetzt macht.
Hier nochmal als Pseudocode.
Im Prinzip sucht er eben nach Pfaden.
Und wenn ich einen Pfad augmentiere, also einen ST-Pfad augmentiere,
dann sucht er eben die kleinste Kapazität, die auf diesem Pfad in dem
Residualgraph frei ist und sagt dann, der Fluss wird für jede...
Moment, also für jede...achso genau.
Für jede Kante in dem Pfad muss ich mir jetzt anschauen, okay,
existiert die Kante im Originalgraphen.
Wenn das der Fall ist, dann erhöhe ich den Fluss entsprechend.
Wenn das nicht der Fall ist, dann ist es offensichtlich eine Kante,
die nur im Residualgraph existiert.
Das heißt, ich muss von der Rückwärtskante dementsprechend den Fluss
abziehen.
Ja, das ist schon die Magie hier.
Und das ist dann der insgesamt fortfahrende Algorithmus.
Am Anfang sagen wir, okay, der Fluss ist null.
Wir haben hier Kapazitäten von E nach N.
Das ist übrigens ein kleines Detail, wie wir gleich noch sehen werden.
Ja, da stehen die natürlichen Zahlen, da stehen keine reellen Zahlen.
Sonst führt das vielleicht zu Problemen, aber das sehen wir gleich
noch.
Der Algorithmus, wie gesagt, am Anfang setzt er den Fluss auf null.
Und solange ein Pfad existiert von S nach T im Residualnetzwerk, ja
gut, solange augmentieren wir halt diese Pfade.
Und dann werden wir gleich sehen, dass dieser Algorithmus tatsächlich
einen maximalen Fluss berechnet.
Genau, Quizfrage.
Als allererstes mal, wie findet man so Pfade in dem Residualnetzwerk?
Ja, eine Variante ist Tiefensuche.
Genau, also oder Breitensuche oder keine Ahnung.
Also aber im Prinzip genau richtig.
Also mit Tiefensuche oder Breitensuche findet man jetzt raus,
existiert hier überhaupt so ein Pfad und da kann man auch direkt ein
Pfad ausgeben.
Und das Augmentieren von einem Pfad, wie teuer ist es?
Na gut, ich muss alle Pfadkanten anschauen.
Das heißt, es kostet auch maximal O von M.
Wenn ich ein Pfad augmentiere, dann heißt das, dass sich der Wert des
Flusses um mindestens eins ändert.
Das heißt, die Laufzeit von dem Algorithmus hier ist offensichtlich O
von M mal der Wert von dem Fluss.
Ja, genau.
So, was wir jetzt machen wollen, ist, wir wollen mehrere Sachen
machen.
Als allererstes wollen wir mal nachweisen, dass dieser...
dass der Ford-Falker ist ein Algorithmus, den wir da haben.
Genau, dass er im Prinzip einen maximalen Fluss berechnet und dann
werden wir auch gleich sehen, dass wir damit zu einem minimalen
Schritt kommen und wie wir damit zu einem minimalen Schritt kommen.
Genau, also...
Wiederholen wir doch mal kurz.
Also wir haben gesagt, ein ST-Cut ist eine Partition von V in S und T.
Wobei hier S in S ist und T in T.
Und die Kapazität von diesem Schnitt haben wir gesagt, ist nichts
anderes als C von S.
Das definieren wir als C von S, V ohne S.
Wobei das hier im Prinzip genau T ist.
Und das ist jetzt definiert als Summe über alle Knoten U in S und V in
T.
Und zwar die entsprechenden Kapazitäten.
Also das ist die Kapazität von dem Schnitt, den wir da haben.
Als nächstes müssen wir uns überlegen, wann nennen wir einen
Schnitt...
wann nennen wir einen Schnitt saturiert?
Wir sagen okay, ein Schnitt ist saturiert,
wenn die Kapazität gleich dem Flusswert entspricht.
Und zwar für alle Kanten UV mit U in S.
Also genau.
U in S und V in T.
Und gleichzeitig soll der Rückfluss gleich Null sein für alle Kanten
VU mit V in T und U in S.
Genau dann ist dieser Fluss eben saturiert, was im Umkehrschluss
heißt, machen wir mal noch ein kleines Bild dazu.
Nehmen wir mal an, wir haben hier so einen Schnitt S und T.
Und wenn der saturiert ist, dann heißt das, dass ich über diesen
Schnitt keinen Fluss mehr drüber schieben kann.
Das ist genau diese Eigenschaft, die ich hier habe.
Alle Kanten, die von links nach rechts gehen, sind saturiert und alle
Rückwärtskanten haben Fluss Null.
Das heißt, ich kann den Fluss über diesen Schnitt nicht mehr erhöhen.
Okay, was wir jetzt zeigen wollen, das ist das genau, was ich meine
mit Deutsch und Englisch.
Wir wollen zeigen, die Kapazität eines S-T-Schnittes ist eine obere
Schranke für einen beliebigen S-T-Fluss.
So, damit sind wir dann schon mal einen Schnitt weiter.
Das heißt, wenn ich das gezeigt habe, dann kann ich einen beliebigen
Schnitt hernehmen und habe damit eine Schranke für den maximalen Wert
eines S-T-Flusses.
Und intuitiv ist das übrigens hier schon klar, aber ich zeige es
trotzdem noch.
Also, Lemma.
Also, sei F beliebiger S-T-Fluss
und dieses Ding hier,
S, V ohne S, beliebiger S-T-Schnitt,
dann ist der Wert von dem Fluss, der Value von dem Flow, kleiner
gleich die Kapazität des Schnittes.
So, und weiter.
Wenn es saturiert ist,
dann gilt sogar, dass der Wert von dem Fluss genau der Wert von dem
Schnitt ist.
Beweis.
So, Beweis.
Also, der Wert von dem Fluss ist irgendwie offensichtlich.
Ich schreibe es erstmal hin.
Minus Summe E in E geschnitten.
T Kreuz S.
Okay, also was hier steht, ist, dass der Wert des Flusses, gegeben ein
S -T-Schnitt, also, dass der Wert dieses Flusses nichts anderes ist,
als alles, was von S nach T fließt, in diese Richtung.
Also, S nach T-Edges.
Der ganze Fluss, der von S nach T fließt, in diese Richtung, minus
das, was in die andere Richtung fließt.
Das ist der S-T.
Das ist der entsprechende Fluss.
Naja, und jetzt weiß ich, diese Flusswerte hier, F, E, die sind immer
positiv.
Das heißt, da steht jetzt nichts anderes als Summe, also, kleiner
gleich Summe E in E, S-Kreuz, T, F, E.
Und diese F, E hier, Definition von dem Flussproblem, ist nichts
anderes als E in E geschnitten, S-Kreuz, T, die Kapazität dieser
Kante.
Und was hier jetzt steht, oh Wunder, ist genau die Kapazität von dem
Schnitt.
Das heißt, hier steht schon die erste Ungleichung.
Der Wert des Flusses ist, nochmal zur Wiederholung, alles, was von S
nach T fließt, minus alles, was von T nach S fließt.
Das ist kleiner gleich, wenn ich den ganzen Term hier hinten weglasse,
kommen wir auf diese Gleichung.
Und das ist wiederum kleiner gleich, durch die Abschätzung der
Flusswerte, durch die Kapazitäten, kleiner gleich diese Summe hier.
Und das ist eben genau die Kapazität dieses Schnittes.
So, und jetzt hatten wir ja eben eingeführt, sieht man das noch?
Was heißt es, dass ein Schnitt saturiert ist?
Na gut, also wenn der Schnitt saturiert ist, dann heißt es zum einen,
dass die Kapazitäten in die Vorwärtsrichtung von S nach T, dass die
alle ausgeschöpft sind.
Und in die andere Richtung gilt, dass die Flusswerte hier alle Null
sind.
Das heißt, diese Summe hier hinten, die ist insbesondere Null.
Das heißt, schreiben wir es nochmal hin,
wenn Schnitt saturiert, dann gilt F von E gleich Null für alle E
gleich VU mit V in T und O in S.
Und das daraus folgt eben, dass diese letzte Summe hier
E in E geschnitten T kreuz S F E gleich Null ist.
Und daraus folgt, zusammen mit der anderen Bedingung, nichts anderes
als der Wert des Flusses ist eben genau der Wert des Schnittes.
Genau, das heißt, wenn ich nochmal einen saturierten Schnitt habe,
dann weiß ich eben den Wert des optimalen Flusses.
So.
Okay.
Als nächstes schauen wir uns an,
schauen wir uns noch ein Lemma an.
Okay, also ein Lemma.
Wir haben einen Fluss in unserem Netzwerk und wir haben das Residual
-Netzwerk.
Also GF
Residual Network.
Und S ist eben genau die Menge V in V mit V erreichbar von S in GF.
Genau.
Also nochmal, wir haben einen Fluss, wir haben das Residual-Netzwerk
GF und jetzt definieren wir eine Menge S, die aus allen Knoten
besteht, die in dem Residual-Netzwerk noch erreichbar sind.
Das heißt insbesondere, wenn ich darüber hinweg möchte, über diese
Menge S, dann komme ich nur noch zu saturierten Kanten.
Das heißt, wir werden gleich sehen, dass diese Menge S hier nachher
ein Zeuge ist für die Maximalität eines Flusses.
Genau, also schreiben wir mal die Aussagen hin.
Dann gilt also erstens, wenn T in S ist, dann ist der Fluss
offensichtlich nicht maximal.
Aber wenn dieses T in F ist, dann kann ich im Prinzip, das werden wir
auch gleich noch im Detail sehen, einen neuen Fluss konstruieren, der
einen höheren Wert hat.
Und die zweite Aussage ist, wenn T nicht in S ist, dann ist S ein
saturierter Schnitt
und F ist Maximum.
Also beweisen wir das wieder.
Erstens sei P ein einfacher Pfad von S nach T in GF.
Genau.
Dann sagen wir, okay, Delta F ist die minimale residuale Kapazität
über alle Kanten in P. Dann muss ja offensichtlich dieses Delta F
größer 0 sein, sonst wäre es eben nicht in dem Residualkraft
enthalten.
Und dann definiere ich mir einen neuen Fluss als F von E plus Delta F
wenn E in P ist.
F von E minus Delta F wenn E nicht in P ist.
Und Moment, das stimmt nicht ganz.
Wenn die entsprechende Rückwärtskante in P ist und F von E sonst.
Das ist jetzt offensichtlich ein gültiger Fluss und für diesen Fluss
gilt der Wert von F' ist eben genau der alte Wert plus das, was wir da
eben drauf addiert haben und F' ist Flow.
Und das ist offensichtlich größer als vorher, das heißt F war vorher
nicht maximal.
So, zu zweitens.
Also, wir haben ja das S jetzt noch.
So, genau, also.
Wir hatten S definiert als alle Knoten, die erreichbar sind von S aus
NGF.
Das heißt, es existiert keine Kante
Vw NGF mit V in S und W in T.
Wenn einer existieren würde, dann hätten wir sie im Prinzip da noch
hinzugefügt.
Das heißt, F von E ist C von E für alle Kanten, die über diese Menge
hier hinaus gehen.
Hier steht ein Kreuz.
Und gleichzeitig muss F von E gleich 0 sein für alle Rückwärtskanten
in T Kreuz S.
Das heißt, der Schnitt ist saturiert.
Und das heißt wiederum, dass F maximal ist.
Das haben wir eben gesehen.
So, was heißt das jetzt für uns?
Wir nehmen jetzt den Algorithmus von Fort Falkassen.
Wir nehmen den Algorithmus von Fort Falkassen, erhöhen da so lange
Pfade, bis es nicht mehr geht, definieren uns diese Menge S hier und
jetzt nochmal eine Preisfrage.
Wie konstruiere ich die Menge S?
Also, was steht hier nochmal?
F erreichbar von S in GF.
Wie macht man so einen Erreichbarkeitstest zwischen zwei Knoten?
Ja, okay.
Also, beantworte die Frage mal selber.
Also, was man im Prinzip machen kann, ist, man nimmt S, macht eine
Breitensuche, startet von S in GF aus.
Und alle Knoten, die von S erreicht werden durch diese Breitensuche,
werden in S reingepackt.
Und das heißt, mit dem Fort Falkassen Algorithmus, der im Prinzip
Flüsse löst, kann ich dann die Menge S konstruieren, die mir einen
minimalen Schnitt liefert.
Okay?
So.
Genau.
Und dann haben wir nochmal ein Lämmer.
Das sagt mir im Prinzip der Algorithmus von Fort Falkassen ist
korrekt.
Okay, also Beweis.
Na gut, also Fort Falkassen berechnet zulässigen Fluss.
Und zwar als Invariante.
Also, am Anfang ist es offensichtlich ein gültiger Fluss.
Wenn ich entlang eines Pfades entsprechender Höhe, bleibt es ein
gültiger Fluss.
Das heißt, am Ende kommt auch wieder ein gültiger Fluss raus.
Ganz einfaches Argument.
Weiter weiß ich, am Ende existiert kein erhöhender Pfad.
Genau, weiter wissen wir, dass für alle UV in E geschnitten S kreuz T
gilt, dass die Residualkapazität UV f gleich Null ist.
Und das heißt, dass der Fluss in die andere Richtung gleich Null sein
muss.
Das heißt, S ist saturiert und beweist Maximalität.
Z So.
Und beweist die Maximalität von f.
So, und dann haben wir im Prinzip mit den Sachen, die wir vorher schon
gezeigt haben, haben wir eben dieses Theorem.
Der Wert eines STmaxflows
gleicht der Kapazität Kapazität eines
minimalen ST-Schnittes.
So.
Gibt es Fragen dazu?
Genau.
Als nächstes schauen wir uns jetzt an zwei schlechte Beispiele für
Vorfallkassen.
Wir haben schon herausgefunden, ja, die Komplexität von dem
Algorithmus ist O von M mal den Wert von dem Fluss.
Okay.
Was ist der Wert von dem Fluss hier?
Na gut, der Wert von dem Fluss ist hier, 100 drüberschieben.
Da 100 drüberschieben.
Das heißt, der Wert des Flusses ist in der Tat 200.
Jetzt kann ich hier den erhöhenden Pfad drüberschieben.
Also ich sehe hier einen augmentierenden Pfad, der Kapazität 1 hat.
Erhöhe den Fluss entsprechend, kriege durch diesen Fluss, den ich über
diese Kante hier rübergeschoben habe, kriege ich im Residual-Netzwerk
die Rückwärtskante rein.
Das heißt, der nächste erhöhende Fluss kann eben wieder diese Kante
verwenden.
Und dann kriege ich wirklich einen Algorithmus, der hier die Worst
-Case -Laufzeit ausnutzt.
Genau.
Es geht noch schlechter.
Und jetzt kommt eben genau dieses kleine Detail, was ich vorher gesagt
habe ins Spiel.
Also vorher hatten wir Kapazitäten, die natürliche Zahlen waren.
Jetzt gehen wir davon aus, dass wir dieses Constraint droppen und auch
reellwertige Zahlen zulassen.
Zum Beispiel eben Kapazitäten wie Wurzel 5 minus 1 durch 2.
Und dann schauen wir uns dieses Netzwerk hier an und dazu diese
augmentierenden Pfade und stellen fest, und das dürft ihr einfach mal
nachreden, dass diese Sequenz von augmentierenden Pfaden hier eine
unendliche Sequenz von Flow Augmentations ist.
Und es wird noch schlimmer.
Der Wert des Flusses hier konvergiert nicht gegen den maximalen Wert.
Das heißt Fort Falkassen kann ich für Kapazitäten, die nicht
natürliche Zahlen sind, kann ich Fort Falkassen im Prinzip nicht
verwenden, weil das Ding nicht mehr konvergiert.
So.
Als nächstes, also jetzt haben wir im Prinzip abgeschlossen mit Fort
Falkassen.
Die Sachen, die wir gelernt haben, sind,
es gibt einen Algorithmus, der maximale Flüsse berechnet in O von M
mal den Wert von dem Fluss.
Und zwar so, dass er immer wieder nach Pfaden sucht, auf denen man den
Fluss erhöhen kann.
Das macht er so lange, bis der Fluss nicht mehr, also bis es keine
augmentierenden Pfade mehr gibt.
Und gleichzeitig haben wir gesehen, dass der Wert eines maximalen
Flusses gerade der Wert eines minimalen Schnittes ist.
Und wir haben gesehen, wie man aus diesem Fluss einen Schnitt
konstruieren kann, der eben genau diese Kapazität hat von dem
maximalen Fluss.
Also genau die Sachen, die man tatsächlich in der Praxis braucht.
Sowohl Fluss als auch Schnitt Dualität hergestellt und im Prinzip die
praktischen Sachen haben wir uns auch überlegt, wie man das machen
kann.
So.
Als nächstes gucken wir uns an Denix-Algorithmus an.
Genau.
Und dafür brauchen wir erstmal Also Denix-Algorithmus ist jetzt auch
noch ein zweiter
Algorithmus ein zweiter Algorithmus, um dieses Flussproblem zu lösen.
Und der möchte jetzt eben genau von dieser Eigenschaft weg, dass wir
den Wert des Flusses in der Komplexität drin haben.
Von dieser Eigenschaft möchten wir wegkommen und was haben, was
polynomial in M und N ist.
Deswegen gucken wir uns Denix-Algorithmus überhaupt an.
Als allererstes mal brauchen wir, was ist ein Blocking-Flow?
Und wir sagen, ein Fluss ist ein Blocking-Flow in einem Netzwerk H.
Und zwar dann, wenn für alle Pfade S nach T existiert immer immer eine
Kante in dem Pfad, die von der Kapazität her ausgeschöpft ist.
Also wenn wir uns ein Beispiel überlegen, haben wir S, zwei Knoten, T
hier Kanten, da Kanten, da Kanten, da Kanten, Kapazität Ich mal
erstmal alles hin.
Eins von eins.
Also was wir jetzt hier gemalt haben, ist die Kapazität auf der linken
Seite des Striches.
Hier C Strich Strich F.
Auf der rechten Seite der Wert des Flusses.
Und für jeden Pfad in diesem Netzwerk gilt jetzt offensichtlich, dass
immer eine Kante existiert, die blockiert.
Hier genau.
Blockiert heißt eben, dass der Wert des Flusses genau der Kapazität
entspricht.
Hier noch dieses Beispiel ein.
Diesen Pfad hier anschauen.
Dann existieren eben sogar mehrere Kanten, die dessen Wert des Flusses
genau die Kapazität ist.
Und das heißt umgangssprachlich nochmal, für jeden S T Pfad in H
existiert eine saturierte Kante.
Als nächstes brauchen wir Distance Labels.
Da werden wir gleich noch sehen, wozu die gut sind.
Distance Labels.
Also wir definieren mal eine Funktion V.
Definierte Funktion D von V in den natürlichen Zahlen n vereinigt die
0.
In Bezug auf die residualen Kapazitäten.
Also D ist eine Funktion von
the set of nodes into non negative integers.
Diese Funktion D nennen wir jetzt eben genau Distance Function.
Jetzt nennen wir D valid oder in Deutsch auch gültig.
In Bezug auf eine Funktion F.
Also in Bezug auf einen Fluss F.
Und zwar genau dann, wenn erstens A der Wert von dieser
Distanzfunktion im Konnoten T ist 0 und B für alle Distanzen gilt
folgendes.
V plus 1 für alle U, V in G, F.
Das heißt, je weiter wir im Prinzip von unserem von unserer Senke
weggehen, desto größer müssen nachher diese Distanzen werden.
Also für jede Kante hier muss diese Gleichung gelten.
So.
Jetzt haben wir zwei Eigenschaften.
Erste Eigenschaft, wenn diese Distanzlabels
gültig sind,
dann ist dieses D von U eine untere Schranke für die kürzeste
Wegedistanz von U nach D.
Und zwar im Residual Netzwerk.
Residual...
Eigenschaft 2, auch wichtig.
Wenn D von S größer gleich N ist, dann existiert kein Fahrt von S nach
T in G von F.
S nach T in G, F.
Und warum gilt das?
Offensichtlich mit der ersten Eigenschaft, die wir gesagt haben, dass
D von U eine untere Schranke für die kürzeste Wegedistanz von U nach T
ist.
Wenn dieses D von S hier größer gleich N ist, dann kann es
offensichtlich keinen Weg mehr geben in dem Residual Netzwerk, weil
ein kürzester Weg hätte höchstens Länge N minus 1.
Wir haben hier keine Kantengewichte.
So.
Die Frage war, ob bei der Gültigkeit dieses plus 1 auf der falschen
Seite steht.
Lass uns mal zusammen überlegen.
Wir haben gesagt, okay, für die Distanz für die Senke selber soll das
Ding 0 sein und je weiter ich von der Senke wegkomme, desto größer
müssen die Distanzlabels werden.
Das heißt, wenn ich hier mal reinmale, ich habe hier T, ich habe
irgendwelche Kanten in T da rein und das ist jetzt eine Kante in T
hinein, dann steht hier im Prinzip das T und hier steht irgendein
anderer Knoten.
Das heißt, hier steht 0 und da steht dann kleiner gleich 1.
Ist ja offensichtlich kein Problem, oder?
Also ich bin noch nicht dabei zu sagen, die Dinger sind exakt.
Das definiere ich gleich erst.
Aber trotzdem ist es ja eine untere Schranke für die kürzeste
Wegedistanz.
Kannst du ein bisschen lauter sprechen?
Genau.
Also die Frage war, die Labels könnten so erstmal alle 0 sein.
Genau, richtig.
Die Labels könnten alle 0 sein.
Ist ja damit auch eine untere Schranke für die kürzeste Wegedistanz.
Genau.
So.
Und jetzt kommt aber ein wichtiges Konzept.
Wir haben jetzt erst gesagt, wann sind diese Distanzfunktionen gültig
und jetzt sagen wir, wann sind Distanzfunktionen exakt.
Also, Distanzlabels
Distanzlabels sind exakt, wenn
wenn D von U eben genau die Länge des kürzesten Weges von U nach T im
Residualnetzwerk ist.
Genau die Länge des kürzesten Weges im Residual Netzwerk ist.
So.
Und jetzt ist die nächste Frage, also erstmal definieren wir uns das
jetzt so.
Die Dinge heißen einfach exakt, wenn D von U eben genau die Länge des
kürzesten Weges im Residualnetzwerk ist.
Von U nach T.
Also von U nach T.
So.
Und jetzt ist die nächste Frage, wie berechnet man sowas?
Na gut.
Finde exakte Distanzlabels
einfach mit einer Rückwärtsbreitensuche im Residualnetzwerk.
Rückwärts BFS im Residual Netzwerk.
Das heißt, was kriegen wir damit?
Laufzeit U von M.
Okay, das heißt, gucken wir uns das nochmal an.
Ich habe hier den Knoten T, jetzt mache ich eine Rückwärtsbreitensuche
und kann damit natürlich explizit die Distanzlabels so bestimmen, dass
sie exakt sind.
So.
Als nächstes brauchen wir, bevor ich den Algorithmus jetzt tatsächlich
auflege, brauchen wir eine Definition von einem Layered Network.
Gucken wir uns das mal an.
Layered Network LF.
Na gut, wir sagen als allererstes mal bestimme exakte Distancelabels
Distanzlabels eben mit dieser Rückwärtsbreitensuche und jetzt sagen
wir, dieses Layered Network LF ist definiert als Knotenlänge vom
Originalgrafen und dann müssen wir uns überlegen, wie sehen die Kanten
aus.
Das sind die Kanten im Residual Grafen, die die von U gleich die von V
plus 1 haben.
Und was heißt das jetzt für uns?
Wir haben jetzt gesagt, die Kanten von diesem Layered Network sind
genau die Kanten im Residual Netzwerk, mit denen ich im Prinzip eins
näher an das Ziel herankomme, an T.
Das heißt, dieses Layered Network hier enthält nur die kürzeste Fade
im Residual Netzwerk.
Also Beobachtung.
Beobachtung.
Jeder ST-Pfad in LF ist kürzester Pfad in GF.
Ziemlich offensichtlich.
Also mit jeder Kante, die ich in dem Layered Network benutze, komme
ich eins näher ran ans Ziel, eben weil das exakte Distanzlabels sind.
So und jetzt ganz grob.
Was macht DNS-Algorithmus?
Wir gucken uns gleich noch den Code von DNS-Algorithmus an.
DNS-Algorithmus macht jetzt folgendes.
Berechne.
Also DNS-Algorithmus berechnet
blockierenden Fluss in LF.
Den nennen wir jetzt FB.
Und setzt F ist gleich FB.
Also DNS-Algorithmus berechnet erstmal exakte Distanzlabels, berechnet
dann das Layered Network, berechnet den blockierenden Fluss in diesem
Layered Network und setzt dann eben den neuen Fluss F plus den Fluss,
den wir da gerade berechnet haben.
Die nächste Frage ist, ja, wie geht das?
Wie berechne ich diesen blockierenden Fluss?
So.
Also.
Folien 2.0.
Oder Moment, bevor ich das jetzt mache.
Schauen wir hier noch einmal kurz drauf.
Also hier nochmal der Gesamtüberblick von DNS-Algorithmus.
Solange ein Pfad im Residualnetzwerk existiert, berechne exakte
Distanzlabels, das ist das Teil hier mit einer rückwärtsbreiten Suche
im Residualnetzwerk, bestimme dieses Layered Network, berechne
Blocking Flow und dann erhöhe den entsprechenden Fluss um den Wert des
Blocking Flows.
So.
Und jetzt die Frage, wie
berechnet man den Blocking Flow?
Was der Algorithmus hier macht, das sieht erstmal ein bisschen
kompliziert aus, ist aber nichts anderes als schon wieder mal eine
Tiefensuche.
Wir haben während der ganzen Laufzeit von dem Algorithmus haben wir
einen Pfad und dieser Pfad soll im Prinzip am Ende einen ST-Pfad sein
und wenn wir einen ST-Pfad gefunden haben, dann erweitern wir unseren
entsprechenden Blocking Flow damit.
Okay, wie funktioniert das?
Als allererstes mal schauen wir uns den letzten Knoten auf dem Pfad an
und haben dann mehrere Fälle, nämlich 1, 2, 3, 4 Fälle.
Der erste Fall, den nennen wir Breakthrough, ist wenn der letzte
Knoten auf meinem Pfad eben der Zielknoten ist.
Das heißt im Prinzip der Pfad, den ich gefunden habe, ist bereits ein
ST -Pfad, das heißt mit dem muss ich irgendwas machen.
Was mache ich jetzt?
Ich bestimme meinen Delta, dass eben genau diese Kapazität ist, die
hier steht.
Und dann sage ich okay, für jede Kante in diesem Pfad erhöhe ich den
Blocking Flow um den Wert Delta und wenn danach die Kante komplett
ausgeschöpft ist, dann entferne ich sie aus dem Residualgraphen.
Insbesondere muss am Ende wenigstens eine Kante existieren, die aus
der Kantenmenge hier entfernt wird.
Also nicht aus dem Residualgraphen, sondern aus meiner Kantenmenge von
dem Layout-Network.
Der zweite Fall ist, der letzte Knoten ist eben nicht T, dann versuche
ich irgendwie den Pfad zu erweitern mit irgendeiner Kante, die noch in
dem Graphen existiert und füge sie an den Pfad heran.
Wenn das nicht möglich ist, das heißt es existiert keine ausgehende
Kante, na gut, dann muss ich offensichtlich irgendwie was anderes
machen.
Das sind genau diese zwei Fälle.
Im ersten Fall ist der Knoten V gleich S, das heißt es existiert keine
ausgehende Kante mehr vom Knoten S.
Dann bin ich offensichtlich fertig, dann kann kein weiterer Pfad mehr
existieren.
Und der letzte Fall ist, na gut, ich bin in den Knoten reingelaufen,
der der, sagen wir mal der da, der keine ausgehende Kante mehr hat,
dann muss ich offensichtlich zurückgehen.
Und zurückgehen heißt, entferne die Kante aus dem Pfad und auch aus
dem Netzwerk E.
Okay, also gucken wir uns das Beispiel nochmal an.
Auf den Folien...
Genau, also hier werden eben Extent-Operationen aufgerufen, die den
Pfad immer weiter ausbauen.
Wenn das der Fall ist, dann wird eben die Kapazität entsprechend
reduziert.
Und die entsprechende Kante dann, die entsprechenden Kanten hier
werden aus dem Netzwerk entfernt.
Hier haben wir festgestellt, okay, hier kommen wir nicht mehr weiter.
Das heißt, wir machen eine Retreat-Operation, machen den Pfad ein
bisschen kleiner, extenden, kommen irgendwann wieder am Ende ran,
erweitern den Fluss um die entsprechenden Werte und dann stellen wir
irgendwann fest, okay, hier komme ich gar nicht mehr weg und dann bin
ich fertig.
Okay, wie teuer ist das?
Das machen wir auch nochmal auf der Dokumentenkamera.
Okay, also okay, wie teuer ist dieser Algorithmus?
Wir haben hier oben den Algorithmus, wir haben hier den Breakthrough
-File, Extend und Retreat.
Okay, das erste Ding hier, ja, die Laufzeit ist offensichtlich die
Anzahl Extents, Anzahl Retreats plus n mal Breakthroughs.
Genau, also dieses n mal Breakthroughs kommt im Wesentlichen dadurch
zustande, dass die maximale Pfadlänge, die ich da habe, eben durch n
beschränkt ist, das heißt, ich kriege n Breakthroughs.
Die Anzahl Retreats, auch offensichtlich, das ist der zweite Fall,
Anzahl Extents ist der Fall und das heißt, die Laufzeit ist
offensichtlich so.
Jetzt ist die Frage, kann ich die Breakthroughs irgendwie abschätzen?
Na gut, ich weiß, dass ich höchstens m Breakthroughs habe, weil mit
jedem Breakthrough wird eine Kante saturiert und eine Kante aus dem
Graph entfernt.
Weiter weiß ich, dass ich höchstens m Retreats habe, auch hier, weil
dieses Retreat eben eine Kante aus dem Graph entfernt.
Und weiter weiß ich, die Anzahl Extents, die ist eben beschränkt durch
die Anzahl Retreats plus n mal die Anzahl Breakthroughs, weil eben ein
Retreat ein Extent cancelt, also wir hatten ein Extent hier und ein
Retreat geht eben zurück, geht eben zurück auf diesem Pfad und ein
Breakthrough cancelt höchstens n Extents, das heißt, wir kriegen
dieses n mal Breakthroughs dahin und das führt dann insgesamt zu einer
Laufzeit von O von n mal m für diese Blocking Flows.
Okay,
so die zweite Beobachtung, die wir jetzt machen, ist ich habe einen
Graph, mit dem alle Kapazitäten gleich sind, zum Beispiel eins, ja,
dann ist es so, dass ein Breakthrough eben alle Kanten auf diesem Pfad
saturiert und dann kommt man eben zu amortisierter konstanter Laufzeit
pro Kante.
Kann man sich leicht überlegen.
Das zweite, wo wir nicht genau hinschauen, ja, es gibt Dynamic Trees,
auch da ist Tarjan, glaube ich, wieder mit involviert.
Die sorgen dafür, dass man Breakthroughs, Retreats und Extents alle in
O von log n implementieren kann, das heißt, man kommt hier auf eine
Laufzeit von O von m plus n mal log n.
Aber es ist tatsächlich so, dass es in der Theorie hier schneller
aussieht, in der Praxis scheint es aber irgendwie langsamer zu sein.
So, jetzt gibt es noch was, was wir nicht beweisen, und was hier
steht, ist im Wesentlichen, das Distanzlabel von dem Knoten S erhöht
sich in jeder Runde um mindestens eins.
Und das heißt wiederum, dass wir maximal n Runden haben, bevor Dienitz
-Algorithmus konvergiert.
Das ist genau der erste Punkt hier, kleiner gleich n Runden, das
heißt, wir haben insgesamt O von m mal n Zeit pro Runde, das heißt,
wir haben insgesamt einen Algorithmus, der m mal n Quadrat ist,
beziehungsweise m mal n mal log n für dynamische, dynamische Bäume
verwendet.
Genau.
Und das war im Prinzip das, was wir für heute machen.
Den Rest drücke ich jetzt nicht mehr durch.
Das heißt, wir sehen uns morgen wieder und genau, schönen Feierabend.