Prof. Dr. R. Laue                                                                            WS0203
                                Graphentheoretische Optimierung
                                Übungsblatt 5
                                Abgabe: Aufgabe bis Donnerstag 21.11.02 12.00 Raum 736 Mathe NW2
URL:         /axel/graph_ws0203_blatt5.html
 
 
 

Aufgabe 9 - Abschätzung (4 Punkte)

Beweisen Sie eine obere Schranke für die Kantenzahl schlichter, zusammenhängender, planarer, bipartiter  Graphen, die besser ist als die aus der Vorlesung bekannten 3n-6.        (Tipp: Euler Formel, doppeltes Abzählen)


Aufgabe 10 - Planar (4 Punkte)

Beweisen Sie mittels Kuratowski Theorem, dass der 4-dimensionale Hyperwürfel nicht planar ist.



Aufgabe 11 - Färben (4 Punkte)

Entwerfen Sie einen Algorithmus zum Färben eines planaren Graphen mit maximal 5 Farben. (pseudo -code)