Prof. Dr. R. Laue                                                                            WS0203
                                Graphentheoretische Optimierung
                                Übungsblatt 3
                                Abgabe: Aufgabe bis Donnerstag 7.11.02 12.00 Raum 736 Mathe NW2

URL:         /axel/graph_ws0203_blatt3.html
 

Aufgabe 6 - (3+3 Punkte)

Berechnen Sie den Zeitaufwand für DFS und BFS als Funktion der Anzahl der Knoten und Kanten des Graphen.


Aufgabe 7 - Turnier / Hamilton Weg (3+6 Punkte)

Ein Turnier ist ein gerichteter Graph, in dem je zwei verschiedene Knoten durch genau eine Kante verbunden sind.
Zeichen Sie alle (=4) Turniere mit 4 Teilnehmern.
Beweisen Sie, dass es in jedem Turnier einen gerichteten Weg gibt, der durch alle Knoten führt. So ein Weg heisst Hamilton Weg.