Ein Algorithmus für die transitive Hülle mit lin. erwarteter Laufzeit
Ein Algorithmus für die transitive Hülle in Digraphen mit linearer erwarteter Laufzeit

Die Wahrscheinlichkeit eines Digraphen mit n Knoten und m Kanten ist (nur) eine Funktion von n und m. Daraus folgt (wir lassen der Einfachheit halber Schleifen (=Kanten $v \rightarrow v$) zu), daß jede Kante (u,v) mit Wahrscheinlichkeit $\frac{m}{n^2}$ vorhanden ist, falls wir Graphen mit n Knoten und m Kanten betrachten.
Einschub: Breitensuche (BFS): Schlange, queue, FIFO:

Durchlaufe Graphen, indem wir, solange möglich den vordersten Knoten v aus der Queue nehmen, ihn behandeln und die Liste seiner noch nicht behandelten Nachbarn in die queue hinten einfügen.

Beispiel:

algorithm exp-lin-transitive-closure

(C.P. Schnorr, An Algorithm for Transitive Closure with Linear Expected Time, SIAM Journal on Computing 7 (1978), pages 127-133.)

Phasen:

0.

Konstruiere die linear geordneten Adjazenzlisten $L^r_i, i=1,\ldots ,n$ des Graphen G^r (entsteht aus G durch Umkehrung aller Knoten).
Beispiel:

$\begin{array} {ccccc\vert ccccc} L_1 & = & 4 & 1 & 2 & L^r_1 & = & 1 & 2 & 4\\... ...^r_3 & = & 2 & 3 & \\ L_4 & = & 1 & 4 & 2 & L^r_4 & = & 1 & 2 & 4 \end{array}$

Ersetze ebenfalls alle L_i durch L^rr_i ($\rightarrow$ sortierte Adjazenzlisten)

1.

Berechne für jeden Knoten i in BFS-Art eine Liste S_i von von i aus erreichbaren Knoten, so daß (i) oder (ii) gilt:

(i)

$\vert S_i\vert < \lfloor \frac{n}{2} \rfloor + 1$ und S_i enthält alle von i aus erreichbaren Knoten

(ii)

$\vert S_i\vert = \lfloor \frac{n}{2} \rfloor + 1$

2.

Entsprechende Listen P_i von Vorgängern von i

3.

for i:=1 to n do
		 $L^*_i := S_i \cup \{j; i \in P_j\} \cup \{j;
 \vert S_i\vert=\vert P_j\vert=\lfloor\frac{n}{2}\rfloor + 1\}$;od      

Bilde (L^*_i)^rr für $i=1,\ldots ,n$

Korrektheit: $j \in L^*_i$ g.d.w. (i,j) in transitiver Hülle.



Beweis: Das Durchlaufen des Graphen (von V₁ aus für die Konstruktion von S₁) in BFS-Manier liefert eine Folge ${(a_t)}_{t \geq 1}$ von Knoten. Sei $L_{\sigma(\nu)}$ die $\nu$-te Adjazenzliste, die in der BFS erkundet wird,

$$L_{\sigma(\nu)} = \left(a_t;\text{h}(\nu) < t \leq \text{h}(\nu + 1)\right)$$

Sei $\Delta L_{\sigma(\nu)}$ die Menge der a_t in $L_{\sigma(\nu)}$, und sei

$$S_i(t) := \{a_1,a_2,\ldots,a_t\}$$

Wie bereits gezeigt, ist

$$\text{WS}(j \in L_i)=\frac{m}{n^2}, \quad \forall i,j$$

Alle n-Tupel von geordneten Listen L₁,L₂,...,L_n mit

$$m=\sum^{n}_{i=1}\vert L_i\vert$$

sind aufgrund der Voraussetzungen über die Wahrscheinlichkeitsverteilung gleich wahrscheinlich.

Also:
Beobachtung 1: Die Mengen $\Delta L_{\sigma(\nu)}, \nu = 1,2,\ldots$ sind (paarweise) unabhängig.
Beobachtung 2: Die $\Delta L_{\sigma(\nu)}$ sind gleichverteilt, d.h. für alle $A \subseteq \{1,\ldots,n\}$ gilt:

$$\text{WS}(\Delta L_{\sigma(\nu)}=A) = (\frac{m}{n^2})^{\vert A\vert}(1-\frac{m}{n^2})^{n-\vert A\vert}$$

Lemma: Sei $A \subseteq \{1,\ldots,n\}$ mit |A|=k. Sei $(\bar{a}_t)_{t\geq 1}$ eine Folge von unabhängigen gleichverteilten Zufallsvariablen mit Wertemenge $\{1,\ldots,n\}$. Dann gilt:

$$\min\{t;\bar{a}_t \not\in A\} \quad\text{hat Erwartungswert}\quad 1+\frac{k}{n-k}.$$

Beweis: WS$(\bar{a}_1,\ldots,\bar{a}_r \in A$ und $\bar{a}_{r+1} \not\in A)=\left(\frac{k}{n}\right)^r \cdot (1-\frac{k}{n})$.
Also ist der Erwartungswert für min$\{t;\bar{a}_t \not\in A\}$:

$$\begin{split} &1 + \sum^{\infty}_{r=0} r\left(\frac{k}{n}\r... ...frac{k}{n}}{1-\frac{k}{n}} \\ &= 1+\frac{k}{n-k} \end{split}$$

$\Diamond$

Anmerkung:

$$\sum^{\infty}_{r=0}rz^{r-1}=\frac{d}{dz}\frac{1}{1-z}=\frac{1}{(1-z)^2}$$

Lemma: Sei $(\bar{a}_t)_{t\geq 1}$ wie oben, $k \leq \frac{n}{2}$. Dann hat min$\{t;\vert\bar{a}_1,\bar{a}_2,\ldots,\bar{a}_t\vert\gt k\}$ Erwartungswert $\leq \frac{3}{2} (k+1)$.

Beweis: Wegen der Additivität des Erwartungswertes gilt: Der gesuchte Erwartungswert ist

$$\begin{split} \leq & \sum^{k}_{\nu=0}\left(1+\frac{\nu}{n-\... ... k+1+\frac{k(k+1)}{n} \\ \leq & \frac{3}{2}(k+1) \end{split}$$

$\Diamond$

Wenn wir jedes $L_{\sigma(\nu)}$ in sich zufällig permutieren, erhalten wir eine Folge $(\bar{a}_t)_{t\geq 1}'$ von Zufallsvariablen, so daß

$$\vert\{a_1, \ldots, a_t\}\vert = \vert\{a_1', \ldots, a_t'\}\vert \text{ f\uml {u}r } t = \text{h}(\nu), \forall \nu$$

Da die a_t' innerhalb eines jeden Intervalls h$(\nu) < t \leq \text{h}(\nu + 1)$ paarweise verschieden sind, gilt für sie die vorhergehende Abschätzung erst recht. Daher sind $(\vert S_1(t)\vert)_{t\geq 1}$ und $(\vert S_1(t)'\vert)_{t\geq 1}$ gleichverteilte Folgen von Zufallsvariablen, denn dies gilt zunächst für alle Zeitpunkte der Form $t=\text{h}(y)$; da aber für diese Zeitpunkte S₁(t) = S₁'(t) ist, und $\text{h}()$ zufällig verteilt ist, ist auch die Verteilung der beiden Folgen zwischen diesen Intervallgrenzen identisch.

Sei s der Erwartungswert und sei |S_i| die tatsächliche Größe von S_i nach der Phase 1. Dann

$$s=\sum^{\left\lfloor\frac{n}{2}\right\rfloor + 1}_{k=1}k \cdot \text{WS}(\vert S_i\vert=k)$$

Die erwartete Anzahl der Schritte (und damit die Kosten) in der BFS sei q. Dann gilt:

$$q \leq \sum^{\left\lfloor\frac{n}{2}\right\rfloor + 1}_{k=1}\text{WS} (\vert S_i\vert=k)\frac{3}{2}k = \frac{3}{2}s.$$

Also ist der Aufwand des Algorithmus für die Phasen 1 und 2 im Erwartungswert $\leq 3sn$. Da ns=m^*, und da die Kosten der anderen Phasen offensichtlich durch $\mathcal{O}(n+m+m^*)$ beschränkt sind, folgt die Behauptung. $\Diamond$