Die Vorlesung beschäftigt sich mit diversen Problemen aus der Graphentheorie und Algorithmen zur Lösung dieser, u.A.:

• Bäume
  • Suchbäume
  • Bäume kleinsten Gewichtes
  • Das Traveling-Salesman-Problem
• Matchings
  • Matchingins in bipartiten Graphen
  • Faktorsätze
• Flüsse
• Färbungen
  • Greedy-Färbungen
  • Komplexität von Färbungsproblemen

Teilweise überschneiden sich die Inhalte der Vorlesungen mit denen aus Effiziente Algorithmen. Damit können die Inhalte der jeweils anderen Vorlesung gut als Ergänzung bzw. genauere/andere Erklärung zum besseren Verständnis genutzt werden.

Die meisten Übungsaufgaben beginnen mit den Worten „Man zeige“. Zu den Übungsterminen wird erwartet, dass die Aufgaben bereits zuhause vorbereitet und gelöst wurden und dass Lösungen nur noch vorgestellt werden. Zudem gibt es die Möglichkeiten, Fragen und Verständnisprobleme zu klären.

• Material Graphen und Algorithmen WS 2023/24

• Reinhard Diestel, Graphentheorie