Beschreibung: Viele graphentheoretische Probleme lassen sich auf planaren Graphen besser lösen. Das Seminar soll klären, warum dies der Fall ist. Dazu werden zunächst einige grundlegende kombinatorische Eigenschaften planarer Graphen besprochen. Daran schließt sich die Frage an, wie man testet, ob ein gegebener Graph planar ist. Ist der Graph planar, möchte man ihn natürlich gerne so aufzeichnen, daß sich keine Kanten überschneiden. Wie macht man das? Ist der Graph nicht planar, so stellt sich die Frage nach einem größten planaren Teilgraphen. Danach soll für eine Reihe von Problemen diskutiert werden, wie sie auf planaren Graphen effizienter oder (qualitativ) besser gelöst werden können, z.B. Färbung von Knoten und Kanten, Handlungsreisendenproblem, Finden von kantendisjunkten Pfaden etc.
Zeit und Ort: Di 16-18, N102
Beginn: 1. Woche
Vorbesprechung: Donnerstag 3.07.97, 13.00 Uhr, N102
Bereich: A/C
Voraussetzungen: Vordiplomkenntnisse im Bereich Algorithmen und Datenstrukturen
Nachfolge-/Begleitveranstaltungen: keine
Vortragsmodus: Einzelvortrag, Ausarbeitung
Plätze: 16
Literatur:
Buchkapitel und Zeitschriftenartikel
Die Themenliste kann hier
abgerufen werden.