Ein fundamentales Problem für Graphen ist das Berechnen seiner
Zusammenhangskomponenten.
Definition Sei $G = (V,E)$ ein Graph.
Für zwei Knoten $u, v \in V$ schreiben wir $u \rightsquigarrow v$, wenn
es einen Pfad von $u$ nach $v$ gibt. Die Relation
$\rightsquigarrow$ ist reflexiv und transitiv.
Wenn $G$ ungerichtet ist, dann ist $\rightsquigarrow$ eine symmetrische Relation und wir
schreiben $u \leftrightsquigarrow v$. In diesem Falle ist
$\leftrightsquigarrow$ also eine Äquivalenzrelation und partitioniert die Knotenmenge
in Zusammenhangskomponenten $C_1, \dots, C_k$, also
$V = C_1 \cup \dots \cup C_k$,
$C_i \cap C_j = \emptyset$ für $i \ne j$
Wenn $u \in C_i$ und $v \in C_j$ dann gilt
$u \leftrightsquigarrow v$ wenn $i=j$ ist und
$u \not \leftrightsquigarrow v$ wenn $i\ne j$.
Was heißt es nun, Zusammenhangskomponenten zu berechnen?
Problem(Zusammenhangskomponenten berechnen).
Sei $G=(V,E)$ ein Graph, gegeben zum Beispiel als unsortierte Liste seiner
Kanten. Wir nehmen an, dass $V = \{1, \dots, n\}$ gilt. Wir wollen
an Array $[c_1, c_2, \dots, c_n]$ berechnen, so dass $c_i$ der "Name" der
Zusammenhangskomponente vom Knoten $i$. Dass also gilt:
\begin{align*}
c_i = c_j \Longleftrightarrow i \leftrightsquigarrow j
\end{align*}
Fragment Merging
Wir stellen nun den Algorithmus Fragment Merging. Die Idee ist,
dass wir die Knotenmenge in Fragmente partitioniert haben und in jeder Phase
mehrere Fragmente, die mit Kanten verbunden sind, zu einem großen Fragment
verschmelzen. Der Algorithmus endet, wenn keine zwei Fragmente durch
Kanten verbunden sind; dann sind die Fragmente genau die Zusammenhangskomponenten.
Definition Sei $G = (V,E$ ein Graph.
Eine Fragmentfärbung ist eine Funktion $f: V \rightarrow X$ in
eine beliebige Farbmenge $X$, so dass
\begin{align*}
\forall u, v \in V: \ f(u) = f(v) \rightarrow (u \leftrightsquigarrow v) \ .
\end{align*}
In Worten: wenn $u$ und $v$ die gleiche Farbe haben, dann gibt es
einen Pfad von $u$ nach $v$. Für eine Farbe $c \in X$ nennen wir
Es gibt zwei extreme Beispiele für Fragmentfärbungen:
Seien $C_1, \dots, C_k$ die Zusammenhangskomponenten von $G$. Wenn wir
$f(u)$ definieren als dasjenige $i$ mit $u \in C_i$, dann ist $f$ eine
Fragmentfärbung.
Die "triviale" Färbung $f(u) := u$ ist auch eine Fragmentfärbung.
Beachten Sie: wenn es $k$ Zusammenhangskomponenten gibt, dann muss jede
Fragmentfärbung mindestens $k$ Farben verwenden; sie Farbklassen entsprechen
den Zusammenhangskomponenten genau dann, wenn genau $k$ Farben verwendet werden.
Der Algorithmus.
Wir ersetzen jede ungerichtete Kanten $\{u,v\}$ durch zwei gerichtete $(u,v)$, $(v,u)$.
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.
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?
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
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:
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'$ mit $(c,c') \in P$. Die Relation $P$ ist also eine
Funktion, und wir schreiben $c' = P(c)$ für dieses eindeutige $c'$.
Die Funktion $P$ lässt sich graphisch als gerichteter Graph darstellen:
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?
Generell: wenn Sie eine Funktion $p: X \rightarrow 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' = p(c)$ und $c'' = p(c')$.
Woher kommt nun der "Vorschlag" $(c,c')$? Dieser kommt ja von einer Kante
$(u,v)$ mit $f(u) = c$ und $f(v) = c'$. Da unser Graph jedoch ungerichtet ist,
gibt es auch $(v,u)$, welche den Vorschlag $(c', c)$ einreicht. Für $c'$ gewinnt
also ein Vorschlag, der höchstens $c$ ist, und somit gilt $p(c') \leq c$.
Laut Annahme unseres Zykels ist jedoch $p(c') = c'' \gt c$.
Wir schließen: der Graph $H$ besteht aus Zweierzyklen, an denen zum Zyklus gerichtete
Bäume hängen.
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 \lt 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.
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.
Jetzt färben wir um: $f(u) := f(p(u))$.
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')$ werden nur behalten, wenn $b_c = 1$ und $b_{c'} = 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{align*}
\left(\frac{3}{4}\right)^t \cdot n \ .
\end{align*}
Nach $2 \cdot \log_{4/3} n$ Phasen ist sie höchstens $\frac{1}{n^2} \cdot n = \frac{1}{n}$.
Spannbäume
Sei $G = (V,E)$ ein Graph. Ein Spannbaum ist ein Subgraph $(V,F)$ der
alle Knoten von $G$ enthält und ein Baum ist, also azyklisch und
zusammenhängend. Das geht natürlich nur, wenn $G$ zusammenhängend ist.
Andernfalls interessieren wir uns für einen maximalen Wald $(V,F)$,
also einen azyklischen Subgraphen, der maximal in dem Sinne ist, dass
jede weiter Kante $e \in E \setminus F$ einen Zyklus erzeugen würde: dass
also $(V, F')$ azyklisch ist für jedes $F \subsetneq F' \subseteq E$.
Es ist nicht schwer, zu sehen, dass ein Wald genau dann maximal in $G$
ist, wenn er die gleichen Zusammenhangskomponenten hat.
Übungsaufgabe
Zeigen Sie, wie man in $O(\log^2 n)$ Zeit einen maximalen Wald
berechnen kann. Konkret: Sie wollen jede Kante mit $0$ oder $1$
markieren, so dass die mit $1$ markierten Kanten einen
maximalen Wald bilden.
Übungsaufgabe
Zeigen Sie, wie man in $O(\log^2 n)$ Zeit entscheiden kann,
ob ein Graph $G = (V,E)$ bipartit ist!
Ein Graph ist bipartit genau dann, wenn er zweifärbbar ist.
Wenn ich Ihnen einen Spannbaum $(V,F)$ von $G= (V,E$) gebe,
können Sie dann schnell entscheiden, ob $G$ zweifärbbar ist?
Der Baum $(V,F)$ ist natürlich in jedem Falle zweifärbbar...
