6. Graphen

6.5 Starke Zusammenhangskomponenten

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.

Für eine Auflistung $L$ der Knotenmenge $V$ (Auflistung heißt hier, dass jeder Knoten genau einmal in $L$ vorkommt) schreiben wir $u <_L v $ (bzw. $u >_L v $), wenn $u$ vor $v$ (bzw. nach $v$) in $L$ vorkommt.

Mit dieser Notation können wir die Definition der topologischen Sortierung sehr kompakt schreiben: $L$ ist eine topologische Sortierung von $G = (V,E)$ wenn $ \forall u, v \in V: u \prec_G v \implies u \leq_L v \ $ gilt.

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)$ sich nur überschneiden können, wenn sie identisch sind. Sie bilden also eine Partition von $V$:

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

Übungsaufgabe Finden Sie die starken Zusammenhangskomponenten in

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(mnn)$. 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 Abschnitt. 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. Statt einer Animation zeige ich Ihnen einfach direkt die Bäume.

Die DFS-Bäume, wenn wir `topSortDFS` ausführen und die Knoten in der Reihenfolge $0, 1, \dots, 9, A, \dots, E$ durchgehen:

Ü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 die DFS-Bäume, die Liste $L$ und die stark zusammenhängenden Komponenten von $G$ in einer Abildung:

Als erstes fällt auf dass jede starke Zusammenhangskomponente in einem DFS-Baum ist, also nicht über mehrere verteilt, und innerhalb dieses DFS-Baumes auch zusammenhängend ist.

Übungsaufgabe Beweisen Sie, dass dies kein Zufall ist. Beweisen Sie, dass eine starke Zusammenhangskomponente $C \subseteq V$ in einem DFS-Baum $T$ enthalten ist: $C \subseteq V(T)$. Zeigen Sie des weiteren, dass $C$ innerhalb von $T$ nicht zerstückelt ist, dass also $C$ in $T$ zusammenhängend ist.

Die Liste $L$ stellt zwar keine topologische Sortierung dar, wie soll sie auch, wenn $G$ gar kein DAG ist, sortiert $G$ aber so gut es geht:

Theorem Sei $L$:=topSortDFS($G$). Für alle $u,v \in V$ gilt $ u \prec_G v \Longrightarrow v <_L u $. In Worten: wenn es einen Pfad von $u$ nach $v$ gibt, aber keinen zurück, dann muss $u$ in $L$ weiter rechts stehen.

Beweis. To be done.

Jetzt können wir einen linearen Algorithmus beschreiben, der die starken Zusammenhangskomponenten findet. Wir gehen dies Liste $L$ von rechts nach links durch und führen eine DFS entgegen der Kantenrichtung durch. Sei $v$ der Knoten, der gerade "dran" ist. Alle Knoten zu seiner rechten in $L$ sind bereits abgearbeitet und markiert worden. Das Theorem garantiert uns, dass für alle Knoten $u$ links von $v$ entweder $u \cong v$ gilt (sie also in der gleichen starken Zusammenhangskomponente wie $u$ liegen) oder $u \not \prec v$ gilt (es also keinen Pfad von $v$ nach $u$ gibt). Alle Knoten, die Tiefensuche "in Rückwärtsrichtung" von $u$ ausgehend findet, sind also mit $u$ in einer Zusammenhangskomponente. Findet sie auch alle? Nun ja, überzeugen sie sich: wenn sie einen Knoten $w$ "übersähe", dann nur, weil der Weg dorthin durch einen bereits früher markierten Aufruf von Tiefensuche markiert und blockiert worden wäre; aber dieser Aufruf hätte ja dann bereits die ganze starke Zusammenhangskomponente markiert.

Algorithmus: Starke Zusammenhangskomponenten finden

def findSCC(G):                                    
  L = topSortDFS(G)
  colorArray = [undefined, ..., undefined]
  for u in L from right to left:
      if colorArray[u] == undefined: 
          colorByDfs(u, color=u)
  
  def colorByReverseDfs(u, color):
      if (colorArray[u] != undefined:
          return                            
      else:
          colorArray[u] = color
                for v in inNeighbors(u):
                    colorByReverseDfs(v, color)
  
  return colorArray