Was wir heute im Prinzip machen werden, das hatte ich ja letzte Woche
schon angekündigt, ist, wir schauen uns einen Algorithmus an, mit dem
man starke Zusammenhangskomponenten tatsächlich berechnen kann.
Wir haben letzte Woche eine Anwendung gehabt, in dem man tatsächlich
diese starken Zusammenhangskomponenten braucht.
Und heute sehen wir, wie man sie tatsächlich in Linearzeit berechnet.
Wie wir es im Prinzip heute anstellen, was wir machen ist, wir machen
wir immer erstmal eine Wiederholung.
Dann gucken wir uns nochmal das Tiefensuchschema an, weil der
Algorithmus, den wir uns anschauen, ist tatsächlich eine Instanzierung
von dem Tiefensuchschema, von dem Algorithmus Tiefensuche.
Dann schauen wir uns sehr im Detail an, warum oder wie, also wir
schauen uns Invarianten an und schauen uns an, wie man einen
Algorithmus entwerfen kann, der diese Invarianten erhält.
Und dadurch kriegt man eben diesen Algorithmus, der in Linearzeit
diese SCCs nachher berechnet.
Und wie gerade eben gesagt, wir gucken uns es sehr, sehr stark im
Detail an.
Das mache ich alles auf dieser Dokumentenkamera, wie schon so öfter.
Und danach gehen wir im Prinzip nochmal, also machen wir kurz Pause
und dann gehen wir nochmal über die Folien drüber und dann sehen wir
nochmal die globale Sicht und sehen im Prinzip, wie schön dieser
Algorithmus ist.
Für mich ist es so, das ist ein Algorithmus, dem muss man tatsächlich
einmal komplett durchdacht haben und auf einmal ist er einfach.
Auf einmal gibt es da überhaupt nichts mehr, was schwierig ist und das
macht den Algorithmus irgendwie spannend.
Okay, so viel zur Struktur.
Okay, also wie im Prinzip jede Woche fangen wir an mit Wiederholung.
Also was haben wir letzte Woche gemacht?
Wir haben erstmal uns überlegt, was verstehen wir überhaupt unter
einer starken Zusammenhangskomponente?
Und dafür haben wir uns diese Relation hier angeschaut, die im Prinzip
sagt, zwei Knoten, u und v, stehen in der Relation, wenn ein Pfad von
u nach v in dem Graphen existiert und gleichzeitig ein Pfad von v nach
u.
Und haben dann gesagt, diese Relation, die wir da haben, ist eine
Äquivalenzrelation.
Und dann habe ich euch gesagt, ja, rechnet das einfach mal nach und
also die Eigenschaften von einer Äquivalenzrelation und das ist
ziemlich einfach.
So und diese Äquivalenzklassen, die sich dadurch ergeben,
haben wir dann gesagt, das nennen wir starke Zusammenhangskomponenten.
Dann haben wir ein Konzept definiert, was wir später auch nochmal
brauchen, nämlich den sogenannten Schrumpfgraphen.
Und dieser Schrumpfgraph, die cs, ist jetzt nichts anderes als eine
Knotenmenge und eine Kantenmenge, wobei dieses vs jetzt nichts anderes
sind als, also die Knoten hier, die wir haben, sind nichts anderes als
die sccs von dc.
Und wir haben Kanten in diesem Schrumpfgraf, cd in ecs per Definition,
genau dann, wenn eine Kante in dem Originalgrafen existiert.
cd in ec mit c in c und d in d.
Genau, das heißt im Prinzip, wenn ich mir einen Graph überlege, in dem
diese runden Boppel, die hier mal die Komponenten sind, dann ist der
Schrumpfgraf nichts anderes als, ich ziehe alle diese starken
Zusammenhangskomponenten zu einem Knoten zusammen und wenn da vorher
irgendwo eine Kante zwischen verlief, dann mache ich die auch in den
Schrumpfgrafen rein.
Also das Ding könnte jetzt ja mehrere Knoten haben, hier noch eine
Kante dazu und da noch ein paar Knoten, dann ist der Schrumpfgraf
nichts anderes als diese drei Knoten hier mit den Kanten dazwischen.
Also auch relativ einfaches Konzept.
Und dann haben wir gezeigt, mit einer ganz einfachen Überlegung, dass
dieser Schrumpfgraf gc-azyklisch ist.
Und wenn man das jetzt nochmal umgangssprachlich beschreibt, wenn wir
annehmen, da wäre irgendwo noch ein Kreis drin in diesem
Schrumpfgrafen, dann heißt das im Prinzip, dass vorher in dem
Originalgrafen Knoten existieren, die zu einem Kreis in dem
Originalgrafen führen.
Und das heißt dann wiederum, dass die Komponenten, die auf dem Kreis
liegen würden, im Prinzip in einer Komponente sind und das wäre ein
Widerspruch.
So, dann haben wir uns angeschaut, Kreise mit Gewicht 0 und haben
gesagt, okay, was ist das überhaupt?
Also wir haben gesagt, wir haben eine Instanz, das ist ein Graf mit
Knoten und Kanten und einer Kostenfunktion auf den Kanten.
Also reellwertig, das heißt positiv, negativ oder null.
Und dann haben wir gesagt, wir brauchen erstmal den Kreis V1 bis Vk.
Und der letzte ist eben wieder der Anfangsknoten.
Und dann haben wir gesagt, okay, Zero-Weight-Cycle-Detection, nichts
anderes als die Frage, existiert ein Kreis K mit C von K gleich 0,
wobei dieses C von K gerade definiert ist als die Summe der
Kantengewichte, die auf diesem Kreis liegen.
Ganz kanonisch, straight forward, keine Magie oder irgendwas.
C von EI.
Okay, also das ist Zero-Weight-Cycle-Detection und dann haben wir als
allererstes uns mal kurz überlegt, mit einer ganz einfachen Reduktion,
das ist allgemeine Problem, wenn man also wirklich keine weiteren
Anforderungen an die Kostenfunktion und an den Grafen hat, ist das
allgemeine Problem NP-hard, also NP-vollständig.
Und dann haben wir das Problem ein bisschen vereinfacht und haben
negative Kreise ausgeschlossen und haben uns dann überlegt, wie kann
man einen Algorithmus angeben, der uns einen zufälligen Gewicht
Nullkreis ausgibt, wenn einer existiert.
Und das ist irgendwie so ein ziemlich, also für mich ist es halt ein
ziemlich cooles Beispiel, wo man sieht, wo hier die Kombinatorik in
den Optimierungsproblem herkommt.
Wenn ich diese negativen Kreise habe, dann habe ich im Prinzip ein
Element, mit dem ich Sachen zusammenpuzzeln kann.
Und wenn ich diese ausschließe, dann habe ich es nicht mehr.
Und da geht genau diese Kombinatorik verloren und deswegen führt das
Ausschließen von negativen Kreisen hier zu einem schwächeren Problem,
also zu einem Problem, was auf einmal im Polynomialzettel lösbar ist.
Okay, wie haben wir das gesagt?
Also erstmal nochmal hinschreiben hier.
Negative Kreise ausschließen.
Ausschließen.
Und was haben wir gemacht?
Wir haben erstmal gesagt, okay, wir überrechnen wieder Potenziale.
Und zwar haben wir uns zu dem Graph G, also zu unserer Instanz G,
wieder einen Hilfsgraph definiert mit einem zusätzlichen Knoten S.
Hier ist ein L-Hilfsknoten.
Dieser Hilfsknoten wird im Prinzip mit allen Knoten in dem Graphen G
verbunden, dessen Kantengewicht hier ist 0.
Jetzt führen wir einmal Bellman-Ford aus und kriegen dadurch wieder
kürzeste Wegedistanzen von S nach V für alle Knoten V und G.
Und genau diese kürzesten Wegedistanzen haben wir dann wieder als
Potenziale definiert.
Also Potenzial von dem Knoten V haben wir definiert als genau diese
kürzeste Wegedistanz.
Dann hatten wir, wie auch vorher schon bei dem All-Pairs-Shortest-Path
-Problem gesagt, okay, wir modifizieren die Kantengewichte.
Haben gesagt, okay, das ist im Prinzip genau das alte Kantengewicht
plus das Potenzial von U minus das Potenzial von V.
Wobei, muss man das hier auch noch reinschreiben, E gerade die Kante
UV ist.
Und dann haben wir gesehen, okay, dieses neue Kantengewicht hier ist
erstmal größer gleich 0.
Wir haben außerdem gezeigt, dass Kreise unter der modifizierten
Kostenfunktion genau das gleiche Gewicht haben.
Das heißt, im Prinzip können wir die Gewicht-Null-Kreise in dem
Graphen finden, der die modifizierten Kostenfunktionen verwendet.
Also Suche-Kreis K mit c2 von K gleich 0.
Und jetzt hatten wir noch eine weitere Überlegung.
Dadurch, dass eben diese modifizierte Kostenfunktion größer gleich 0
ist und wir in dem modifizierten Modell Gewicht-Null-Kreise finden
können, können wir Kanten rausschmeißen, die ein Gewicht größer als 0
haben.
Also bald eine Kante mit Gewicht größer als 0 dabei ist, führt die
dazu, dass der Kreis ein Gewicht hat, was größer als 0 ist.
Und damit kann es kein Gewicht-Null-Kreis mehr sein.
Also schmeißen wir diese ganzen Kanten raus.
Entferne Kanten mit c2 von E größer 0.
Und was wir dann machen ist, SCCs berechnen.
Berechne SCCs.
Und damit haben wir gesehen, wenn eine SCC existiert mit mehr als
einem Knoten, dann wissen wir schon, es existiert ein K-Kreis mit c
von K gleich 0.
Diese starken Zusammenhangskomponenten ist ja genau diese Eigenschaft.
Für ein paar von Knoten kann ich auf der einen Seite von U nach V
laufen mit einem Pfad, auf der anderen Seite mit einem anderen Pfad
wieder zurück und damit kriege ich einen Kreis.
Und wenn ich in diesem modifizierten Graph eine starke
Zusammenhangskomponente habe, die mehr als einen Knoten hat, dann
heißt das, ich habe erstens einen Kreis und zweitens weiß ich, dass
alle diese Kreise, also alle die Gewichte, die die Kanten des Kreises
haben, dass die im Prinzip alle 0 sein müssen, weil die anderen
Kantengewichte habe ich ja Also wenn wir wirklich tatsächlich einen
Kreis mit Gewicht 0 ausgeben möchten, dann machen wir einfach einen
Random Walk in einer zufälligen SCC.
Und dieser Random Walk, das können wir auch nochmal kurz im Bild
zumalen, dieser Random Walker, nehmen wir mal an, wir hätten jetzt
hier so eine SCC, der macht nichts anderes als im Prinzip ist das so
eine kleine Person, die auf einem starken Knoten hier steht und in
jeder Iteration sucht die sich von seinen Nachbarn einen zufälligen
Nachbarn aus, Uniformen gleich verteilt, springt zu diesem Nachbarn.
In der nächsten Iteration macht der Random Walker wieder genau das
gleiche, sucht sich den nächsten zufälligen Nachbarn in dieser SCC und
dann dadurch, dass eben diese SCC endlich viele Knoten enthält, weiß
ich nach endlich vielen Schritten, muss ich irgendwie auf einen Knoten
gesprungen sein, den ich schon mal gesehen habe.
Das heißt, ich komme irgendwie dazu, wenn das hier mein Random Walker
ist, dass ich auf einen Knoten springe in der SCC, auf dem ich schon
mal war.
Und das heißt aber wiederum, dass ich diese Parent Pointer hier im
Prinzip verfolgen kann oder rückwärts, wie man das auch immer gerade
speichert.
Und dann kann ich diesen Kreis ausgeben.
Okay, gibt es Fragen?
Man kann es natürlich auch deterministisch machen, aber das Ziel, was
ich jetzt gerade irgendwie versucht habe, kurz darzulegen, ist einen
zufälligen Gewicht Nullkreis auszugeben.
Ich will nicht deterministisch ausgeben, sondern ich will einen
zufällig und gleich verteilt unter allen Gewicht Nullkreisen, die es
dort gibt.
Also ich muss die Frage nochmal sagen, warum macht man das nicht
deterministisch, war die Frage.
Sonst noch Fragen?
Ja, vielleicht Gegenfrage, was würdest du denn deterministisch machen?
Also die Antwort war irgendwie, ich nehme den Knoten und gehe halt
rum.
Die Frage ist, warum denkst du, dass du irgendwann einen Algorithmus
hast, der terminiert?
Ja, aber wenn du irgendwie rumgehst, dann bist du ja ziemlich planlos.
Wahrscheinlich müsste man es nochmal ein bisschen genauer formulieren,
aber so funktioniert es auf jeden Fall.
Okay, genau.
Also, was wir jetzt wie gesagt machen ist, wir gucken uns an, wie
berechne ich tatsächlich diese SCCs und wie geht es in die Nährzeit.
Und das kostet uns den Großteil der Vorlesung heute.
Als allererstes nochmal zur Wiederholung das Tiefensuchschema.
Wer kennt das noch?
Oder fangen wir andersrum, wer kennt es nicht mehr?
Ich kenne im Prinzip alle.
Also dieses Schema hier, das werden wir gleich nochmal brauchen und
wir werden da auch ziemlich ins Detail nochmal gehen an den Stellen,
wo wir den Algorithmus modifizieren oder wie wir die bestimmten
Methoden hier instanziieren, um dann tatsächlich SCCs zu berechnen.
Was wir jetzt machen ist, als allererstes mal, wir brauchen für Knoten
eine Notation, beziehungsweise wir müssen Knoten markieren.
Also es gibt zwei Zustände von Knoten, entweder ein Knoten ist
markiert oder er ist eben nicht markiert.
Dann rufen wir in diesem Tiefensuchschema erstmal eine Init-Funktion
aus, nachdem wir diese Knoten ja alle unmarkiert haben und dann gucken
wir für jeden Knoten in unserem Graphen, ja ist dieser Knoten schon
markiert?
Und wenn er nicht markiert ist, dann markieren wir den Knoten und
führen eine Funktion aus Root von S, die uns im Prinzip sagt, ok
erzeuge hier einen neuen DFS-Baum, der genau an S gerootet ist.
Und dann führen wir diese Funktion DFS von S,S aus, was im Prinzip
diese Funktion hier ist.
Und diese Funktion DFS macht jetzt nichts anderes, als eben diese
Tiefensuche von dem Knoten S auszustarten.
So, was macht jetzt diese Tiefensuche?
Die Tiefensuche geht, wie der Name schon sagt, beim Explorieren des
Graphen erstmal in die Tiefe.
Das heißt, wir schauen uns hier alle Kanten ausgehend von dem Knoten V
an.
Also hier das Eingabepaar ist U und V.
Jetzt gucken wir uns alle ausgehenden Kanten von dem Knoten V an, mit
Endpunkt W.
Und jetzt gibt es zwei Fälle.
Entweder der Endpunkt ist schon markiert.
Wenn dieser Knoten schon markiert ist, dann ist es so, dass unsere
Tiefensuche den Knoten ja vorher schon mal gesehen hat.
Sonst wäre er nicht markiert.
Das heißt, die Kante, die wir da explorieren, ist keine Baumkante.
Die Baumkanten sind immer die Kanten, die die Tiefensuche als erstes
exploriert.
Und dadurch, dass es eben keine Baumkante ist, wird eine Funktion
aufgerufen, die sagt, ok, traversiere non-tree-edge.
Und im anderen Fall ist es eben eine Baumkante, dann wird eine andere
Funktion aufgerufen, die sagt, ok, traversiere eine Baumkante,
markiere den Knoten und dann mache dort weiter.
Und hier ist genau der springende Punkt, hier geht das Ding in die
Tiefe.
Wenn ich eine Baumkante gefunden habe, dann gehe ich tatsächlich
weiter in die Tiefe zur nächsten Baumkante.
Und dann gibt es noch eine Funktion, die heißt backtrack von U und V,
die im Prinzip sagt, tu irgendwas, wenn ich aus meiner Rekursion
zurückkomme.
Wenn ich alle Baumkanten und Nichtbaumkanten unterhalb meines
aktuellen Knoten traversiert habe, dann rufe ich diese Funktion
backtrack auf und die macht dann wieder was.
Das ist jetzt ein allgemeines Schema, deswegen steht da
Tiefensuchschema und nicht Tiefensuche.
Und diese Funktionen hier, traverse non-tree-edge, traverse tree-edge,
backtrack und root, das sind genau die Funktionen, die wir nachher
instanziieren werden, um den Algorithmus zu kriegen für die SCCs.
Jetzt ist es bei Tiefensuche normalerweise so, dass man Sachen
berechnen kann, wie zum Beispiel so etwas wie eine DFS-Nummer.
Am Anfang sagen wir diese DFS-Nummer oder DFS-Position, das ist 1.
Dann setzen wir, wenn wir diesen Root-Knoten hier, diese Root-Funktion
haben, dann sagen wir, die DFS-Nummer von dem Knoten ist die aktuelle
Nummer und danach wird das Ding inkrementiert.
Traverse tree-edge sagt auch wieder, die DFS-Nummer von dem neu
angeschalteten Knoten wird auf die aktuelle Nummer gesetzt und danach
wird das Ding inkrementiert.
Das heißt im Prinzip sagt uns diese DFS-Nummer, in welcher Reihenfolge
diese Knoten von der Tiefensuche das erste Mal gesehen wurden.
Wenn ich mir zwei Knoten anschaue, U und V, dann sagt mir das wie
gesagt, in welcher Reihenfolge die von der Tiefensuche exploriert
wurden.
Und dann definieren wir uns eine Relation, die brauchen wir später
nochmal.
Also U steht in Relation zu V, wenn eben die DFS-Nummer von U kleiner
ist als die DFS-Nummer von V.
Und dann, oh Wunder, da braucht man auch nicht viel zu wissen oder
viel zu sehen,
dass die Knoten auf dem Rekursionsstabel, wenn ich diese Tiefensuche
gerade ausführe, genau bezüglich dieser Relation sortiert sind.
Das liegt daran, dass das eben genau so gemacht ist hier.
Auf der anderen Seite kann ich eine Finishing Time definieren.
Die sagt mir im Prinzip, zu welchem Zeitpunkt wurde der Knoten
fertiggestellt.
Also was ist der Zeitpunkt, zu dem ich den Knoten fertig stelle.
Und hier auch wieder im Prinzip nichts Spezielles.
Wir haben diese Init-Funktion, da setzen wir Finish Time auf 1.
Und wenn ich diese Backtrack-Funktion Uv ausführe, das heißt, wenn ich
aus der Rekursion rauskomme, dann setze ich die Finishing Time von dem
aktuellen Knoten auf den aktuellen Wert von Finishing Time und erhöhe
den Wert von Finishing Time danach um 1.
Das kennen wir schon.
Den Rest machen wir dann auf der Dokumentenkamera.
Also, schreiben wir mal hin.
Wir wollen jetzt starke Zusammenhangskomponenten.
Genau, also ich schreibe jetzt erstmal einen Algorithmus hin.
Und zwar, jetzt wissen wir auch, wo dieses GC herkommt, wollen wir im
Prinzip einen Graphen haben, der besteht aus den Knoten des Original
-Graphen und am Anfang sind die Kanten dieses Graphen leer.
Also am Anfang hat dieser Graph nicht eine einzige Kante.
Und jetzt sagen wir, okay, für jede Kante in E,
füge diese Kante zu meinem aktuellen, zu meinen Kanten EC hinzu.
Dann tun wir irgendwas.
Und was, das ist genau das, was wir im Prinzip jetzt im Laufe der
Vorlesung uns erarbeiten.
Und dann haben wir eine Invariante.
Und diese Invariante sagt, die SCCs von GC sind bekannt.
Genau, also das ist sozusagen der Blueprint erstmal für den
Algorithmus, den wir uns überlegen.
Wir wollen einen Algorithmus haben, der uns diesen Graphen hier
definiert und dann Stück für Stück Kanten hinzufügt, irgendwas macht
und dann die Invariante hat, okay, die SCCs von GC sind bekannt.
Jetzt haben wir zwei Sachen, die wir im Laufe der Vorlesung sehen
werden.
Das erste ist, wenn der Algorithmus fertig ist, dann stimmen diese
SCCs von GC eben mit den SCCs von Geber ein.
Was wir auch sehen werden ist, dass die Reihenfolge, in welche man
hier diese Kanten hinzufügt zum Graphen, dass es tatsächlich so, dass
es sehr wichtig ist, in welcher Reihenfolge man es tut.
Also der Algorithmus, den ich hier hingeschrieben habe, wenn ich
Kanten in zufällige Reihenfolge hinzufüge, dann ist kein Algorithmus
bekannt, der die SCCs damit effizient berechnet.
Wenn ich diese Kanten jetzt aber in eine Reihenfolge hinzufüge, die
der Explorationsreihenfolge von Tiefensuche entspricht, dann geht das
auf einmal effizient.
Und dann werden wir genau sehen, wo das hier im Prinzip effizient
geht.
So, das heißt, die erste Frage, die wir uns stellen.
Wie ändern sich die SCCs von GC und GCS?
Wobei das jetzt hier der Schrumpfgraph von diesem GC ist.
Wenn man eine Kante E zu GC hinzufügt.
So, wichtige Frage, ja?
Und jetzt gucken wir uns mal an, welche Fälle gibt es überhaupt?
Also wir haben jetzt drei Fälle.
Der erste Fall ist im Prinzip, beide Endpunkte dieser Kante,
beide Endpunkte von E, gehören zur selben SCC.
So, was passiert dann?
Also wie ändern sich die SCCs?
Weiß das jemand?
Kann mir das irgendjemand sagen?
Ja?
Genau, gar nicht.
Hervorragend.
Also, nichts passiert.
Triviale Frage.
Also ein Bonuspunkt für die Klausur.
Nichts passiert.
So, zweiter Fall.
E verbindet verschiedene SCCs.
Schließt aber keinen Kreis.
Okay, und in dem Fall, was passiert?
Na gut, dann haben wir eben eine neue Kante im Schrumpfgraphen.
Im Schrumpfgraphen GCS.
GCS.
Genau, also der Fall hier, E verbindet verschiedene SCCs.
Läuft also insbesondere zwischen zwei SCCs.
Schließt aber keinen Kreis.
Das heißt, die SCCs ändern sich offensichtlich nicht.
Aber in dem Schrumpfgraphen kommt eine Kante hinzu, falls vorher noch
keine da war.
So, und der dritte Fall.
E verbindet verschiedene SCCs.
Moment.
Schließt einen oder mehrere Kreise.
Mehrere Kreise.
So, und was muss man in dem Fall machen?
Klar ja, alle SCCs auf diesen Kreisen werden kollabiert.
So, jetzt mache ich noch ein kurzes Bild dahin.
Also wir haben im Prinzip hier unsere Struktur, die wir aktuell haben.
Hier eins, zwei, drei.
Der erste Fall, haben wir gesagt, die Kante verläuft innerhalb der
SCC.
Das ist der Fall A.
Also hier A.
Da passiert dann nichts mit den SCCs.
Der zweite Fall.
Na gut, wir haben jetzt hier zusätzlich eine Kante.
E.
Genau, in dem Fall ändert sich der Schrumpfgraf.
Schrumpfgraf erhält neue Kante.
Und im letzten Fall, wir haben hier schon irgendwelche Kanten
dazwischen.
Und fügen jetzt die neue Kante E hinzu.
Na gut, jetzt habe ich hier diesen Kreis geschlossen.
Das heißt, diese SCCs, die ich hier habe, die müssen tatsächlich
gemerged werden.
Okay.
So.
Jetzt wissen wir erstmal schon mal, was passiert mit den SCCs, wenn
ich Kanten hinzufüge.
Was unser Ziel jetzt ist, im Prinzip wollen wir einen effizienten
Algorithmus haben.
Und dafür brauchen wir eine Verwaltung für diese SCCs.
Wir benötigen SCC-Verwaltung.
Genau.
Und dann nochmal einmal Achtung.
Für zufällige Kantenreihenfolgen ist nichts Effizientes bekannt.
So.
Okay.
Also für zufällige Kantenreihenfolgen ist nichts bekannt.
Das heißt, wir wollen jetzt im Prinzip die Kantenreihenfolge von der
DFS verwenden.
Struktur.
Und unser grober Algorithmus sieht jetzt folgendermaßen aus.
Jetzt geht mein Stift alle.
Sieht jetzt folgendermaßen aus.
Also am Anfang wollen wir eine DFS erstmal verwenden.
Verwende DFS auf G.
Die Kanten EC sind genau die bisher explodierten Kanten.
Die Knoten VC definieren wir als bisher markierte Knoten.
So.
Und kleiner Tipp.
Dieses VC, das ist nicht die gleiche Knotenmenge wie in dem
Algorithmus, die wir hier oben definiert hatten.
Das sind zwei verschiedene Knotenmengen.
Hier haben wir die Knoten von dem ganzen Graphen und hier nur die
bisher markierten Knoten.
Okay.
So.
Und dann wollen wir im Prinzip...
Modifiziere...
Templatefunktionen...
Template...
Funktionen...
vom
Tiefensuchschema...
so dass die Invarianten im Algorithmus erfüllt sind.
Also das ist die grobe Struktur.
Was wir jetzt brauchen ist...
als allererstes mal ein bisschen Nomenklatur.
Also wir wollen jetzt bestimmten Knoten, bestimmten SCCs einen Namen
geben, so dass wir den Algorithmus gleich besser verstehen.
Also Nomenklatur.
Wir sagen jetzt, ein Knoten...
ein aktiver Knoten ist ein markierter Knoten.
Das heißt, die Tiefensuche hat den tatsächlich schon mal irgendwie
gesehen.
Aber...
nicht...
finisht.
Das heißt, ich habe auf diesem Knoten noch keinen Backtrack aufgerufen
insbesondere.
Also aktiver Knoten nochmal markiert, nicht finisht.
Jetzt gucken wir uns die Nomenklatur für SCCs von unserem GC an.
Und da gibt es dann eben SCCs, die haben wir noch nicht erreicht.
Noch nicht erreicht.
Genau, das sind im Prinzip einfach unmarkierte Knoten.
Dann gibt es offene SCCs.
Das sind...
SCCs, die aktive Knoten enthalten.
Enthält...
aktive Knoten.
Also insbesondere...
existieren Knoten in dieser SCC, die markiert sind, aber nicht
finisht.
Und damit ist diese SCC auch noch nicht fertig.
Deswegen nennt man sie offen.
Und man nennt die...
abgeschlossen.
Wenn alle Knoten in dieser SCC finisht sind.
Alle Knoten in SCC finisht.
Finisht.
Das heißt, wir führen später noch ein Array ein.
Das nennen wir Komponente.
Komponente von einem Knoten W.
Gibt den Repräsentanten einer SCC an.
Repräsentant...
einer SCC an.
Genau.
Und was ich mit Repräsentant meine...
Der Repräsentant...
Repräsentant...
Das ist im Prinzip der Knoten in der SCC, der die kleinste DFS Nummer
hat.
Also...
Knoten in...
SCC...
mit...
kleinster...
DFS Nummer.
So.
Und letzte Definition, die wir jetzt noch brauchen.
Wir sagen, ein Knoten...
Knoten von...
offenen bzw.
abgeschlossenen...
Komponenten...
heißen offen...
offen oder abgeschlossen.
So.
Also jetzt haben wir diese Nomenklatur hier.
Und was wir jetzt machen ist, wir schreiben drei Invarianten hin.
Und diese Invarianten...
werden im Prinzip dazu führen, dass wir nachher einen korrekten
Algorithmus haben.
Und dann bauen wir danach den Algorithmus Stück für Stück auf.
Zeigen, dass jede dieser Funktionen, also diese Instanzierung dieser
Funktionen...
in dem Tiefensuchschema diese Invarianten erhält.
Und werden dann irgendwie verstehen, okay, der Algorithmus macht das
Richtige.
Okay.
Also schreibe ich mal die...
schreibe ich mal die Invarianten hin.
Wo sind wir?
Also Invarianten...
Eigenschaften.
Also ich schreibe hier Schrägstrich Eigenschaften, weil wir...
diese Invarianten im Prinzip erst mit dem Algorithmus entwickeln...
und dann erst dabei sehen, warum diese Invarianten sinnvoll sind.
Also Invariante A...
Kanten...
von abgeschlossenen Knoten...
gehen zu abgeschlossenen Knoten.
So, Invariante B...
die offenen...
Komponenten...
S1 bis SK...
bilden...
einen Pfad...
in GCS.
So, und die dritte Invariante...
die Repräsentanten...
partitionieren die offenen Komponenten.
Hier nochmal kurz auf den Beamer.
Das sind eben genau diese drei Invarianten.
Und jetzt müsst ihr euch vorstellen, okay, ich starte hier irgendwo
eine Tiefensuche.
Das ist der aktuelle Knot von diesem...
in dieser Tiefensuche.
Und entlang des Pfades, die diese Tiefensuche gerade hat...
habe ich eben genau diese offenen Komponenten.
Die Repräsentanten sind immer die Knoten...
mit der kleinsten DFS-Nummer.
Das heißt, man kriegt durch diese Repräsentanten...
eben eine Partitionierung der offenen Komponenten.
Und gleichzeitig bilden diese offenen Komponenten...
wie man in dem Bild sieht, einen Pfad in dem Schrumpfgrafen.
Okay?
Fragen dazu erstmal?
Genau, also...
wir entwickeln nun...
einen Algorithmus...
der eben genau diese Invarianten erhält.
Invarianten...
erhält.
Und sehen im Prinzip, dass am Ende...
alle SCCs abgeschlossen sind.
Am Ende...
sind alle SCCs abgeschlossen.
Und...
mit dem nächsten Lemma, was ich jetzt gleich schreibe, sehen wir
dann...
im Prinzip, dass der Algorithmus...
korrekte SCCs berechnet.
Was sagt das Lemma?
Das Lemma sagt...
abgeschlossene...
SCCs...
von GC...
sind...
SCCs von G.
So.
Und dann sieht man hier direkt die Korrektheit.
Wenn am Ende alle SCCs abgeschlossen sind vom Algorithmus...
und ich dieses Lemma hier habe, das sagt...
abgeschlossene SCCs von GC sind SCCs von G...
dann weiß ich, ich habe alle SCCs von G gefunden.
Also gucken wir uns das Lemma kurz an.
Übrigens, diese Nomenklatur und die Invarianten...
die lege ich gleich nochmal auf, weil wir sie im Prinzip brauchen...
während ich die anderen Sachen nachher aufbaue.
Aber für das Lemma erstmal nicht.
Also...
V sei jetzt erstmal...
ein abgeschlossener Knoten.
Dann...
S sei mal eine SCC, sodass...
V in...
S ist.
Dann SC...
sei eine...
SCC in GC mit...
V in SC...
und W...
in S sei ein anderer Knoten.
Was wir jetzt zeigen müssen ist...
W...
W ist auch abgeschlossen...
und...
W ist in SC.
Ja, und dann habe ich eben genau, dass die abgeschlossenen...
SCCs von GC die SCCs von G sind.
Also...
Nehmen wir uns mal einen Kreis her.
Sei C...
ein Kreis...
in G...
durch V...
und W.
Mal ein kurzes Bild.
V, W...
Kreis.
Wir wissen...
Wir haben Invariante A...
und diese Invariante A, nochmal zur Wiederholung, sagt...
dass Kanten von abgeschlossenen Knoten gehen ausschließlich zu
abgeschlossenen Knoten.
Das heißt...
entlang dieses Pfades hier...
finde ich hauptsächlich abgeschlossene Knoten.
Also es gibt nur Kanten zu abgeschlossenen Knoten.
Und damit folgt insbesondere, dass...
dadurch eben alle Knoten in dem Kreis...
Knoten in C sind abgeschlossen.
Insbesondere W.
Also auch W.
Weiter weiß ich, dass...
abgeschlossene Knoten...
finished sind.
Das heißt, ich habe die Backtrack-Funktion schon aufgerufen.
Und Kanten aus finished Knoten wurden bereits exploriert.
Einfach, das ist die Definition DFS.
Definition DFS...
Kanten aus...
finished Knoten...
wurden...
bereits...
exploriert.
Genau.
Das heißt aber, dass...
alle...
Knoten von...
C in GC bereits drin sind.
Und damit folgt dann, dadurch dass wir eben den Kreis haben...
das W in diesem SC ist.
Genau.
Und das war's.
Gibt es Fragen dazu?
Wie gesagt, wir machen jetzt erstmal die ganzen Details...
und am Ende gucken wir uns das Ganze nochmal von oben drauf an...
und dann hat man nochmal einen guten Überblick.
Was wir uns als nächstes jetzt überlegen...
ist, wie repräsentieren wir die offenen Komponenten...
und wie repräsentieren wir die Repräsentanten...
während unserer Tiefensuche.
Schauen wir mal, ob wir das hier irgendwo so hinlegen können.
Repräsentation...
von offenen Komponenten.
Was wir jetzt haben wollen, ist im Prinzip einfach zwei Stapel...
einmal mit offenen Knoten.
Die Dinger nennen wir O-Notes.
Und einmal von offenen Repräsentanten.
Und das nennen wir O-Reps.
Und es ist nicht schwer zu sehen...
oder was wir gleich sehen werden...
ist, dass diese Knoten auf diesen Stapeln hier...
ebenfalls sortiert sind nach ihrer DFS-Nummer.
Und jetzt wird es spannend.
Jetzt gucken wir uns im Prinzip die ganzen einzelnen Funktionen...
von dieser Tiefensuche an und überlegen uns genau...
was mache ich mit diesen beiden Stapeln...
und warum erfüllen wir immer noch die Invarianten.
Also am Anfang...
füllen wir diese Init-Funktion aus.
Was wir da machen, ist nichts anderes als...
oder was wir wissen, kein Knoten ist markiert.
Also am Anfang diese Init-Funktion...
und wir wissen ganz genau...
wir haben vorher alle Knoten unmarkiert.
Das heißt, es gibt im Prinzip keinen markierten Knoten.
Also kein Knoten ist markiert.
Gleichzeitig weiß ich, dass keine Kante traversiert wurde.
Keine Kante traversiert.
Und das heißt insbesondere, dass keine offene Komponente existiert.
Es existiert keine offene Komponente.
Aber gleichzeitig auch keine geschlossene.
Ich habe ja noch nichts gemacht.
Das heißt, unsere beiden Stacks...
O-Notes und O-Wraps...
die sind im Prinzip beide leer.
Da ist nichts drin.
Und damit ist offensichtlich...
dass alle Invarianten erfüllt sind.
Alle Invarianten...
Check.
So, jetzt gucken wir uns nochmal die Invarianten an.
Sieht man das alles hier drauf?
Kompliziert.
Ein Stück nach oben noch.
Kann von abgeschlossenen Knoten gehen zu abgeschlossenen Knoten?
Klar.
Wir haben keine abgeschlossenen Knoten.
Das heißt, diese Invariante ist erfüllt.
Offene Komponenten bilden Fahrt in GCS.
Wir haben keine offenen Komponenten.
Das heißt, die Invariante ist erfüllt.
Und das dritte Ding.
Repräsentanten präsentieren die offenen Komponenten bezüglich ihrer
DFS -Nummer.
Wieder das gleiche Argument.
Wir haben keine offenen Komponenten.
Das heißt, die Aussage da ist wahr.
So.
Nächster Schritt in unserer Tiefensuche ist diese Root-Funktion.
Da überlegen wir uns als nächstes, was wir für diese Root-Funktion
hier machen.
Also B.
Neuer Root-Knoten
wird markiert.
Gut, was passiert dann?
Als allererstes mal fällt uns auf, dass alle markierten Knoten
sind finisht.
Warum ist das so?
Wenn ich erstmal aus diesem Call hier draußen bin, dann habe ich für
alle Knoten, die ich angeschaut habe, diese Backtrack-Funktion
ausgeführt.
Und damit sind die Knoten ja finisht.
Wir erinnern uns, die Finishing-Time wird in der Backtrack-Funktion
gesetzt.
Das heißt, die Dinger sind dann gefinisht.
Und das heißt insbesondere, wenn ich in der nächsten Iteration diese
Root -Funktion aufrufe, dass alle Knoten, die ich bereits exploriert
habe, also markiert sind, finisht sind.
Weiter weiß ich, dass meine O-Notes, also meine offenen Knoten und
meine offenen Repräsentanten leer sind.
Es gibt ja keine offenen Knoten und damit auch keine offenen
Repräsentanten.
So, dann das Markieren von S.
Das erzeugt eine neue offene Komponente.
Neue offene Komponente.
Nehmen wir sie mal irgendwie so was wie S.
Das heißt, die In-Varianten, also erstmal überlegen wir uns als
nächstes ja, die In-Varianten sind wieder erfüllt.
Genau, also wir haben eine einzige offene Komponente.
Hier In-Variante A ist damit offensichtlich erfüllt, weil wir uns hier
nur abgeschlossene Knoten anschauen.
Offene Komponenten bilden einen Pfad in GC.
Wir haben eine einzelne offene Komponente.
Das heißt, das ist offensichtlich ein Pfad.
Und der dritte Punkt hier, Repräsentanten partitionieren die offenen
Komponenten bezüglich ihrer DFS-Nummer, ist auch offensichtlich klar.
Also ist auch offensichtlich richtig.
Was wir als nächstes noch machen ist, S wird zu
den offenen Knoten hinzugefügt und gleichzeitig auch zu den offenen
Repräsentanten hinzugefügt.
Okay, und damit sind wir mit der Root-Funktion hier fertig.
So, die nächste Funktion, die wir uns anschauen, ist jetzt als
allererstes mal dieses TraverseTreeEdge.
Ja, das ist der nächste Fall, den wir uns anschauen.
Was machen wir da?
Na gut, also Traversierung einer Baumkante
Baumkante, E gleich VW Also wir sind jetzt in dieser
in diesem tiefen Suchschema drin und schauen uns jetzt eine neue Kante
an, in der der Knoten W noch nicht markiert ist und dann heißt das,
dass wir im Prinzip diese Funktion TraverseTreeEdge aufrufen.
Was dann passiert ist, W wird markiert und eigene offene Komponente
eigene offene Komponente
Alle anderen Komponenten, die ich im Prinzip hier habe, die bleiben
unverändert.
Also ich füge einfach nur eine neue offene Komponente hinzu.
Alle anderen offenen Komponenten bleiben unverändert.
Okay, das heißt, wenn wir jetzt uns wieder an die Invarianten hier
denken Invariante A Gut, das ist offensichtlich.
Also ich habe ja keine neue abgeschlossene Komponente.
Das heißt, Kanten von abgeschlossenen Komponenten haben vorher nur zu
abgeschlossenen Komponenten gezeigt.
Das tun sie auch immer noch danach.
Weiter Achso, genau.
Also Invariante A erledigt.
Dann hatten wir den alten aktuellen Knoten das war V und der neue
aktuelle Knoten aktuelle Knoten das ist W Das heißt, was wir im
Prinzip jetzt machen müssen dadurch, dass wir auch gesagt haben W wird
markiert und eigene offene Komponente Wir müssen W zu O-Notes und O
-Wraps hinzufügen.
Jetzt überlegen wir uns, was passiert mit Invariante B Invariante B
Also Invariante B bleibt erhalten Und dann überlegen wir uns, warum
das so ist Naja gut, W wird ein offener Knoten beziehungsweise eine
offene Komponente Knoten-Komponente und zwar hat die die größte DFS
-Nummer mit
größter DFS-Nummer Und das heißt insbesondere, dass der aktuelle
Knoten erstens hier ganz hinten steht und zweitens, dass ich immer
noch einen Pfad in GC habe Also die offenen Komponenten bilden immer
noch einen Pfad in SC Das heißt, Invariante B bleibt mit dem, was wir
da tun erhalten
Und gleichzeitig, dadurch, dass eben die Komponente aus einem
einzelnen Knoten besteht und damit gleichzeitig den Repräsentanten hat
wissen wir, Invariante C bleibt erhalten
Okay, weiter im Text Was wir als nächstes machen wollen Ja genau, was
wir als nächstes machen wollen ist wir schauen uns jetzt an, was
passiert, wenn wir eine Nicht-Baumkante traversieren Also D
Traversiere Nicht-Baumkante
Nicht -Baumkante Nicht-Baumkante E gleich VE
Also, dann gibt es im Prinzip mehrere Fälle Moment
Also schauen wir uns die Fälle mal an Wenn der Knoten, den ich mir da
gerade anschaue nicht in den offenen Knoten ist in den offenen Knoten
enthalten ist dann heißt das ja schon, okay, VE muss abgeschlossen
sein Und das heißt aber insbesondere dass sich die SCCs von GC durch
diese Kante, die wir da gerade haben nicht mehr ändert Ändert sich
nicht Und das gilt durch dieses Lemma, was wir vorhin gesagt haben Die
abgeschlossenen SCCs in GC sind eben schon SCCs in G Das heißt, wenn
der Knoten abgeschlossen ist dann kann sich die SCC nicht mehr ändern
Ist also nichts zu tun So, wenn der Knoten jetzt allerdings ein
offener Knoten ist Das heißt, er ist bereits in diesen offenen Knoten
hier enthalten Dann heißt das dass W in einer offenen Komponente liegt
W liegt in offener Komponente Und das heißt also er liegt in offener
Komponente SI von GC Und jetzt ist es im Prinzip genau der Punkt, wo
es spannend wird Bisher haben wir noch nicht viel gemacht Wir haben
gesagt, Traversierung von der Funktion Baumkante, da erzeuge ich im
Prinzip eine neue offene Komponente Jetzt kommt wirklich der
Knackpunkt von dem Algorithmus wo ich eine Nicht-Baumkante traversiere
und die Kante in eine offene Komponente reinzeigt Und zwar nicht in
eine abgeschlossene Komponente sondern in eine offene Komponente Und
dann behaupte ich
die SCCs SI bis SK werden gemerged in eine einzelne Komponente
Und zweitens behaupte ich, alle anderen
Komponenten bleiben unverändert.
Unverändert.
Okay, wie sehen wir das?
Auch hier nochmal ein Bild, was von den Folien ist.
Wir haben jetzt den aktuellen Knoten V.
Wir explorieren diese Kante zu dem Knoten W.
Und der liegt jetzt in einer offenen Komponente.
So, der Knoten W wurde bereits exploriert.
Das heißt, wir wissen, er liegt in irgendeiner Komponente SI.
Und das heißt insbesondere, dass es für den Knoten W einen Pfad zu dem
Repräsentanten geben muss.
Und jetzt können wir noch ein Stück weiter denken.
Ich habe also insgesamt eine Kante von V nach W, einen Pfad von W nach
RI und gleichzeitig einen Pfad von RI zu V, nämlich genau dem
Baumpfad.
Und das heißt, dass diese ganzen Knoten, die ich hier angeschaut habe
in meiner Tiefensuche, die ich aktuell auf meinem Stack liegen habe,
dass die tatsächlich alle gemersht werden müssen.
Ja, weil die liegen ja auf einem Kreis.
Okay, also das ist im Prinzip die Idee, die jetzt dahinter steckt.
So,
genau.
Also gucken wir uns das nochmal genau an.
Sei RI der Repräsentant von SI.
Dann weiß ich, es gibt einen Pfad von RI nach V, nämlich genau den
Baum.
Ich weiß, es gibt eine Kante VW.
Und ich weiß, es existiert ein Pfad W nach RI, wobei hier SI die
offene Komponente ist.
Genau.
So, und jetzt die Frage als allererstes mal, wie finden wir dieses RI?
Also hier nochmal dieses Bild.
Wir sind hier in Komponente SI mit dem Knoten W.
Die Frage ist, wie finde ich dieses RI hier?
Na gut, also durch Invariante C weiß ich folgendes.
Also die offenen Knoten, O-Notes.
Also Invariante C nochmal.
Ja, Repräsentanten partitionieren die offenen Komponente bezüglich
ihrer DFS-Nummer.
Das heißt, die O-Notes, das wissen wir auch, sind sortiert nach DFS
-Nummer.
Und der Repräsentant, das haben wir eben so definiert, ist der Knoten,
der die kleinste DFS-Nummer hat, von allen Knoten in dieser
Komponente.
Ist der Knoten mit kleinster DFS-Nummer in der Komponente.
Und was heißt das jetzt?
Na gut, das heißt im Prinzip, dass die nochmal hingeschrieben wäre,
DFS -Nummer von RI ist kleiner gleich DFS-Nummer von W.
Und auf der anderen Seite weiß ich, die DFS-Nummer von W muss echt
kleiner sein als die DFS-Nummer von RI für alle J größer als I.
Und warum weiß ich das?
Lege ich das Bild nochmal auf.
Rj, das sind genau die Repräsentanten, die hier danach in diesem Bild
kommen.
W ist in der offenen Komponente SI.
Das heißt, diese Geschichte hier war ja sortiert nach DFS-Nummer.
Das heißt, insbesondere ist es offensichtlich, dass diese DFS-Nummer
von W kleiner sein muss als die DFS-Nummer von den anderen Knoten da.
Okay, und was heißt das jetzt?
Na gut, das heißt, dass mein Update easy ist.
Update easy.
Und zwar entferne ich jetzt einfach die offenen Repräsentanten.
R mit DFS-Nummer von R größer DFS-Nummer von W.
So, und das erkläre ich jetzt auch nochmal genau.
Also, wir wissen folgendes.
Wir sind an dem Knoten W.
Wir haben auf diesem Stack OReps, haben wir alle diese einzelnen
Repräsentanten hier drauf.
Und gleichzeitig haben wir alle diese ganzen offenen Knoten hier
drauf.
Was wir jetzt machen ist, wenn wir durch diese beiden Eigenschaften
hier, weiß ich, wenn ich diese beiden Komponenten, also wenn ich alle
Knoten hier merchen möchte in einer einzelnen SCC, kann ich einfach
die ganzen Repräsentanten, die danach kommen, von meinem
Repräsentanten -Stack runternehmen.
Okay, und dann durch dieses Herunternehmen, habe ich diese Komponenten
gemerged.
Das heißt, die neue Komponente wird eben diese große, umzingelte
Komponente hier mit Repräsentanten R i.
So, die letzte Funktion, über die wir uns jetzt noch Gedanken machen
müssen, ist die Frage, wie finisht man jetzt einen Knoten oder wie
instanziiert man diese Backtrack-Funktion.
Also, E, finishing a node, V, Schrägstrich, Backtrack von U, V.
Okay, also durch Invariante B, also Invariante B sagt, offene
Komponenten S1 bis SK bilden Fahrt in GCS.
Durch Invariante B weiß ich, dass alle Knoten in der aktuellen
Komponente sind Baum-Nachfolger vom Repräsentanten.
Also, wenn ich hier so eine Komponente habe, dann sind alle Knoten,
die in dieser Komponente sind, sind Baum-Nachfolger von diesem
Repräsentanten.
So, das heißt, dass der Repräsentant,
dass das genau der letzte Knoten ist, auf dem die Backtrack-Funktion
aufgerufen wird von dieser Komponente.
Also, Repräsentant ist der letzte Knoten,
der gefinisht wird, der Komponente.
Und das heißt jetzt wiederum, dass die Komponente wird abgeschlossen,
wenn der Repräsentant abgeschlossen wird.
Das heißt, Komponente wird abgeschlossen, abgeschlossen,
wenn der Repräsentant abgeschlossen wird.
So, genau, der nächste Schritt ist jetzt wieder, sich zu überlegen,
wie sind diese Knoten auf den beiden Stacks geordnet.
Na gut, wir wissen, die Repräsentanten dieser Repräsentanten-Stacks
ist nach DFS-Numm geordnet.
Genau, und das heißt jetzt, dass unsere Komponente abgeschlossen wird,
die Komponente wird abgeschlossen, wenn der letzte Knoten
auf OREPs gefinisht wird.
Okay,
so und jetzt gucken wir uns das Bild hier nochmal an.
Wir fügen, also wir sind jetzt hier, das ist im Prinzip der letzte
Knoten von der Komponente, die ich gerade betrachte und ich möchte
einen Backtrack auf dieser Kante hier ausführen.
Was ich jetzt mache ist, na gut, okay, ich gucke, ist der aktuelle
Knoten im Prinzip der Knoten, der auf der Spitze von meinem OREPs
-Array hier steht.
Wenn das der Fall ist, dann kann ich allen Knoten, die in der
Komponente sind, den Repräsentanten zuweisen.
Und das mache ich genau, indem ich erstmal den Knoten selbst von dem
Stapel hier runternehme und dann führe ich diese Funktion so lange
aus, also was in dieser Schleife hier drin passiert ist im
Wesentlichen, ich weiß, die offenen Knoten sind alle hier auf dem
Stapel noch drauf und jetzt nehme ich im Prinzip alle Knoten von dem
offenen Knotenstapel runter, bis ich zu meinem Repräsentanten komme
und weise denen den Repräsentanten zu.
Also V ist hier offensichtlich der Repräsentant.
Solange eben der offene Knoten nicht der aktuelle Knoten ist, weise
ich diesen Knoten, wo ich hier Stück für Stück nach hinten gehe, den
Repräsentanten zu.
Und das ist dann die Backtrack-Funktion.
Und jetzt kann man sich als nächstes mal überlegen, warum, also ich
werde gleich noch im Detail erläutern, warum hier die Invarianten
erhalten bleiben, aber nebenbei kann man sich direkt mal überlegen,
warum das immer noch Linearzeit ist.
Ich habe ja dieses Dex und für diese Backtrack-Funktion muss ich ja
hier Knoten anschauen.
Aber das macht nichts anderes, als die Knoten anschauen, wie ich im
Prinzip vorher schon einmal angeschaut habe.
Das heißt, das macht nichts an der Linearzeit kaputt.
Genau, also, falscher Stift.
Also, wegen Invariante C.
Invariante C sagt, Repräsentanten partitionieren die offenen
Komponenten bezüglich ihrer DFS-Nummer.
Gilt folgendes, und zwar erstens, SK mit Repräsentant V gleich RK
besteht aus allen Knoten wie in O-Nodes nach W.
Also, alle diese Knoten sind auf O-Nodes drauf und sind tatsächlich
nach diesem Repräsentanten.
Zweitens, Finishing V schließt meine aktuelle Komponente SK ab.
So.
Dann weiß ich durch Invariante 2, keine Kante geht aus SK raus.
Moment, in offene Komponente.
Genau.
Weiter weiß ich dadurch, dass Invariante 1 gilt,
wenn SK abgeschlossen ist.
Genau.
Weiter weiß ich eben auch wieder durch Invariante 2, dass der Parent
von V in SK-1 liegen muss.
Ja, das ist eben genau offene Komponenten bilden diese Fahrt.
Ja, das heißt, der Parent muss in SK-1 liegen.
Auch offensichtlich.
Und dann überlegen wir uns noch Invariante 3.
Wenn ich diesen Knoten eben abgeschlossen habe, dann bilden die
Repräsentanten, äh, partitionieren die Repräsentanten immer noch die
Komponenten, die offenen Komponenten bezüglich ihrer DMS Nummer R.
Das Ding ist dann nicht mehr abgeschlossen und damit habe ich das
immer noch partitioniert.
Also, wenn alle Knoten nach V von O-Nodes entfernt wurden
und V von O-Reps entfernt wurde.
Okay, also die gilt offensichtlich.
So, und das war's.
Fertig.
Also, wie gesagt, ich habe es ganz schön detailliert gemacht.
Schauen wir uns noch mal ganz grob die grobe Struktur an.
Die Pause lassen wir jetzt leider weg.
Also, wo kommt die Magie her?
Wir haben nochmal diese drei Invarianten hier, die im Wesentlichen
sagt, okay, Kanten von abgeschlossenen Knoten gehen zu abgeschlossenen
Knoten, offene Komponenten bilden einen Faden GC und Repräsentanten
partitionieren die offenen Komponenten bezüglich ihrer DFS Nummer.
Jetzt haben wir die einzelnen Funktionen von der Tiefensuche
hergenommen und zwei Stapel dazu gepackt, nämlich genau diese beiden
Stapel hier, einmal O-Reps und O-Nodes, wobei O-Reps die
Repräsentanten der offenen Komponenten enthält und O-Nodes alle
offenen Knoten.
Das sind alle Knoten, die wir hier auf diesem Pfad hier sehen.
Und dann haben wir genau diese beiden Stapel immer so aktuell
gehalten, dass eben die offenen Knoten genau die Knoten auf diesem
Pfad hier sind und gleichzeitig die Repräsentanten ebenfalls auf
diesem Repräsentanten-Stapel sind.
Und die Magie, die ist genau passiert bei diesem Traverse-Non-Tree
-Edge.
Und dieses Traverse-Non-Tree-Edge schließt jetzt im Prinzip diesen
Kreis hier.
Und wenn ich diesen Kreis gefunden habe, dann kann ich die ganzen
Repräsentanten, die auf den einzelnen offenen Komponenten nach dem AI
sind, einfach von meinem Repräsentanten-Stapel runterschieben.
Das heißt, der Repräsentant der neuen Komponente ist eben genau dieses
AI.
Und wenn ich jetzt diese Backtrack-Funktion ausführe, da passiert
genau das.
Die ganzen offenen Knoten, die in dieser offenen Komponente hier sind,
kriegen eben ihre finale Komponentennummer hinzugewiesen, was eben
genau der Repräsentant von dieser Komponente ist.
Okay.
So, jetzt machen wir folgendes.
Jetzt haben wir nämlich noch 15 Minuten.
Jetzt gucken wir uns noch an, wie das tatsächlich dann irgendwie mal
in Code aussieht.
In den Übungsaufgaben ist es ja so, ihr sollt ein bisschen mit diesem
Framework rumspielen, weil man damit irgendwie Graphen-Algorithmen
relativ nett implementieren kann.
Was man da hat, ist irgendwie so Markos, die einem sagen, okay, für
einen Graphen-Iterier über alle Knoten.
Das Farbchen mal kann ich leider nicht spontan ändern.
Keine Ahnung, wie das gerade geht.
Ich hoffe, es geht halbwegs.
Kann ich das Licht noch vielleicht ausmachen?
Oder dunkel machen hier?
Beleuchtung, Tafel, aus.
Allgemein, aus.
Besser?
Dann nochmal Tisch.
Also dunkler kann ich es nicht machen, tut mir leid.
Gemütlicher wird es nicht.
Aber ich kann es tatsächlich auch hier zeigen.
Wir haben halt diese Markos, mit denen man über alle Knoten drüber
iterieren kann.
Am Anfang sind eben alle Knoten unmarkiert.
Die Komponentennummer ist irgendwie uninitialisiert.
Und dann habe ich diese globale Schleife, die mir sagt, ich führe
Knoten von allen unmarkierten Knoten aus.
Achso, das ist ja nett.
So, was passiert jetzt hier?
Dieses SCC, wie eben auch in der Funktion, die wir gesehen haben,
iteriert im Prinzip über alle ausgehenden Kanten von einem Knoten, den
ich mir gerade anschaue.
Am Anfang haben wir auch gesehen, werden die Knoten zu den Unfinished
und den offenen Repräsentanten hinzugefügt.
Luft natürlich, dass die jetzt hier nicht gleich heißen.
Nichtsdestotrotz gibt es jetzt hier zwei Fälle.
Der erste Fall ist, ja gut, wir haben eine Baumkante.
Das heißt, wir müssen tatsächlich weitermachen mit der Tiefensuchung,
müssen weiter reingehen.
Der andere Fall hier ist, wir haben eine Nicht-Baumkante.
Und in dem Fall müssen wir eben die Repräsentanten, die zu viel sind,
von unserem Stack runterschmeißen.
Das heißt, wir führen hier immer diese RootsPop-Funktion aus.
Und am Ende, wenn ich eben zurückkomme von meinem rekursiven Aufrufen
hier, führe ich diese Backtrack-Funktion aus.
Und diese Backtrack-Funktion, die wir gerade auch eben schon mal
gesehen haben, macht nichts anderes, als jetzt final die Komponenten
zuzuweisen.
Und zwar nehme ich genau die Komponente, die wir uns gerade anschauen.
Okay, Fragen dazu?
Okay, dann war es das im Prinzip, was wir heute machen wollten.
Nächste Woche, also Moment, morgen gibt es erstmal die Einführung und
Übung.
Michael wird morgen auch nochmal was zu den SCCs sagen, das auch
nochmal wieder rekapitulieren.
Und nächste Woche machen wir weiter mit Flussalgorithmen, die für sich
genommen auch spannend sind.
Da gibt es auch einen Haufen richtig interessante Anwendungen, die ich
auch nochmal versuche darzulegen.
Und dann war es das von meiner Seite.