|
Universität Bonn
Institut für Informatik V
Prof. Dr. N. Blum, M. Nikolaidou, C. Rick
Seminar Planare Graphen: Theorie und Algorithmen
(WS 1999/2000)
Inhalt:
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.
Themenübersicht:
- Graphentheoretische Grundlagen (Euler, Kuratowski), 26.10.1999
- Graphentheoretische Grundlagen (Dualität), 2.11.1999
- Planaritätstest (Vertex-Addition), 9.11.1999
- Zeichnen Planarer Graphen (konvex), 16.11.1999
- Zeichnen Planarer Graphen (Gitter), 23.11.1999
- Knotenfärbung, 30.11.1999
- Unabhängige Knotenmengen, 7.12.1999
- Isomorphismustest, 14.12.1999
- Aufzählen von Teilgraphen, 11.1.2000
- Planare Seperatoren, 18.1.2000
- Maximale Schnitte, 25.1.2000
- Kantendisjunkte (s,t)-Pfade, 1.2.2000
Alle Kurzbeschreibungen als zip-Datei.
Seminartermin:
jeweils Dientags, 16-18 Uhr, N102
Bereich:
A/C
Vorbesprechung:
Dienstag, 29. Juni 1999, 16 c.t., N102
Voraussetzungen:
Vordiplomkenntnisse im Bereich Algorithmen und Datenstrukturen
(insbesondere Graphenalgorithmen)
Vortragsmodus:
Vortragsausarbeitung, Einzelvortrag
Plätze:
14
Literatur:
Buchkapitel und Zeitschriftenartikel
Tips zur Vorbereitung eines Seminarvortrags:
- Regeln speziell für unser Seminar
- Student Speakers Guide
Universität Bonn
/
Informatik
/
Abteilung V
15.07.99 - rick@informatik.uni-bonn.de
|