Graphentheorie (Vorlesung)

Der knoten- und kantengefärbte Petersen-Graph.

Einführung

Die Graphentheorie ist ein Teilgebiet der Kombinatorik. Innerhalb der Informatik läßt sich die Graphentheorie auch als eine Art "Strukturtheorie" verstehen, die Fragen über die Existenz und Nichtexistenz spezieller Strukturen stellt und beantwortet. Viele praktische Probleme, die mit Hilfe von Rechnern gelöst werden sollen, sind spezielle Graphprobleme oder lassen sich leicht als solche modellieren. Kenntnisse über Strukturen in den Eingaben helfen, effiziente Algorithmen zur Lösung zu entwickeln.

Vorlesungsinhalt

Wir werden uns im wesentlichen mit ungerichteten Graphen beschäftigen. In einem längeren ersten Teil der Vorlesung werden wir wichtige (Grund-)Begriffe aus der Graphentheorie kennenlernen und untersuchen. Alle untersuchten Begriffe haben große Bedeutung auch in praktischen Anwendungen, als da viele klassische algorithmische Probleme wären. Die Themen aus dem ersten Teil der Vorlesung:

  • Bäume und Zusammenhang
  • Euler- und Hamilton-Kreise
  • Knoten- und Kantenfärbungen
  • Matchings.

In einem kürzeren zweiten Teil der Vorlesung werden wir einige spezielle Themen der Graphentheorie untersuchen, zum Beispiel:

  • planare Graphen
  • perfekte Graphen
  • Expandergraphen.

Voraussetzungen

Außer den üblichen Voraussetzungen über die Kenntnis grundlegender Begriffe aus den Einführungsveranstaltungen zur Informatik, wie Grundlagen der Theoretischen Informatik I oder Diskrete Strukturen, werden keine Spezialkenntnisse vorausgesetzt. Alle Begriffe werden in der Vorlesung definiert.