Vorlesung

Dozent: Volker Diekert

Übungen: die wissenschaftlichen Mitarbeiter der theoretischen Informatik

Ansprechpartner: Jan Philipp Wächter

Zeit Raum Termine
Mo 15:45–17:15 0.108 erster Termin: 16.10.17
Do 15:45–17:15 0.108  

Inhalt

Datum Inhalt
Mo., 16.10. Grundbegriffe, „die Summe aller Grade ist gerade”, Eulerkreis, Satz von Euler, Hamilton-Kreis, Satz von Ore
Do., 19.10. Übung: Besprechung von Blatt 1
Mo., 23.10. Bipartite Graphen: Heiratssatz; Bäume: Charakterisierungen und Algorithmus von Prim zum Berechenen von Spannbäumen
Do., 26.10. Satz von Kőnig (Matching, Verbesserungswege, Träger), Folgerung des Heiratssatzes aus dem Satz von Kőnig
Mo., 30.10. Satz von Menger, Folgerung des Satzes von Kőnig aus dem Satz von Menger, Satz von Tutte
Do., 02.11. Graphparameter; |G| = α(G) + τ(G); bipartite Graphen sind perfekt
Mo., 06.11. Übung: Besprechung von Blatt 2
Do., 09.11. Cographen: Definition, perfekt, äquivalent zu P4-Freiheit, G oder sein Komplement sind zusammenhängend
Mo., 13.11. Plättbar, planar, eulersche Polyederformel, Kantenanzahl in Wäldern; transitiv orientierbare Graphen (TROs): Definition, perfekt mit Satz von Dilworth
Do., 16.11. Prüfer-Codes, Cayley-Formel; Lineare Algebra: Kantenmengen liefern 𝔽2-Vektorraum, Basis, Zyklenraum, Schnitte, Orthogonalität zwischen Zyklen und Schnitten
Mo., 20.11. Wiederholung „lineare Algebra“; Chordale Graphen: Definition, simpliziale Knoten, simpliziale Ordnung

Übung

Übungsblätter

  • Blatt 1 geändert: fehlendes „mindestens“ bei Aufgabe 2 eingefügt
  • Blatt 2 Besprechung ab dem 2. November

Vorschau-Blätter

Die Aufgaben auf folgenden Blättern werden möglicherweise später im Semester besprochen:

Literatur

  • Volker Diekert, Manfred Kufleitner, Gerhard Rosenberger: Elemente der diskreten Mathematik, Walter de Gruyter, 2013.
  • Reinhard Diestel: Graphentheorie, Springer-Verlag, 2010.
  • Altes (teilwiese unvollständiges) Skript zur Vorlesung von Manfred Kufleitner aus dem Wintersemester 09/10.

News

[Jun’17] Lukas’ paper “Green’s Relations in Finite Transformation Semigroups” and Armin’s paper “The conjugacy problem in free solvable groups and wreath product of abelian groups is in $\text{TC}^0$ \text{TC}^0 “ both have received a Best Paper Award at the 12th International Computer Science Symposium in Russia (CSR).