Ψ Die Informatikseite

Menü
Informatik » Bachelor » Algorithmen der Informatik » Algorithmen auf besonderen Graphen
Dynamisches Programmieren Algorithmen der Informatik Netzwerkflußproblem
Unterabschnitte

Algorithmen auf besonderen Graphen

DFS in Digraphen (Baumkante,Vorwärtskante,Rückwärtskante und Seitwärtskante)

Wir durchsuchen den Graphen mit einer Tiefensuche (DFS). Dabei gehen wir die Adjazenslisten der Knoten durch. Dabei sind die Knoten,
  • die noch nicht besucht sind, blau
  • die besucht worden sind, schwarz
  • und die gerade noch auf dem Stack liegen, für welche die DFS also noch läuft, grün
Die dabei explorierten Kanten werden folgendermaßen genannt:
  • Baumkante: Wenn der Zielknoten beim explorieren der Kante blau ist. (ganz normale Kante)
  • Vorwärtskante: Wenn der Zielknoten beim explorieren der Kante schwarz ist. (d.h. der Index, der dem Zielknoten bei der Tiefesuche zugeteilt worden ist, ist größer als der Index von dem momentanen Knoten)
  • Rückwärtskante: Wenn der Zielknoten beim explorieren der Kante grün ist. (d.h. das die Tiefensuche für diesen Knoten nicht abgeschlossen ist.) Der Knotenindex des Zielknotens ist kleiner als der Knotenindex des momentanen Knotens. Wir haben in diesem Fall einen Zyklus gefunden.
  • Seitwärtskante: Alle übrigen Kanten. Die Tiefensuche kann vollständig abgeschlossen sein, ohne das ein Teilgraph besucht worden ist, wenn dieser von diesem Bereich nicht explorierbar ist. Alle Kanten, die von diesem Bereich dann in den alten schon abgeschlossenen Bereich führen, werden Seitwärtskanten genannt.

Topologische Sortierung

Eine topologische Sortierung kann nur dann vorliegen, wenn der Graph keine Zyklen hat. Der Knoten, der keine Vorgänger hat, bekommt die topologische Sortierungsnummer 1. Dann gehen wir nacheinander die Adjazenslisten mittels Breitensuche durch und numerieren die einzelnen Knoten durch, die wir in die Schlange einfügen.

SCCs - ,,strongly connected component'' - Starke Zusammenhangskomponenten

Algorithmus - Aho/Hopcroft/Ullman

Der Algorithmus funktioniert wie folgt:
  • Wir gehen den Graphen mit Hilfe einer Tiefensuche durch. Dabei bestimmen wir den Schwarzfärbungsindex eines jeden Knotens. Der Schwarzfärbungsindex ist die Reihenfolge in der die Knoten von der Tiefensuche wieder verlassen werden und schwarz gefärbt werden.
  • Wir drehen alle Kanten um. D.h. wir erzeugen aus dem Graphen $G$ den inversen Graphen $G^{-1}$
  • Wir lassen wiederum die Tiefensuche laufen. Dabei starten wir diese immer wieder von dem Knoten mit dem höchsten Schwarzfärbungsindex, der noch nicht besucht ist. Heraus kommt dann ein DFS-Wald. Jeder Baum im Wald ist eine SCC.

Beweis des SCC-Algorithmusses

  • Es ist klar, daß wenn man innerhalb einer SCC die Kanten umdreht immer noch eine SCC hat, weil eine SCC einen Zyklus bildet. Es geht so nur die andere Richtung herum.
  • Nehmen wir an, im Originalgraphen $G$ gab es eine Kante von
    $A$ nach $B$.
    Dann gibt es in $G^{-1}$ eine Kante von
    $B$ nach $A$.
    Die Tiefensuche für die aktuelle SCC $B$ würde Gefahr laufen auch andere SCCs in sich mit aufzunehmen, da es eine Kante gibt. Dies ist jedoch nicht der Fall, da die Tiefensuche im Originalgraphen $G$ über die Kante gekommen ist und folglich beim Schwarzfärben die Knoten in den anderen SCCs einen höheren Schwarzfärbungsindex bekommen haben und folglich zuerst exploriert werden. Also darf die Kante in $G^{-1}$ von $B$ nach $A$ gar nicht gegangen werden.

Dynamisches Programmieren Algorithmen der Informatik Netzwerkflußproblem