Directed Graphs und Strong Connectivity



  • Hallo zusammen
    Ich beschäftige mich gerade mit gerichteten Graphen und der Eigenschaft der Strong Connectivity (Sämtliche Vertices müssen von sämtlichen Vertices erreichbar sein).

    Ich hätte mir gedacht, dass ich einfach der Reihe nach von allem Vertices einen DFS (Depth First Search) mache und prüfe, ob am Ende jedes Durchlaufs sämtliche Vertices als "Visited" deklariert sind. In meinen Unterlagen ist jedoch festgehalten, dass ich einfach einen beliebigen Vertex aussuchen kann, einen DFS durchführen und prüfen, ob sämtliche Vertices besucht wurden, schliesslich sämtliche Richtungen umdrehen und das Ganze noch einmal. Also nur 2 iterationen.

    Das ist natürlich phänomenal, allerdings sehe ich nicht, wieso dass funktioniert! Kann mir das jemand erklären?



  • Die erste DFS liefert Dir alle Knoten, die von Deinem Startknoten x aus erreichbar sind. Das ist denke ich noch klar.

    Im zweiten Schritt wo du die Pfeile umdrehst entdeckst Du alle Knoten, die einen Weg zu x besitzen.

    In der starken Zusammenhangskomponente von x sind nun gerade alle Knoten drin, die sowohl von x aus erreichbar sind, als auch x erreichen können. Also gerade die Knoten, die von beiden vorherigen Suchen aus gefunden wurden. Wenn Du Dir das also vorher für jeden Knoten gemerkt hast, dann mußt Du nur nochmal alle Knoten ablaufen und anschauen, ob sie von beiden Suchen gefunden wurden.



  • OK, aber nehmen wir einmal an, ich hätte ganz einfach 3 Vertices (A,B,C). Die beiden DFS's waren beide erfolgreich für den Vertex A. Das heisst doch aber nun lediglich, dass A -> B and A -> C and B -> A and C -> A erfüllt ist. Doch was ist mit B -> C resp. C -> B ??? Das ist doch nun nicht ermittelt also die "Strong Connectivity" IMHO nicht nachgewiesen...





  • Ishildur schrieb:

    OK, aber nehmen wir einmal an, ich hätte ganz einfach 3 Vertices (A,B,C). Die beiden DFS's waren beide erfolgreich für den Vertex A. Das heisst doch aber nun lediglich, dass A -> B and A -> C and B -> A and C -> A erfüllt ist. Doch was ist mit B -> C resp. C -> B ??? Das ist doch nun nicht ermittelt also die "Strong Connectivity" IMHO nicht nachgewiesen...

    Das ist doch transitiv: wenn Du von A nach C kommst und von B nach A, dann kommst Du auch von B über A nach C.

    Du kannst sozusagen wenn Du von A nach B willst und x Dein Startknoten ist, immer im zweiten Baum von A zu x laufen und im ersten dann von x zu B. Das ergibt insgesamt einen Weg von A nach B.



  • Die Beweis Idee ist in etwa so:
    Der erste DSF Durchlauf stellt fest, welche Knoten von den jeweiligen Startknoten des DSF Durchlaufs erreicht werden können. Es entstehen also Bäume aus T- Kanten.
    Man findet also zuerst den ersten T_baum , dann den zweiten (wenn es ihn gibt) dann den dritten usw. Somit kann es zwischen den _Bäumen keine T_Kanten mehr geben, sondern nur rückwärts gerichtete Kanten. (Sonst währe der durch eine weitere T-Kante erreichbare Knoten ja schon im vorherigen Baum).

    Also gibt es zwischen allen so gefundenen T_Bäumen nur Rückwärtskanten.

    Daraus ergibt sich aber, das die starken Zusammenhangskomponenten nur jeweils innerhalb eines Baumes sein können. (Wenn man einen Baum vertläßt kommt man nicht mehr dahin zurück, da es zwischen den Bäumen keine T-Kanten gibt).

    Dann drehst du die Kanten um und suchst erneut mit einem DSF Durchlauf.

    Beim ersten Durchlauf hast du die Knoten gefunden die von der "Wurzel" des jeweiligen T baumes erreichbar sind. Nach dem Umdrehen suchst du wieder von der Wurzel alle erreichbaren kanten.
    Da du aber die Kanten umgedreht hast findest du die Knoten von denen es einem Weg zur Wurzel gibt (innerhalb des entsprechenden T_Baumes).

    Du hast also beim ersten DSF Durchlauf Knoten die von der Wurzel aus erreichbar sind. Beim Zweiten Durchlauf erhälst du von diesen die Teilmenge die auch einen Weg zur Wurzel haben. Beides zusammen ist starker Zusammenhang.

    Damit hast du die erste starke Zusammenhanhskomponente korrekt berechnet.
    Entfernst du diese jetzt (nur vorstellen das du dies tun würdest) kannst du mit den selben Argumenten die nächste starke Zusammenhangskomponente finden usw. (Das ist die Induktion in dem Beweis auf Seite 18)
    Somit berechnest du alle starken Zusammenhangskomponenten korrekt.



  • Es fehlt aber noch etwas was ich vergessen habe zu schreiben. Man führt nicht einfach nur 2 DSF Durchläufe durch und dreht dazwischen die Kanten um, sondern beim ersten Durchlauf speichert man in umgekehrter Reihenfolge die Reihenfolge in der die Knoten beim DSF Durchlauf abgearbeitet sind. Diese umgekehrte Reihenfolge ist dann die, mit der man den 2. DSF Durchlauf beginnt.
    So bekommt man die Information die der erste durchlauf erzeugt (Die T-Baäume)in den 2 DSF Durchlauf.


Log in to reply