Transcript
Universit¨ at zu K¨ oln Institut f¨ ur Informatik Dr. O. Schaudt A. van der Grinten
¨ Ubung zu Parallele Algorithmen Blatt Nr. 6 ¨ Dieses Ubungsblatt muss bis zum 02.06.2016, 15:30 abgegeben werden. Schreiben Sie Ihren Namen ¨ und Ihre Ubungsgruppe 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: F¨ arben von B¨ aumen (15 Punkte) Sei G ein Graph. Eine k-Knoten-F¨ arbung (oder nur k-F¨arbung) 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-F¨arbung von G existiert, heißt chromatische Zahl von G. Eine k-Kanten-F¨ arbung ist eine Abbildung c : V (E) → {1, . . . , k}, so dass f¨ ur 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-F¨arbung von G mit O(n) Prozessoren in O(log n) Zeit bestimmt. (4 Punkte) (c) Zeigen Sie, dass ∆ Farben f¨ ur eine Kantenf¨arbung von G ausreichen. (Offensichtlich sind ∆ Farben auch notwendig) (3 Punkte) (d) Konstruieren Sie einen Algorithmus, der eine ∆-Kanten-F¨arbung von G mit O(n) Prozessoren in Zeit O(log n) berechnet. Hinweis: Stellen Sie sich eine Tiefensuche in G vor. Wir bezeichnen f¨ ur 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 f¨ ur d(w0 − w1 ) + d(w1 − w2 ) + . . . + d(wl−1 − wl ) mod ∆? (6 Punkte)
1
