6. Graphen

6.5 Starke Zusammenhangskomponenten

Definition 6.5.1 Sei

G = (V, E)

ein Digraph und

u, v \in V

. Wir schreiben

$u ⪯_{G} v$ , wenn es einen Pfad von $u$ nach $v$ gibt;
$u ≅_{G} v$ , wenn $u ⪯_{G} v$ und $v ⪯_{G} u$ , wenn es also Pfade in beide Richtungen gibt;
$u ≺_{G} v$ , wenn $u ⪯_{G} v$ aber nicht $v ⪯_{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 ≺_{G} v ⟹ u \leq_{L} v$ gilt.

Definition 6.5.2 Ein Digraph

G = (V, E)

heißt stark zusammenhängend, wenn

u ≅ 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 ≅ 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$ :

C C (G) := {{scc}_{G} (u) | u \in V}

ist die Menge der starken Zusammenhangskomponenten von

G

Übungsaufgabe 6.5.1 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 ⪯ v}$
can_reach_u := ${v \in V | v ⪯ 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 (m n n)$ . 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 6.5.2 Zeigen Sie, dass die obige Laufzeitanalyse optimal ist. Genauer gesagt: finden Sie einen Digraphen mit

Knoten und

Kanten, sodass die Laufzeit

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 ein DAG ist, liefert er uns eine topologische Sortierung. Falls kein DAG ist, kann uns die Ergebnisliste , 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 durchgehen:

Übungsaufgabe 6.5.3 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 und die stark zusammenhängenden Komponenten von 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 6.5.4 Beweisen Sie, dass dies kein Zufall ist. Beweisen Sie, dass eine starke Zusammenhangskomponente

in einem DFS-Baum

enthalten ist:

. Zeigen Sie des weiteren, dass

innerhalb von

nicht zerstückelt ist, dass also

zusammenhängend ist.

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

Theorem 6.5.3 Sei :=topSortDFS(). Für alle

gilt

. In Worten: wenn es einen Pfad von

nach

gibt, aber keinen zurück, dann muss

weiter rechts stehen.

Beweis. To be done.

Jetzt können wir einen linearen Algorithmus beschreiben, der die starken Zusammenhangskomponenten findet. Wir gehen dies Liste von rechts nach links durch und führen eine DFS entgegen der Kantenrichtung durch. Sei der Knoten, der gerade "dran" ist. Alle Knoten zu seiner rechten in sind bereits abgearbeitet und markiert worden. Das Theorem garantiert uns, dass für alle Knoten links von entweder gilt (sie also in der gleichen starken Zusammenhangskomponente wie liegen) oder gilt (es also keinen Pfad von nach gibt). Alle Knoten, die Tiefensuche "in Rückwärtsrichtung" von ausgehend findet, sind also mit in einer Zusammenhangskomponente. Findet sie auch alle? Nun ja, überzeugen sie sich: wenn sie einen Knoten "ü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