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 |
Prüfung
Die Prüfung erfolgt mündlich. Als Zulassungsvoraussetzung ist ein Übungsschein erforderlich.
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 |
Do., 23.11. | (minimale) Eckenseparatoren; chordal ⇔ simpliziale Ordnung ⇔ minimale Separatoren sind Cliquen; Satz von Dirac: Chordale Graphen sind perfekt |
Mo., 27.11. | G χ-perfekt ⇔ G α-perfekt ⇔ |H| ≤ α(H)ω(H) (Satz von Lovász) |
Do., 30.11. | G Intervallgraph ⇔ G chordal und G TRO |
Mo., 04.12. | Transitive Orientierung; Pseudo-TRO; Implikationsklassen; Äquivalent: G besitzt TRO ⇔ A ∩ A-1 = Ø für Implikationsklassen A ⇔ geschlossene Kantenzüge haben Dreieckssehnen ⇔ G besitzt Pseudo-TRO |
Do., 07.12. | Übung: Besprechung des Rests von Blatt 2 und von Blatt 3/4 |
Mo., 11.12. | Permutationsgraphen: abgeschlossen unter induzierten Untergraphen und Komplement, G Permutationsgraph ⇔ G und G TRO; Splitgraphen: abgeschlossen unter induzierten Untergraphen und Komplement, G Splitgraphen ⇔ G und G chordal ⇔ G ist 2K2-, C4- und C5-frei ⇔ G und G sind C4- und C5-frei |
Do., 14.12. | Gradsequenzen; Satz von Erdős-Gallai; Charaketerisierung von Splitgraphen über Gradsequenz |
Mo., 18.12. | Graphhomomorphismen; Unterteilungsgraphen; Minoren |
Do., 21.12. | Übung: Besprechung von Blatt 3/4 |
Mo., 08.01. | Definition von Minoren über Graphhomomorphismen und über Kantenkontraktionen; Minorenrelation ordnet endliche Graphen partiell; einfache Lemmata zum Zusammenhang zwischen Minoren und Unterteilungen |
Do., 11.01. | K5 oder K3,3 ist genau dann Minor von G, wenn G eine Unterteilung des K5 oder K3,3 enthält. |
Mo., 15.01. | Besprechung von Blatt 3/4 und von Blatt 5 |
Do., 18.01. | k-Zusammenhang, Satz von Thomassen, Satz von Kuratowski |
Mo., 22.01. | Satz von Kuratowski (2. Teil); Satz von Wagner-Fáry |
Do., 25.01. | Übung: Besprechung von Blatt 5 |
Mo., 29.01. | Separator-Theorem von Lipton und Tarjan |
Do., 01.02. | Alternativer Beweis für das Separator-Theorem von Lipton und Tarjan |
Mo., 05.02. | Übung: Besprechung von Blatt 6 |
Do., 08.02. | Satz von Erdős-Pósa; kubische Multigraphen haben viele disjunkte Kreise |
Übung
Übungsblätter
- Blatt 1 geändert: fehlendes „mindestens“ bei Aufgabe 2 eingefügt
- Blatt 2 Besprechung ab dem 2. November
- Blatt 3 und 4 geändert: Aufgabe zu platonischen Körpern korrigiert
- Blatt 5
- Blatt 6 geändert: Zahlen bei Aufgabe 3 korrigiert
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.
- Aktualisierte Fassung des Skripts
- Altes (teilwiese unvollständiges) Skript zur Vorlesung von Manfred Kufleitner aus dem Wintersemester 09/10.