Graphentheorie (M05)Wintersemester 2019/20
|
 |
Kurzbeschreibung
| Inhalt: | Einführungsvorlesung zur Graphentheorie. Es wird ein Überblick über die moderne Graphentheorie gegeben. Insbesondere werden die Themenkreise Zusammenhang, Plättbarkeit, Färbungen und Minoren behandelt. |
| Zielgruppe: | wo: D_InEM7, D_TM__7, D_WM__7, M_MaFM1, M_MaIn1, M_MaMa1, M_MaWM1, D_Ma__7 fak: D_TM__5, D_TM__9, D_WM__5, D_WM__9, M_MaTM1, D_Ma__9, D_Ma__5 |
| Vorwissen: | Grundlagen der Mathematik |
Literatur
- Graphentheorie (R. Diestel)
- Introduction to Graph Theory (D. B. West)
- A simple test for planar graphs (W. K. Shih & W. L. Hsu)
- Planarity in linear time (R. Thomas)
- List Colorings of planar graphs (M. Voigt)
- Every Planar Graph Is 5-Choosable (C. Thomassen)
Inhalt
- Grundbegriffe (Graph, Knoten, Kanten, Adjazenz, Inzidenz, ...)
- Zusammenhang (Wege, Bäume, Brücken, Satz von Menger, ...)
- Eulerzyklen und Hamiltonkreise
- Matchings
- Planarität
- Färbungen
- Ramsey-Theorie
- Extremalgraphen
- Zufallsgraphen
- Wohlquasiordnung
Übungen
-
Exercise 1 (german version only)
-
Exercise 2 (german version; two relevant IMO tasks here and here)
