Vorlesung Graphentheoretische Algorithmen

Günter Rote

Wintersemester 2001/02, 3+2 Stunden
7 ECTS-Leistungspunkte (Informatik), 8 ECTS-Leistungspunkte (Mathematik)

Graphen und Netzwerke sind ein wichtiges Darstellungsmittel für alle möglichen Strukturen in Anwendungen aus der Informatik und aus der Wirklichkeit. Viele Optimierungsaufgaben können als graphentheoretische Probleme formuliert werden. Der Bereich der Graphenalgorithmen ist neben den geometrischen Algorithmen ein wichtiges und grundlegendes Teilgebiet der algorithmischen Informatik.

Ich werde einerseits einen möglichst breiten Überblick über das Feld der Graphenalgorithmen geben, aber auch bei einzelnen Kapiteln in die Tiefe gehen.

Geplanter Inhalt:

  1. Kürzeste Wege. Den kürzesten Weg von A nach B zu finden, ist ein grundlegendes algorithmisches Problem in der Graphentheorie. Die Verfahren Breitensuche und Tiefensuche zum Absuchen eines Graphen und zur Bestimmung von Zusammenhangskomponenten gehören in diesen Zusammenhang.
  2. Heuristische Suchalgorithmen. Das Lösen von Rätseln und Denksportaufgaben lässt sich oft als das Finden eines Lösungsweges oder eines Ausweges interpretieren. Verschiedene Lösungsverfahren aus dem Bereich der künstlichen Intelligenz sind Varianten von kürzesten-Wege-Algorithmen.
  3. Verallgemeinerte Wegprobleme. Auch Probleme, die auf den ersten Blick nichts mit Graphen zu tun haben, wie das Invertieren einer Matrix, lassen sich als Wegprobleme auffassen und lösen.
  4. Kürzeste spannende Bäume. Hier geht es um ein möglichst kurzes Netz, das eine gegebene Menge von Knoten verbindet.
  5. Matroide und der gierige Algorithmus. Der einfache Algorithmus zur Bestimmung kürzester spannender Bäume kann auf viele andere Situationen angewendet werden.
  6. Steinerbäume. Wenn man die Aufgabenstellung, ein möglichst kurzes zusammenhängendes Netz zu finden, leicht verändert, ist die optimale Lösung viel schwieriger zu ermitteln.
  7. Flüsse und Schnitte in Netzen. Flussprobleme sind neben Wegeproblemen die zweite wichtige Problemklasse bei Graphen. Ich möchte die schönen theoretischen Grundlagen sowie einige einfachere und schwierigere Lösungsverfahren vorstellen. Überraschend viele andere Aufgaben lassen sich auf Flüsse und Schnitte zurückführen.
  8. Paarungen und Zuordnungen. Gegebene Objekte sollen möglichst gut zu Paaren zusammengefasst werden. Auch das sogenannte chinesische Briefträgerproblem kann mittels optimaler Paarungen gelöst werden.
  9. Das Rundreiseproblem. Beim bekannten Rundreiseproblem ist eine kürzeste Tour durch eine gegebene Menge von Städten gesucht.
  10. Färbungen und Cliquen. Färbungsprobleme sind im Zusammenhang mit dem Vierfarbenproblem bekannt. Zur Bestimmumg guter Färbungen und großer Cliquen gibt es Heuristiken.
  11. Zeichnen von Graphen; Planarität. Graphen, die nur im Computer gespeichert sind, sind dem bloßen Auge nicht zugänglich. Daher ist es wichtig, sie in zwei (oder drei) Dimensionen schön darzustellen, um ihre Struktur sichtbar zu machen. Besonders einfach sind planare Graphen, die sich ohne Kreuzungen in der Ebene zeichnen lassen.

Voraussetzungen:

Grundlegende Begriffe aus der Graphentheorie (Bäume, Kreise, etc.) sollen bekannt sein. Grundkenntnisse über lineare Optimierung, Komplexitätstheorie (NP-Vollständigkeit) oder elementare Datenstrukturen zur Speicherung von Graphen im Computer sind hilfreich, aber nicht notwendig. Ich werde den Kenntnisstand der TeilnehmerInnen am Anfang erheben und gegebenenfalls alles Notwendige selbst darstellen, oder den Inhalt der Vorlesung entsprechend anpassen.

Literatur: