Graph Theory (Wintersemester 2013/14)
- Dozent*in: Prof. Dr. Maria Axenovich, Torsten Ueckerdt
- Veranstaltungen: Vorlesung (0104500), Übung (0104510)
- Semesterwochenstunden: 4+2
| Termine | |||
|---|---|---|---|
| Vorlesung: | Montag 9:45-11:15 | 1C-03 | Beginn: 21.10.2013 |
| Mittwoch 8:00-9:30 | Neue HS Geb. 20.40 | ||
| Übung: | Freitag 11:30-13:00 | RPH HS Geb. 40.32 | Beginn: 25.10.2013 |
| 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 | ||
Aktuelles
- Die Noten für Graph Theory hängen in der 4. Etage des Allianzgebäudes aus.
- Die Klausureinsicht findet am 28. April von 13:00 bis 14:00 im Raum 1C-01 des Allianzgebäudes statt.
- Es werden individuelle mündliche Nachprüfungen angeboten. Bitte kontaktieren Sie uns.
Im Sommersemester 2014 bieten wir das Seminar Topics in Graph Theory an. Interessierte Studenten mögen zur Vorbesprechung am Donnerstag, den 6. Februar kommen.
Weitere Informationen unter Topics in Graph Theory.
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 Montag (beginnend am 21. Oktober) ein Übungsblatt mit 4 Aufgaben zu je 5 Punkten.
- Die Übungsblätter können in kleinen Gruppen gelöst, und einzeln, zu zweit oder dritt abgegeben werden.
- Jeder Student bearbeitet drei Aufgaben seiner Wahl.
- Abgabefrist ist jeweils 12:00 am Mittwoch der folgenden Woche.
- Die Blätter können während der Vorlesung oder in dem Abgabekasten im 4. Stock des Allianzgebäudes abgegeben werden.
Die Übungsblätter werden jeden Montag in der Vorlesung ausgeteilt.
Schriftliche Prüfung
Am Ende des Semester gibt es eine schriftliche Prüfung:
26. Februar 2014, 9:00 Uhr bis 13:00 Uhr
Die Klausur findet im Hörsaal Nusselt (Geb. 10.23) und Hörsaal Tulla (Geb. 11.40).
Prüfungsanmeldung
Beginn: 15. Januar 2014
Ende: 15. Februar 2014
Die Anmeldung zur Prüfung "Graph Theory" erfolgt über das Studierendenportal unter https://studium.kit.edu. Die Anmeldung ist im Zeitraum von 15.01.2014 bis 15.02.2014 möglich. Eine Anmeldung nach dem 15. Februar kann nur persönlich im Sekretariat erfolgen. Eine Abmeldung ist bis zum 25. Februar im Studierendenportal und am 26. Februar persönlich möglich.
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 den in der schriftlichen Prüfung erreichten Punkten. Wird die schriftliche Prüfung bestanden, dann kann die erreichte Note um ein, zwei oder drei Schritte nach oben korrigiert werden. Dies geschieht aus Basis der in den Hausaufgaben erreichten Punkten wie folgt:
- Mindestens 108 Punkte aus 9 Blättern oder mindestens 90 Punkte aus 7 Blättern: 1 Notenschritt besser
- Mindestens 115 Punkte aus 9 Blättern oder mindestens 95 Punkte aus 7 Blättern: 2 Notenschritte besser
- Mindestens 122 Punkte aus 9 Blättern oder mindestens 100 Punkte aus 7 Blättern: 3 Notenschritte (eine ganze Note) besser
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 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 bis inklusive Menger's Theorem: (pdf)
Es gibt desweiteren ein Vorlesungsskript welches alle relevanten Definitionen, Notationen und Sätze enthält. Allerdings sind keine Beweise, keine Motivation und nur wenige Beispiele enthalten.
- Vorlesungsskript: (pdf)