Graph Theory (Wintersemester 2015/16)
- Dozent*in: Prof. Dr. Maria Axenovich
- Veranstaltungen: Vorlesung (0104500), Übung (0104510)
- Semesterwochenstunden: 4+2
Nachklausur
Die Ergebnisse hängen jetzt an der Pinnwand zwischen Raum 1.043 und Raum 1.044 aus.
Die Einsicht zur Nachklausur findet am Dienstag, 18. Oktober um 14:00 im Raum 1.045 statt.
Termine | ||
---|---|---|
Vorlesung: | Dienstag 11:30-13:00 | SR 1.066 / 1.067 |
Donnerstag 9:45-11:15 | SR 1.066 / 1.067 | |
Übung: | Freitag 8:00-9:30 | SR 1.066 / 1.067 |
Lehrende | ||
---|---|---|
Dozentin | Prof. Dr. Maria Axenovich | |
Sprechstunde: Fr. 10:00-11:00 | ||
Zimmer 1.043 Kollegiengebäude Mathematik (20.30) | ||
Email: maria.aksenovich@kit.edu | Übungsleiter | Torsten Ueckerdt |
Sprechstunde: | ||
Zimmer Kollegiengebäude Mathematik (20.30) | ||
Email: torsten.ueckerdt@kit.edu |
Vorlesungsinhalte
Die Vorlesung behandelt Themen der klassischen und modernen Graphentheorie:
- Eigenschaften von Bäumen, Kreisen, Matchings und Faktoren
- Verbotene Teilgraphen
- Planare Graphen
- Graphenfärbungen
- Zufallsgraphen
- Ramsey Theorie
- Graph Minoren
Lernziele
Der Schwerpunkt der Vorlesung liegt auf dem Lösen von Problemen. Die Studenten sollen grundlegende Konzepte der Graphentheorie kennenlernen, interessante Probleme bearbeiten und lernen Beweise zu schreiben und kreativ zu präsentieren.
Voraussetzungen
Grundkenntnisse der linearen Algebra; geeignet für Studenten ab dem 5. Semester
Prüfung
Übungsblätter
- Es gibt jeden Dienstag (beginnend am 20. Oktober) ein Übungsblatt mit 4 Aufgaben zu je 5 Punkten.
- Die Übungsblätter werden einzeln oder zu zweit gelöst und abgegeben.
- In jeder Abgabe sollen höchstens drei Aufgaben bearbeitet werden.
- Bei Abgabe zu zweit, soll jeder Student mindestens eine Lösung geschrieben haben.
- Abgabefrist ist jeweils 14:00 am Dienstag der folgenden Woche.
- Die Blätter können während der Vorlesung oder in dem Abgabekasten im Atrium des Mathegebäudes abgegeben werden.
Bonus
Es ist möglich durch erfolgreiches Bearbeiten der Übungsblätter einen Bonus für die Klausur zu erlangen.
Um diesen Bonus zu erhalten, muss sowohl auf den ersten 6 Übungsblättern, als auch auf den zweiten 6 Übungsblättern, des Semesters, mindestens die Hälfte der jeweiligen Gesamtpunktzahl erreicht werden.
Der Bonus verbessert die Note einer bestandenen Klausur für diese Vorlesung am Ende des Semesters um einen Notenschritt (0.3 oder 0.4 Notenpunkte).
Schriftliche Prüfung
Am Ende des Semester gibt es eine schriftliche Prüfung:
Datum: 22. Februar 2016
Ort: Tulla Hörsaal und Fritz-Haller Hörsaal
Zeit: 13:00 -- 16:00
Prüfungsanmeldung
Die Anmeldung zur Prüfung "Graph Theory" erfolgt über das Studierendenportal unter https://studium.kit.edu.
Anmeldebeginn ist der 10.1.2016.
Anmeldeschluss ist der 15.2.2016.
Tag der Prüfung
Jeder Student informiert sich über seinen Sitzplatz und erscheint mindestens 10 Minuten vor Prüfungsbeginn.
Benotung
Die Note für die Veranstaltung errechnet sich aus den in der schriftlichen Prüfung erreichten Punkten.
Literaturhinweise
Die Vorlesung orientiert sich grösstenteils an dem Buch Graph Theory von Reinhard Diestel. Eine englische Version kann kostenlos auf der Webseite des Autoren (http://diestel-graph-theory.com/) gelesen werden.
Zusätzliche Literatur
- D. West -- Introduction to graph theory
- B. Bollobas -- Modern graph theory
- A. Bondy und U.S.R. Murty -- Graph Theory
- L. Lovasz -- Combinatorial problems and exercises
- G. Chartrand, L. Lesniak und P. Zhang -- Graphs & Digraphs
Vorlesungsskript
Es gibt desweiteren ein Vorlesungsskript welches alle relevanten Definitionen, Notationen und Sätze enthält. Allerdings sind keine Beweise und nur wenige Beispiele enthalten.
- Vorlesungsskript: (pdf)
- Ergänzendes Material zu Extremal Functions: (pdf)
- Ergänzendes Material zu Hypergraph Ramsey: (pdf)
Es gibt eine Vorlesungsmitschrift aus dem Wintersemester 2011/12. Die momentane Version ist nicht überarbeitet und erhebt keinen Anspruch auf Vollständigkeit oder Korrektheit.
- nicht überarbeitete Vorlesungsmitschrift: (pdf)