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 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$.

Wenn nun $v$ ein SCC-Chef ist und wir von $v$ ausgehend die Kanten rücktwärts erkunden, dann erreichen wir (1) alle Knoten in $\scc(u)$; (2) eventuell manche Knoten, deren SCC-Chef rechts von $u$ steht; (3) gemäß Korollar keine Knoten $u$, deren SCC-Chef links von $v$ steht. Dies motiviert die zweite Phase des Algorithmus: wir gehen $L$ von rechts nach links durch; für jeden noch nicht besuchten Knoten $v$ führen wir eine Tiefensuche entgegen der Kantenrichtung durch; Knoten wie in (2), deren SCC-Chef weiter rechts steht als $v$, werden nicht besucht, weil sie bereits vorher markiert worden sind; Knoten $u$ wie in (3), deren SCC-Chef weiter links steht als $v$, werden nicht besucht; Knoten wie in (1), die zur gleichen Zusammenhangskomponente gehören wie $u$, werden alle besucht, weil sie anfangs ja auch alle unmarkiert sind.

Algorithmus: Finde starke Zusammenhangskomponenten

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

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

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

      while (stack.nonEmpty()):
          v = stack.top() 
          if v has unvisited in-neighbor w:
              sccChef[w] = u # wie oben begründet gehört $w$ zur gleichen SCC wie u 
              stack.push(w)
          else: # wir haben alle Nachbarn von v 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 \equiv 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.