Prof. Dr. R. Laue                                                                            SS2005
Dr. A. Kohnert
                                Diskrete Algorithmen
                                Übungsblatt 7
                                Besprechung 10.6.05

URL:         /axel/disc_ss05_blatt7.html

Abgabe zu Beginn der Übung.



Aufgabe 12- bcc Teil 2 - (2+4 Punkte)


Auf unserem Weg zum Algorithmus für bcc definieren wir:

Sei G ein zusammenhängender Graph ohne Schleifen. Das Zentrum der bcc sei der Knoten mit der zweitkleinsten DFSNUM. Bei Verwendung der Notation (T,F,B,DFSNUM, FATHER) aus dem DFS Algorithmus definiert man ähnlich wie bei der Einfachzusammenhangskomponente:

LOWPT[v]= min { DFSNUM[v]  {DFSNUM[z] | ex ein Knoten w mit v  --T*> w  --B> z}}

Beweisen Sie folgendes Lemma:

1) LOWPT[v] <= DFSNUM[FATHER[v]] für alle v mit DFSNUM[v] >=2

2) v ist Zentrum einer bcc  <==> LOWPT[v] = DFSNUM[FATHER[v]] und DFSNUM[v] >= 2

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

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