TI

Definition Sei $G = (V,E)$ ein Digraph und $u,v \in V$. Wir schreiben

$u \preceq_G v$, wenn es einen Pfad von $u$ nach $v$ gibt;
$u \cong_G v$, wenn $u \preceq_G v$ und $v \preceq_G u$, wenn es also Pfade in beide Richtungen gibt;
$u \prec_G v$, wenn $u \preceq_G v$ aber nicht $v \preceq_G u$.

Wenn es klar ist, welcher Digraph $G$ gemeint ist, dann lassen wir den Subskript auch gerne weg.

Definition Ein Digraph $G = (V,E)$ heißt stark zusammenhängend, wenn $u \cong v$ für alle $u,v \in V$ gilt. Wenn es also von jedem Knoten zu jedem anderen einen Pfad (und auch wieder zurück) gibt.

Für einen (nicht unbedingt stark zusammenhängenden) Digraph $G$ ist die starke Zusammenhangskomponente von $u$ (Englisch strongly connected component) die Knotenmenge

$$ \scc_G(u) := \{ v \in V \ | \ u \cong v \} $$

Zwei Mengen $\scc_G(u)$ und $\scc_G(v)$ können sich nur überschneiden, wenn sie identisch sind. Sie bilden also eine Partition von $V$:

$$ \SCC(G) := \{ \scc_G(u) \ | \ u \in V\} $$ ist die Menge der starken Zusammenhangskomponenten von $G$.

Übungsaufgabe Finden Sie die starken Zusammenhangskomponenten in

Wir können einen Meta-Graphen auf den starken Zusammenhangskomponenten definieren, in dem wir jede Komponente als einen Knoten betrachten. Formal:

Definition Sei $G$ ein gerichteter Graph. Der SCC-Graph von $G$ hat als Knotenmenge die starken Zusammenhangskomponenten von $G$ und die Kantenmenge

\begin{align*} \{ (\scc(u), \scc(v)) \ | \ (u,v) \in E \} \ . \end{align*}

Zwei starke Zusammenhangskomponenten $C_1$ und $C_2$ von $G$ sind also im SCC-Graphen benachbart, wenn es $u \in C_1$ und $v \in C_2$ gibt mit $(u,v) \in E$.

Übungsaufgabe Zeichnen Sie den SCC-Graphen zum obigen Beispielgraphen.

Übungsaufgabe Zeigen Sie: der SCC-Graph eines gerichteten Graphen ist immer azyklisch.

Unser Hauptziel in diesem Abschnitt ist es, einen linearen Algorithmus zu entwickeln, der die linearen Zusammenhangskomponenten findet. Wenn Ihnen Effizienz egal ist, dann können Sie zum Beispiel folgendes machen:

Ineffizienter Algorithmus für starke Zusammenhangskomponenten

color := ein Array der Größe $n$; jede Zelle auf undefined initialisiert
for u in V:

if color[u] != undefined: continue (weil u schon besucht wurde)
reachable_from_u := $\{v \in V \ | \ u \preceq v\}$
can_reach_u := $\{v \in V \ | \ v \preceq u\}$
gibt allen Knoten in der Schnittmenge reachable_from_u $\cap$ can_reach_u die Farbe $u$

Nun ist color[v] für jeden Knoten definiert und ist einfach der Name des kleinsten Knoten, der in der gleichen Zusammenhangskomponente liegt.

Was ist die Laufzeit des Algorithmus? Die for-Schleife macht $n$ Durchläufe. Jeder Durchlauf ermittelt reachable_from_u und can_reach_u, zum Beispiel mit Tiefensuche und benötigt daher $O(m)$ Zeit. Wir erhalten also eine Laufzeit von $O(mn)$. Dies ist nicht linear.

Ist unsere Analyse übermäßig pessimistisch? Wenn zum Beispiel $u$ in Zeile 2.i bereits eine Farbe hat, dann überspringen wir ihn ja.

Übungsaufgabe Zeigen Sie, dass die obige Laufzeitanalyse optimal ist. Genauer gesagt: finden Sie einen Digraphen mit $n$ Knoten und $m \geq n$ Kanten, sodass die Laufzeit $\Omega(nm))$ ist. Hinweis. Es ist kein besonders kompliziertes Beispiel.

Der Algorithmus von Kosaraju und Sharir

Der erste Schritt hin zu einem linearen Algorithmus ist Tiefensuche. Erinnern Sie sich an den Algorithmus topSortDFS im letzten Teilkapitel. Wenn $G$ ein DAG ist, liefert er uns eine topologische Sortierung. Falls $G$ kein DAG ist, kann uns die Ergebnisliste $L$, wenn sie schon keine topologische Sortierung ist, uns dennoch nützliche Information liefern? Probieren wir es aus und lassen topSortDFS auf dem Digraph der letzen Übungsaufgabe laufen, und zwar indem wir die Knoten in der Reihenfolge $0, 1, \dots, 9, A, \dots, E$ durchgehen. Sie sehen hier den Graphen mit den von der DFS beschrittenen Kanten, die daraus entstandenen Bäume sowie die Liste $L$:

Übungsaufgabe Lassen Sie den Algorithmus topSortDFS nochmal auf dem gleichen Graphen laufen, gehen aber die Knoten in Zeile 5 von topSortDFS in einer anderen, von Ihnen selbst gewählen Reihenfolge durch.

Welche Reihenfolge gibt Ihnen die wenigsten DFS-Bäume? Welche die meisten?

Wir zeigen nun nochmal obige Abbildung, aber zusammen mit den stark zusammenhängenden Komponenten:

Die Liste $L$ ist natürliche keine topologische Sortierung von $G$; die kann es ja gar nicht geben. Wir könnten allerdings hoffen, dass sie zumindest Knoten aus verschiedenen starken Zusammenhangskomponenten topologisch sortiert. Dass also aus $u \prec_G v$ folgt, dass $v \lt_L u$. Dies ist aber nicht der Fall: wir haben $B \prec_G 9$ und $5 \prec_G 9$, die $9$ steht aber in der Liste zwischen $5$ und $B$. Die Tatsache $u \prec_G v$ allein kann also noch nichts über deren Positionen in $L$ aussagen. Um etwas interessantes über $L$ sagen zu können, brauchen wir eine Definition:

Definition Sei $G$ ein gerichteter Graph und $L$ die Ergebnisliste von topSortDFS$(G)$. Der SCC-Chef eines Knotens $u$ ist derjenige Knoten in $\scc(u)$, der in $L$ am weitesten rechts steht. Wir schreiben dafür kurz $\sccchef(u)$.

Im obigen Beispiel sind die SCC-Chefs $A$, $0$, $1$, $9$, $3$ und die $4$. Interessant wird es, wenn wir uns den SCC-Graphen zu $G$ anschauen und jede starke Zusammenhangskomponente (also jeden Knoten vom SCC-Graphen) nach ihrem Chef benennen. Der SCC-Graph schaut dann so aus:

Jetzt sehen wir (zumindest für dieses Beispiel), dass $L$ zumindest die SCC-Chefs topologisch sortiert. Formal:

Lemma Sei $G$ ein gerichteter Graph und $L$ die Ergebnisliste von topSortDFS$(G)$. Sei $u$ ein SCC-Chef und $v$ ein beliebiger Knoten mit $u \prec_G v$. Dann gilt $v \lt_L u$, der Knoten $u$ steht also rechts von $v$.

Beweis. Sei $w$ von allen Knoten, die auf einem Pfad von $u$ auf $v$ liegen, derjenige, der von topSortDFS zuerst auf den Stack gelegt wird. Sei $X$ die Menge der Knoten, die nach $w$ auf den Stack gelegt werden, bevor $w$ wieder entfernt wird; also die Menge der echten Nachfahren von $w$ im DFS-Wald.

Fall 1: Dieser Knoten ist $u$. Da es einen Pfad von $u$ nach $v$ gibt und diese Knoten alle noch nicht visited sind, wird die Tiefensuch $v$ erreichen, bevor sie $u$ wieder vom Stack löscht: $v \in X$. Somit wird $v$ noch vor $u$ der Liste angefügt.

Fall 2: Dieser Knoten ist $v$. Da es keinen Pfad von $v$ nach $u$ gibt (nach Annahme $u \prec_G v$), gilt $u \not \in X$. Der Knoten $u$ kommt also erst auf den Stack, nachdem $v$ wieder gelöscht worden ist; $v$ wird somit zuerst der Liste $L$ angehängt.

Fall 3: Dieser Knoten ist weder $u$ noch $v$. Wir wissen: es gibt einen Pfad $w \path v$ (nach Definition von $w$), und somit $v \in X$. Aber keinen von $w$ nach $u$. Warum nicht? Wenn es einen gäbe, gälte $u \in X$ und $u$ stünde somit links von $w$ in der Liste $L$. Weiterhin hätten wir nun einen Pfad $u \path w$ (nach Wahl von $w$) und $w \path u$ (nach fälschlicher Annahme); es gälte somit $u \equiv w$, die Knoten $u$ und $w$ wären also in der gleichen Zusammenhangskomponente. Dies kann nicht sein, da $u$ ja ein SCC-Chef ist und von all diesen am weitesten rechts in $L$ steht. Somit: $u \not \in X$.

Da nun also $v \in X$ und $u \not \in X$ gilt, wird $v$ vor $w$ an die Liste angehängt und $u$ nach $w$. Somit steht $u$ weiter rechts als $v$. $\square$

$L$ definiert somit eine topologische Ordnung auf den Chefs der Zusammenhangskomponenten:

Korollar Wenn $u \prec_G v$, dann gilt auch $\sccchef(u) \prec_G \sccchef(v)$ und somit $\sccchef(v) \lt_L \sccchef(u)$. Im Umkehrschuluss: wenn $\sccchef(u) \lt_L \sccchef(v)$, dann gibt es keinen Pfad von $u$ nach $v$.

Nun können wir starke Zusammenhangskomponenten wie folgt finden, indem wir $L$ von rechts nach links durchgehen und pro (noch nicht besuchtem) Knoten eine Tiefensuche entgegen der Kantenrichtung ausführen:

Algorithm find_scc$()$

markiere alle Knoten als noch nicht besucht
for $v \in L$ von rechts nach links:
1. Falls $v$ bereits besucht wurde: continue
2. Ansonsten, falls $v$ noch nicht als besucht markiert ist, führe von $v$ ausgehend eine Tiefnsuche aus entgegen der Kantenrichtung. Dies markiert die neuen Knoten als besucht.
3. Sei $S$ die Menge der Knoten, die durch diese Tiefnsuche besucht wurde.
4. Behauptung: $S = \scc(v)$. Färbe die Knoten $w \in S$ dementsprechend.
second step

Theorem Die Behauptung in Punkt 2.4 stimmt: die Menge der nun neu besuchten Knoten ist genau $\scc(v)$.

Beweis. Wir zeigen, dass folgende Invariante vor Schritt 2.2 gilt:

Alle Knoten rechts von $v$ in $L$ stehend sind als besucht markiert.
Für jede Zusammenhangskomponente $S$ sind entweder alle Knoten besucht oder kein Knoten besucht.

Die Invariante gilt trivialerweise am Anfang, weil rechts von $v$ nichts steht und auch noch kein Knoten als besucht markiert ist. Nehmen wir nun an, die Invariante gilt vor Schritt 2.2, wo wir Knoten $v$ betrachten. Wir müssen zwei Dinge zeigen: (1) die Menge $S$ der in Schritt 2.2 besuchten Knoten ist $\scc(v)$; (2) die Invariante gilt dann auch für den nächsten Knoten, den die Schleife in Punkt 2 wählt; in beiden Fällen dürfen wir annehmen, dass die Invariante zur Zeit gilt.

Wir zeigen nun (1), also $\scc(v) = S$. Dies folgt aus zwei Behauptungen.

Behauptung: $\scc(v) \subseteq S$. Um dies zu sehen, betrachten wir ein beliebiges $u \in \scc(v)$. Vor Schritt 2.2 ist $v$ noch unbesucht, und gemäß Invariante ist ganz $\scc(v)$ unbesucht, auch der Pfad von $u$ nach $v$. Die rückwärtsgewandte Tiefensuche wird von $v$ ausgehend somit $u$ sicherlich erreichen. Es gilt also $v \in S$.

Behauptung: $S \subseteq \scc(v)$. Sei $u \in S$ ein beliebiger Knoten. Wir wollen zeigen, dass $u \in \scc(v)$ liegt. Da $u$ von der rückwärtsgewandten Tiefensuche erreicht worden ist, gilt $u \leq_G v$. Es gibt nun zwei Fälle: (i) $u \cong_G v$ ist, dann gilt $u \in \scc(v)$, wie behauptet. (ii) $u \prec_G v$: es gibt einen Pfad von $u$ nach $v$ aber nicht zurück. In diesem Falle gilt auch $\sccchef(u) \prec_G v$. Nach gilt $v \lt_G \sccchef(u)$. Laut Invariante ist aber alles, was in $L$ rechts von $v$ liegt, bereits besucht worden. ALso auch $\sccchef(u)$ und somit die ganze starke Zusammenhangskomponente $\scc(u)$. Der Knoten $u$ ist also auch bereits markiert worden. Die von $v$ ausgehende Tiefensuche würde $v$ also nicht besuchen. Wir folgern, dass Fall (ii) nicht eintreten kann. Und somit tritt Fall (i) ein und es gilt $u \in \scc(v)$.

Aus beiden Behauptungen folgt nun $S = \scc(v)$. Wir müssen nun zeigen, dass die Invariante auch in der nächsten Runde gilt. Dass jede Zusammenhangskomponente entweder ganz oder gar nicht als besucht markiert worden ist, gilt immer noch, denn geändert hat sich ja nur, dass nun zusätzlich $\scc(v)$ als besucht markiert worden ist. Und das nächste $v'$, mit der wir in Schritt 2.2 gehen, ist das rechteste aller unmarkierten Knoten, und somit gilt die Invariante weiterhin. $\square$

Algorithmus: Finde starke Zusammenhangskomponenten

def KosarajuSharirSCC(G):                                    
  L = topSortDFS(G)
  sccChef = [undefined, ..., undefined] # alle SCC-Chefs noch unbekannt / undefiniert

  for v in L from right to left: 
      if sccChef[v] != undefined 
          continue # kein SCC-Chef; gehört zu einer schon besuchten SCC

      stack = new Stack(v)
      sccChef[v] = v # v ist der rechteste Knoten in seiner SCC; also sein eigener Chef

      while (stack.nonEmpty()):
          u = stack.top() 
          if u has unvisited in-neighbor u':
              sccChef[u'] = v # wie oben begründet gehört $u'$ zur gleichen SCC wie v 
              stack.push(u')
          else: # wir haben alle Nachbarn von u erkundet 
              stack.pop()
  return sccChef

Insgesamt erhalten wir folgendes Ergebnis:

Theorem Der Algorithmus KosarajuSharir läuft in $O(n+m)$ Schritten und findet die starken Zusammenhangskomponenten. Genauer gesagt: wenn sccChef das Ergebnis-Array ist, dann gilt $u \cong_G v$ genau dann, wenn sccChef[u] == sccChef[v].

Hier eine Animation der zweiten Phase von KosarajuSharirSCC, also die Rückwärts-DFS auf Basis der Liste $L$. Zur Verdeutlichung habe ich die starken Zusammenhangskomponenten farblich markiert.