Zur Startseite der Abteilung Theoretische Informatik

Graphentheorie (WS 2015/16)

Organisatorisches

Dozenten: Volker Diekert, Manfred Kufleitner

ÜbungenLukas Fleischer

Zeit Raum Termine
Mo 15:45–17:15 0.447 wöchentlich ab 12.10.
Do 15:45–17:15 0.447 wöchentlich (Vorlesung/Übung im Wechsel) ab 15.10.

Die Prüfung im Sommersemester 2016 findet am Freitag, den 14.10.2016, von 11:00 Uhr bis 13:00 Uhr in Raum 0.108 statt.

Die Prüfung im Wintersemester 2016/2017 findet am Freitag, den 28.04.2017, von 14:00 Uhr bis 16:00 Uhr in Raum 1.156 statt.

Vorlesungsinhalte

Die folgenden Themen und Konzepte wurden in der Vorlesung und in den Übungen behandelt:

  • Eulerkreise, Eulerwege, Hamiltonkreise, Satz von Ore
  • Knotengrade, Handschlaglemma, Schubfachprinzip
  • Bäume und Wälder, Cayley-Formel, Prüfer-Codes
  • Planarität, Eulerformel, Satz von Fáry-Wagner, Satz von Thomassen, Satz von Kuratowski, Testen auf Planarität in Polynomialzeit
  • Planare Separatoren, Satz von Lipton-Tarjan, Dualgraph, Berechnung planarer Separatoren in Linearzeit, Anwendungen
  • Färbungen, 3-Färbbarkeit ist NP-vollständig, 3-Färbbarkeit für planare Graphen ist NP-vollständig, 5-Färbbarkeit planarer Graphen, Kantenfärbungen
  • Satz von Hall, Heiratsbedingung, Stabile Heirat nach Gale-Shapley
  • AB-Separatoren, Satz von Menger, k-Zusammenhang, k-Kantenzusammenhang, unabhängige und kantendisjunkte Wege, Testen auf k-Zusammenhang in Polynomialzeit
  • Flussprobleme, Max-Flow-Min-Cut-Theorem, Algorithmus von Dinic
  • Graphparameter, Cliquen, unabhängige Mengen
  • Träger, Matchings, bipartite Graphen, Satz von Kőnig
  • Perfekte Graphen, α-Perfektheit, χ-Perfektheit
  • Cographen, Charakterisierungen von Cographen, Serien-Parallel-Graphen
  • Chordale Graphen, simpliziale Ordnungen, Separatoren in chordalen Graphen, Perfektheit chordaler Graphen, Berechnung simplizialer Ordnungen in Polynomialzeit, Intervallgraphen
  • Transitiv orientierbare Graphen, Ketten, Antiketten, Satz von Dilworth, Permutationsgraphen
  • Split-Graphen, Charakterisierungen von Split-Graphen
  • Gradsequenzen, Satz von Erdős–Gallai, Gradsequenzen von Split-Graphen
  • Schwache Vermutung für perfekte Graphen (Satz von Lovász)
  • Ramseytheorie, unendliche und endliche Version des Satzes von Ramsey, Ramsey-Zahlen

Übungsblätter

  • Blatt 1
  • Blatt 2
  • Blatt 3
  • Probeklausur – Update (05.02.2016): Die Single-Choice-Aufgaben zu k-Zusammenhang wurden umformuliert; die Randfälle sind jetzt ausgeschlossen.

Literatur