Graphentheorie (Vorlesung)

Der knoten- und kantengefärbte Petersen-Graph.

Die Graphentheorie gilt als ein Teilgebiet der Kombinatorik. Betrachten wir Graphen als Darstellung komplexer Systeme, so beantwortet die Graphentheorie Fragen nach notwendigen und hinreichenden Eigenschaften, damit gewisse und erwünschte Strukturen im System vorhanden sind.

Allgemeinhin wird Leonhard Eulers Arbeit aus dem Jahre 1736 zum "Königsberger Brückenproblem" als Geburtsstunde der Graphentheorie als eigenständigem Gebiet der Mathematik betrachtet. Hier ging es um die Frage, ob ein bestimmter Graph einen Pfad hat, der alle Kanten genau einmal durchläuft. Euler gab eine genaue Charakterisierung aller Graphen mit dieser Eigenschaft an.

Vorlesungsinhalt

Wir werden uns fast ausschließlich mit ungerichteten Graphen beschäftigen. Wir werden wichtige Begriffe aus der Graphentheorie kennenlernen und untersuchen. Alle diese Begriffe haben große Bedeutung in praktischen Anwendungen.

Wichtige Themen der Vorlesung werden sein:

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

Voraussetzungen

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

Termine

Vorlesungmontags, 12 Uhr c.t.H 7erstmals: 17. Oktober
Übungfreitags, 12 Uhr c.t.H 7erstmals: 21. Oktober

Dozent

Daniel Meister