6. Übungsblatt - ZAIK

Universität zu Köln
Institut für Informatik
Dr. O. Schaudt
A. van der Grinten
Übung zu Parallele Algorithmen
Blatt Nr. 6
Dieses Übungsblatt muss bis zum 02.06.2016, 15:30 abgegeben werden. Schreiben Sie Ihren Namen
und Ihre Übungsgruppe oben auf die Abgabe!
Aufgabe 1: 2-ZHKs (15 Punkte)
Wenden Sie den Algorithmus zum Finden von 2-ZHKs auf folgenden Graphen an:
Aufgabe 2: Eulerkreise in allgemeinen Graphen (10 Punkte)
Zeigen Sie die in der Vorlesung unbewiesene Behauptung, dass die Arrays EDGE und SUCC zusammen
den Graphen in Zykel partitionieren.
Aufgabe 3: Färben von Bäumen (15 Punkte)
Sei G ein Graph. Eine k-Knoten-Färbung (oder nur k-Färbung) von G ist eine Abbildung c : V (G) →
{1, . . . , k}, so dass es keine Kante u − v mit c(u) = c(v) gibt. Das minimale k, so dass eine k-Färbung
von G existiert, heißt chromatische Zahl von G.
Eine k-Kanten-Färbung ist eine Abbildung c : V (E) → {1, . . . , k}, so dass für keine zwei Kanten u − v
und u − w gilt: c(u − v) = c(u − w).
Sei im folgenden G ein Baum. Sei ∆ der maximale Grad eines Knoten in G.
(a) Sei |V (G)| > 1. Zeigen Sie: Die chromatische Zahl von G ist 2. (2 Punkte)
(b) Konstruieren Sie einen paralellen Algorithmus, der eine 2-Färbung von G mit O(n) Prozessoren
in O(log n) Zeit bestimmt. (4 Punkte)
(c) Zeigen Sie, dass ∆ Farben für eine Kantenfärbung von G ausreichen. (Offensichtlich sind ∆
Farben auch notwendig) (3 Punkte)
(d) Konstruieren Sie einen Algorithmus, der eine ∆-Kanten-Färbung von G mit O(n) Prozessoren
in Zeit O(log n) berechnet.
Hinweis: Stellen Sie sich eine Tiefensuche in G vor. Wir bezeichnen für jede Kante v − u den
Index, in der die Kante v − u von v aus besucht wird mit d(v − u). Sei nun r die Wurzel des
DFS-Baums und sei r =: w0 − w1 − . . . − wl ein Pfad. Was gilt für d(w0 − w1 ) + d(w1 − w2 ) +
. . . + d(wl−1 − wl ) mod ∆? (6 Punkte)
1

Download Report