Prof. Dr. R. Laue                                                                            WS0203
                                Graphentheoretische Optimierung
                                Übungsblatt 2
                                Abgabe: Aufgabe 4+5 bis Donnerstag 31.10.02 12.00 Raum 736 Mathe NW2

Aufgabe 3 bis 15.11. Abgabe per email an kohnert@uni-bayreuth.de

URL:         /axel/graph_ws0203_blatt2.html
 

Aufgabe 3 - (Programmieren 4 Punkte in 3er Gruppen)


Implementieren Sie in C/C++ den Algorithmus für die Berechnung einer Euler Tour.  Die abzugebende Routine eulertour()
soll drei Parameter haben 

1. Parameter: die Nachbarschaftsliste als *int (siehe hierzu die Dokumentation )

2. Parameter: die Knotennummer des Startknotens, vom Typ int.

3. Parameter: das Ergebnis wird ein int Vektor, der die Knoten enthält wie sie nacheinander besucht werden. Die Länge dieses Vektors wird die Anzahl der Kanten sein. Er wird innerhalb der Routine allokiert, also vom Typ int**.

Details zu dieser Aufgabe werden in der Übung besprochen.


Aufgabe 4 - (2+2 Punkte)

Zeichnen sie die beiden resultierenden Bäume für den DFS und BFS Durchlauf am Beispiel des 4-dimensionalen Hyperwürfels. 


Aufgabe 5 - Topologisch Sortieren (4 Punkte)

Sortieren Sie den Graphen des Teilerverbands von 5! topologisch. Eine Kante geht dabei vom Knoten i zum Knoten j falls j in i maximaler Teiler ist.