Prof. Dr. R. Laue                                                                            WS0203
                                Graphentheoretische Optimierung
                                Übungsblatt 9
Abgabe: bis Donnerstag 16.1.03 12.00 Raum 736 Mathe NW2

URL:         /axel/graph_ws0203_blatt9.html
 


Aufgabe 18 bcc - letzter Teil - (6 Programmier Punkte)


Abgabe: 16.1. per email
Implementieren Sie den bcc Algorithmus. Ergebnis soll eine C routine bcc(int *nbl, int **bcc) sein, die eine Nachbarschaftsliste übergibt und in der Routine ein array  allociert das die Länge = Anzahl Kanten hat und zu den Kanten die Nummer der bcc (0,1,....) notiert.


Bei den beiden folgenden Aufgaben geht es um diesen gerichteten Graphen mit Kantenlängen
fehlt hier was?
Aufgabe 19 Wegealgebra (2+2+4 Punkte)

Finde die kürzesten Wege von jedem Knoten zum Knoten 4.
Formuliere dazu eine Wege Algebra und eine zu lösende Gleichung (2 Punkte)
Ist die Matrix A (wie schaut die aus?) absorbierend? (2 Punkte)
Löse die Aufgabe mit dem Gauss-verfahren. (4 Punkte)



Aufgabe 20 Wegealgebra (6+2 Punkte)
Formulieren Sie den Dijkstra Algorithmus für Wege Algebren.
(6 Punkte). Lösen Sie obige Aufgabe mit dem neuen Algorithmus. (2 Punkte)