4.1 Zusammenhangskomponenten

Wir ersetzen jede ungerichtete Kanten $\{u,v\}$ durch zwei gerichtete $(u,v)$, $(v,u)$.

1. Jeder Knoten $u$ hat eine "Farbe" $f(u)$; es gilt zu jedem Zeitpunkt: wenn $f(u)=f(v)$, dann gibt es einen Pfad von $u$ nach $v$. Für eine Farbe $c$ sei $V_c:=\{u\in V|f(u)=c\}$; wir nennen $V_c$ ein Fragment.
2. Pro Phase reicht jede Kante $(u,v)$ einen "Umfärbe-Vorschlag" $(f(u),f(v))$ ein, falls $f(u)\ne f(v)$ ist. Die Interpretation ist: die Kante $(u,v)$ schlägt vor, alle Knoten mit Farbe $f(u)$ umzufärben in Farbe $f(v)$. Nun soll pro Farbklasse der kleinste Vorschlag gewinnen:

   

   Im obigen Beispiel reicht Kante $(u,v)$ den Vorschlag Farbe 2 soll durch 8 ersetzt werden ein; dieser Vorschlag gewinnt jedoch nicht, weil er durch Farbe 2 soll durch 3 ersetzt werden ausgestochen wird. Wie implementieren wir diese Minimum-Operation?
3. Jede Kante $(u,v)$ erstellt einen Vorschlag und schreibt diesen in eine dezidierte Zelle. Falls jedoch $f(u)=f(v)$ ist, so wird kein Vorschlag eingereicht. Im obigen Beispiel erhalten wir die Vorschläge

   [(7,8), (7,8), (8,7), (8,7), (8,9), (8,2), (2,8), (2,3), (3,2), (3,6), (3,6), (6,3), (6,5), (6,3), (6,4), (5,6), (5,6), (4,8), (4,6)]

   Wir sortieren die Umfärbe-Vorschläge $(c_1,c_2)$ lexikographisch:

   [(2, 3), (2, 8), (3, 2), (3, 6), (3, 6), (4, 6), (4, 8), (5, 6), (5, 6), (6, 3), (6, 3), (6, 4), (6, 5), (7, 8), (7, 8), (8, 2), (8, 7), (8, 7), (8, 9)]

   Um nun pro Fragment das Minimum zu bestimmen, betrachtet jeder Prozessor "seine" Zelle im Array und die links davon. So kann er feststellen, ob "seine" Zelle den Beginn eines Fragments markiert. Falls nicht, so wird der Vorschlag gestrichen:

   [(2, 3), (2, 8), (3, 2), 3, 6), 3, 6), (4, 6), 4, 8), (5, 6), 5, 6), (6, 3), 6, 3), 6, 4), 6, 5), (7, 8), 7, 8), (8, 2), 8, 7), 8, 7), 8, 9)]

   Es bleiben also folgende Vorschläge übrig:

   [(2, 3), (3, 2), (4, 6), (5, 6), (6, 3), (7, 8), (8, 2)]

   Die Menge der Paare bildet eine binäre Relation $P$ auf der Menge der unvollständigen Farbklassen; in der Tat gibt es für eine unvollständige Farbklasse $c$ genau ein $c^{\prime }$ mit $(c,c^{\prime })\in P$. Die Relation $P$ ist also eine Funktion, und wir schreiben $c^{\prime }=P(c)$ für dieses eindeutige $c^{\prime }$. Die Funktion $P$ lässt sich graphisch als gerichteter Graph darstellen:

   

4. Diese Vorschläge definieren ihrerseits einen gerichteten Graphen $H$ auf den Fragmenten. Vollständige Fragmente, also solche, die bereits eine ganze Zusammenhangskomponente sind, sind in $H$ isolierte Knoten. Andere, nicht vollständige Fragmente, haben genau eine ausgehende Kante. Für ein Fragment $c$ bezeichne $p(c)$ den Zielknoten dieser ausgehenden Kante. Wie kann nun dieser Graph aussehen?
5. Generell: wenn Sie eine Funktion $p:X\to X$ und den gerichteten Graphen $H=(X,\{(u,p(u))|u\in X\})$ betrachten, so hat $H$ eine sehr spezielle Struktur: eine Menge gerichteter Zyklen und eine Menge von Bäumen, die an den Zyklen-Knoten hängen. In unserem Falle ist die Struktur noch spezifischer: jeder solche Zyklus hat Länge 2. Länge $1$ ist nicht möglich, weil dann ja $p(c)=c$, was nicht geht, weil ein Vorschlag $(c,c)$ gar nicht eingereicht worden wäre. Dass Zyklen der Größe 3 oder mehr nicht existieren, ist nicht so offensichtlich.

   Um zu sehen, dass dies gilt, sei $Z$ ein Zyklus aus mindestens drei Farbklassen und sei $c$ die kleinste auf diesem Zyklus. Sei $c^{\prime }=p(c)$ und $c^{″}=p(c^{\prime })$. Woher kommt nun der "Vorschlag" $(c,c^{\prime })$? Dieser kommt ja von einer Kante $(u,v)$ mit $f(u)=c$ und $f(v)=c^{\prime }$. Da unser Graph jedoch ungerichtet ist, gibt es auch $(v,u)$, welche den Vorschlag $(c^{\prime },c)$ einreicht. Für $c^{\prime }$ gewinnt also ein Vorschlag, der höchstens $c$ ist, und somit gilt $p(c^{\prime })\le c$. Laut Annahme unseres Zykels ist jedoch $p(c^{\prime })=c^{″}>c$.

   Wir schließen: der Graph $H$ besteht aus Zweierzyklen, an denen zum Zyklus gerichtete Bäume hängen.

6. Jeder Pseudo-Baum hat also genau zwei Wurzeln. Jeder Knoten $c$ kann parallel in einem Schritt feststellen, ob er eine Wurzel ist (falls $p(p(c))=c$), und falls ja, ob er von den beiden Wurzeln der kleinere ist $c<p(c)$ . Falls ja, setzt er $p(c)=c$. Jetzt haben wir also eine Menge von zur Wurzel gerichteten Bäumen mit Selbstschleife an der Wurzel.
7. Jetzt betreiben wir $\log n$ Runden von Pointer Jumping: jede Farbklasse $c$ setzt also $p(c):=p(p(c))$. Nach $\log n$ solchen Jumping-Schritten deutet $p(c)$ auf die Wurzel. Jeder Baum ist nun also zu einem Stern (mit Selbstschleife an der Wurzel) geworden.
8. Jetzt färben wir um: $f(u):=f(p(u))$.
9. Wieviele Phasen brauchen wir? Jedes unvollständige Fragment ist Teil eines Baumes von mindestens 2 Knoten. Jeder Baum wird nach Umfärben zu einem Fragment. Die Anzahl der unvollständigen Fragmente halbiert also mindestens.

Laufzeit $O({\log }^{2}n)$.

Randomisierte Variante

Auf einer CRCW-PRAM mit Arbitrary-Rule (d.h. bei Schreibkonflikten gewinnt ein beliebiger Prozessor), kann die Kante $(u,v)$ ihren Vorschlag $(f(u),f(v))$ direkt in die Speicherzelle $p[f(v)]$ Schreiben. Für jedes unvollständige Fragment $c$ gibt es nun also einen Wert $p[c]$. Dies definiert wiederum einen gerichteten Graphen mit Raus-Grad höchstens $1$. Dieser kann nun aber lange Zyklen haben, und das Tie-Breaking zwischen den beiden Wurzeln geht nicht mehr. Irgendeine Lösung, in der sich manche Knoten selbst zu Wurzeln erklären, geht zwar irgendwie, aber das Pointer Jumping würde immer noch $\log n$ Schritte pro Phase benötigen.

Wir gehen einen anderen Schritt: jede Farbklasse $c$ wählt ein Bit $b_c$. Kanten $(c,c^{\prime })$ werden nur behalten, wenn $b_c=1$ und $b_{c^{\prime }}=0$ ist; alle anderen werden gelöscht. Der verbleibende Digraph besteht nun aus isolierten Knoten und Sternen. Jede Kante überlebt mit Wahrscheinlichkeit $1/4$ und somit verschwindet jede unvollständige Farbklasse mit Wahrscheinlichkeit $1/4$. Somit nimmt die Anzahl der unvollständigen Fragmente im Erwartungswert um einen Faktor von $3/4$ ab. Vor Phase 1 ist die Anzahl unvollständiger Fragmente höchstens $n$. Nach $t$ Phasen ist sie im Erwartungswert höchstens

$$\begin{array}{r}{\left(\frac{3}{4}\right)}^t\cdot n.\end{array}$$

Nach $2\cdot {\log }_{4/3}n$ Phasen ist sie höchstens $\frac{1}{n^2}\cdot n=\frac{1}{n}$.