Prof. Dr. R. Laue                                                                            WS0001                                 Graphentheoretische Optimierung
                                Übungsblatt 7
                                Abgabe: 8.12 vor der Vorlesung

Aufgabe 13 - Autokauf (4 Punkte)

Wir wollen möglichst kostengünstig zu einem fahrbaren Untersatz kommen. Es soll ein ROVER 214 i sein. Aus der Schwacke Liste
bekommen wir folgende Information:

Neupreis	23990
1 Jahr alt	12000
2 Jahre alt	11000
3 Jahre alt	9500
4 Jahre alt	8000

An Reperaturkosten setzen wir DM 1000 * Alter (d.h. im ersten Jahr 1000) an. Stellen Sie die Wegealgebra auf, und zeigen Sie wie Sie am günstigsten für drei Jahre zu einer Fahrgelegenheit in Ihrem Traumauto kommen.

Aufgabe 14- bcc Teil 3 - (4+2 Punkte)

Auf unserem Weg zum Algorithmus für bcc beweisen wir zwei weitere Aussagen:

Sei G=(V,E) ein ungerichteter Graph ohne Schleifen. Seien T,F,B,DFSNUM,FATHER, LOWPR wie in Aufgabe 12 definiert.

Es gilt:

1) Sei G'=(V',E') ein bcc von G mit Zentrum v. Dann ist

V'={FATHER[v] w; wobei für w gilt: es ex ein Weg von v nach w mit Kanten aus T und kein Knoten ausser v auf diesem Weg ist Zentrum}

2) Es gilt: LOWPT[v] = min(
                            { DFSNUM[v] }
                            { DFSNUM[z] mit (v,z) B}
                            { LOWPT[u] mit (v,u) T}
                                            )
     für alle v aus V