ParAlg, Kapitel 4.2

4.2 Erreichbarkeit in gerichteten Graphen

Problem 4.2.1 ( $s$ - $t$ -Erreichbarkeit)Gegeben ein gerichteter Graph $G = (V, E)$ und zwei Knoten $s, t \in V$ : gibt es einen Pfad von $s$ nach $t$ ?

Falls $G$ ungerichtet ist, dann können wir den Algorithmus für Zusammenhangskomponenten aus dem vorherigen Kapitel laufen lassen und dann überprüfen, ob $s$ und $t$ in der gleichen Zusammenhangskomponente liegen. Für gerichtete Graphen geht das leider nicht mehr. Wir brauchen einen vollständigen Perspektivwechsel.

Definition 4.2.2 Sei $G = (V, E)$ ein gerichteter Graph über der Knotenmenge $V = {1, \dots, n}$ . Die Adjazenzmatrix ist die Matrix $A \in N^{n \times n}$ mit

\begin{array}{r} A_{u v} := {\begin{cases} 1 & falls (u, v) \in E \\ 0 & sonst. \end{cases} \end{array}

Erinnern Sie sich: ein Kantenzug in $G$ (auf Englisch walk in $G$ ) ist eine Folge $u_{0}, u_{1}, \dots, u_{k}$ mit $(u_{i - 1}, u_{i}) \in E$ für alle $1 \leq i \leq k$ . Also eine Folge von Knoten, bei der zwei aufeinanderfolgende Knoten durch eine Kante verbunden sind. Die Länge des Kantenzuges ist $k$ . Ein Kantenzug heißt Pfad, falls die $k + 1$ Knoten $u_{0}, \dots, u_{k}$ alle verschieden sind.

Lemma 4.2.3 Sei $G = (V, E)$ ein gerichteter Graph und $A$ seine Adjazenzmatrix. Mit $A^{k}$ bezeichnen wir die $k$ -te Potenz von $A$ und mit $A_{u v}^{k}$ den Eintrag von $A^{k}$ in Zeile $u$ und Spalte $v$ . Dann ist $A_{u v}^{k}$ die Anzahl der Kantenzüge von Länge $k$ mit Startpunkt $u$ und Endpunkt $v$ .

Beweis. Wir beweisen das Lemma per Induktion über $k$ . Für $k = 0$ gilt $A^{k} = I$ , die $(n \times n)$ -Einheitsmatrix. Es gilt $I_{u v} = 1$ genau dann, wenn $u = v$ , ansonsten ist $I_{u v} = 0$ . Dies ist auch genau die Anzahl der Kantenzüge von Länge $0$ von $u$ nach $v$ .

Sei nun $k \geq 1$ . Wir schreiben $B := A^{k - 1}$ und somit $A^{k} = A \cdot B$ . Nach Induktionshypothese ist $B_{u w}$ die Anzahl der Kantenzüge der Länge $k - 1$ von $v$ nach $w$ . Für zwei Knoten $u$ und $w$ gilt

\begin{aligned} A_{u w}^{k} & = (A \cdot B)_{u w} = \sum_{v \in V} A_{u v} B_{v w} \\ = \sum_{v \in V} {\begin{cases} 1 & falls (u, v) \in E, \\ 0 & sonst \end{cases}} \cdot {Anzahl der Kantenzüge der Länge k - 1 von v nach w} \\ = \sum_{\begin{array}{c} v \in V \end{array} (u, v) \in E} {Anzahl der Kantenzüge der Länge k - 1 von v nach w} \\ = {Anzahl der Kantenzüge der Länge k von u nach w} \end{aligned}

Die letzte Gleichung gilt, weil jeder $k$ -Kantenzug von $u$ nach $w$ die Form $u, v, \dots, w$ hat, wobei $(u, v) \in E$ gilt und $v, \dots, w$ ein Kantenzug der Länge $k - 1$ ist. $◻$

Die Idee für unseren parallelen Algorithmus für $s$ - $t$ -Erreichbarkeit ist nun, $A^{1}, A^{2}, \dots, A^{n - 1}$ irgendwie parallel zu berechnen und dann zu schauen, ob irgendwo $A_{s t}^{k} = 1$ gilt; hierbei nutzen wir aus, dass ein $s$ - $t$ -Pfad höchstens Länge $n - 1$ haben kann. Als Komplikation ergibt sich noch, dass die Einträge von $A^{k}$ exponentiell groß werden können: in einem vollständigen Graphen zum Beispiel ist $A_{u v}^{k} = (n - 1)^{k - 2} \cdot (n - 2) = Θ (n^{k})$ .

Übungsaufgabe 4.2.1 Die Formel $(n - 1)^{k - 2}$ ist fehlerhaft. Sei $K_{n}$ der vollständige gerichtete Graph auf $V = {1, \dots, n}$ ohne Selbstschleifen, also

\begin{aligned} K_{n} & = (V, V \times V ∖ {(v, v) | v \in V}) \end{aligned}

Sei $A$ die Adjazenzmatrix von $K_{n}$ . Finden Sie eine explizite Formel für die Einträge in $A^{k}$ .

Das Problem hoher ganzer Zahlen in $A^{k}$ lässt sich leicht umgehen. Wir sind ja nicht an der Zahl der Kantenzüge interessiert, sondern nur daran, ob deren Anzahl $0$ oder positiv ist. Wir definieren daher für $A, B \in {0, 1}^{n \times n}$ das Matrixprodukt $A ⊙ B$ als

\begin{array}{r} (1) & (A ⊙ B)_{u w} = \underset{v \in V}{⋁} A_{u v} \land B_{v w} . \end{array}

Es gilt nun: ${(A^{⊙ k})}_{u v}$ ist $1$ genau dann, wenn es einen Kantenzug der Länge $k$ von $u$ nach $v$ gibt. Wir definieren nun $\tilde{G}$ als den Graphen $G$ plus einer Selbstschleife an jedem Knoten; die Adjazenzmatrix $A$ von $\tilde{G}$ ist genau wie die von $G$ , nur dass auf der Diagonale lauter Einsen stehen. Es gilt nun: $A_{u v}^{k} = 1$ genau dann, wenn es in $G$ einen Kantenzug der Länge höchstens $k$ von $u$ nach $v$ gibt. Und somit lösen wir $s$ - $t$ -Erreichbarkeit, in dem wir schauen, ob

\begin{array}{r} {(A^{⊙ n})}_{s t} \end{array}

gleich 1 ist.

Beobachtung 4.2.4 Sei $G$ ein gerichteter Graph, $\tilde{G}$ der Graph $G$ plus eine Selbstschleife an jedem Knoten und $A$ die Adjazenzmatrix von $G$ . Für $s, t \in V$ gilt: es gibt einen $s$ - $t$ -Pfad in $G$ genau dann, wenn ${(A^{⊙ (n - 1)})}_{s, t} = 1$ ist. Hierbei ist $⊙$ das in ( $1$ ) definierte "Boolesche Matrixprodukt".

Ein Boolescher Schaltkreis für $s$ - $t$ -Erreichbarkeit

Unseren parallelen Algorithmus für $s$ - $t$ -Erreichbarkeit beschreiben wir als Booleschen Schaltkreis. Sei $d$ so, dass $2^{d - 1} < n \leq 2^{d}$ gilt. Wir berechnen $A^{⊙ 2^{d}}$ statt $A^{⊙ n}$ , was aber das Gleiche ist. Es gilt $d = ⌈ \log n ⌉$ . Wir können nun $A^{2^{d}}$ mit $d$ vielen " $⊙$ -Gates" berechnen:

Dies ist im Prinzip die schnelle Matrixmultiplikation, wie Sie sie vielleicht in Theoretischer Informatik 1 gesehen haben. Wir beschreiben nun einen Schaltkreis für $⊙$ . Dieser ist sehr groß, aber nicht sehr tief:

Dieser Schaltkreis berechnet $(A \cdot B)_{u w}$ für ein Paar $u w$ ; wir bauen nun $n^{2}$ solche Schaltkreise parallel für jedes Paar. Um Fan-in 2 zu erreichen, müssen wir das $⋁$ noch durch einen Binärbaum aus $\lor$ ersetzen. Der $⊙$ -Schaltkreis hat somit $n^{2} \cdot (n + n - 1) i n Θ (n^{3})$ Gates. Beachten Sie: das $Θ (n^{3})$ entspricht der $Θ (n^{3})$ , das Sie für die Laufzeitkomplexität des "üblichen" Matrixmultiplikationsalgorithmus bekommen. Fassen wir zusammen: ein $⊙$ -Schaltkreis hat $O (n^{3})$ Gates und Tiefe $O (\log n)$ . Der gesamte Schaltkreis für $s$ - $t$ -Erreichbarkeit hat somit $O (n^{3} \log n)$ Gates und Tiefe $O (\log^{2} n)$ .

Randbemerkung: auf einer Collision CRCW PRAM oder Common CRCW PRAM können wir das in $O (\log n)$ implementieren, weil wir das $⋀$ in $O (1)$ auswerten können.

4.2 Erreichbarkeit in gerichteten Graphen

Ein Boolescher Schaltkreis für s-t-Erreichbarkeit

Ein Boolescher Schaltkreis für $s$ - $t$ -Erreichbarkeit