3. Übungsblatt - ZAIK - Universität zu Köln

Universität zu Köln
Institut für Informatik
Dr. O. Schaudt
A. van der Grinten
Übung zu Parallele Algorithmen
Blatt Nr. 3
Dieses Übungsblatt muss bis zum 05.05.2016, 15:30 abgegeben werden. Schreiben Sie Ihren Namen
und Ihre Übungsgruppe oben auf die Abgabe!
Aufgabe 1: Zusammenhangskomponenten (15 Punkte)
(a) Wenden Sie den Algorithmus zum Berechnen von Zusammenhangskomponenten aus der Vorlesung auf das nachfolgende Beispiel an. Geben Sie dazu sinnvolle Zwischenschritte an. (8 Punkte)
7
4
3
1
2
6
5
9
8
(a) Zeigen Sie: Nach Schritt 1 und 2 des Algorithmus kann, in dem durch T definierten Digraphen,
von jedem Knoten aus höchstens ein (einfacher) Kreis erreicht werden. Weiterhin haben alle
Kreise in diesem Graphen die Länge 1 oder 2. (7 Punkte)
Aufgabe 2: Transitive Reduktion (15 Punkte)
Sei G ein gerichteter Graph. Die transitive Reduktion T (G) von G ist ein minimaler (bzgl. der Anzahl
der Kanten) Graph, so dass ein Weg von u nach v in T genau dann existiert, wenn er auch in G
existiert.
(a) Sei G azyklisch. Zeigen Sie, dass T (G) ein Teilgraph von G und eindeutig ist. Gilt dies allgemein?
(5 Punkte)
(b) Konstruieren Sie einen Algorithmus, der die transitive Reduktion eines azkylischen, gerichteten
2
n3
Graphen mit O( log
n ) Prozessoren in Zeit O(log n) berechnet. (10 Punkte)
Aufgabe 3: Eulerkreise in K5 (10 Punkte)
Berechnen Sie die Anzahl der Eulerkreise in K5 . Tipp: Wie setzt sich ein Eulerkreis in K5 aus einfachen
Kreisen zusammen?
1

Download Report