Prof. Dr. R. Laue                                                                            WS0001
                                Graphentheoretische Optimierung
                                Übungsblatt 5
                                Abgabe: 24.11. vor der Vorlesung

URL:         /axel/graph_ws0001_blatt5.html
 

Aufgabe 9- bcc Teil 1 - (4 Punkte)

Ein ungerichteter Graph G=(V,E) heißt zweifach zusammenhängend, wenn G\v für jeden Knoten v aus V zusammenhängend ist. Eine Zweifachzusammenhangskomponente (bcc) ist ein maximaler zweifach zusammenhängender Teilgraph.

Beweisen Sie folgendes Lemma:
Seien G1=(V1,E1) .... Gm=(Vm,Em) die bcc des Graphen G=(V,E). Dann bilden die Kantenmengen E1, ..., Em eine Partition von E, d.h. sie sind paarweise disjunkt und die Vereinigung ist E.
 
 

Aufgabe 10 - BWin - bcc  (2 Punkte)


Unter diesem Link kann man eine Karte des deutschen BWin Netzes anschauen.
Ist das Netz der BWin Knoten (rote Knoten) zweifachzusammenhängend? Was bedeutet dies für die Ausfallsicherheit?