Webrelaunch 2020

Graph Theory (Wintersemester 2013/14)

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

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)


Zusätzliche Materialien

  • Beispielbeweis aus der Übung vom 25.10.2013: (pdf)
  • Programm zum Berechnen von Zusammenhangskomponenten, Maximalgrad und Durchmesser von Wort-Graphen: (tar-ball)

Herzlichen Dank an Daniel Hoske, der hier freundlicherweise seinen Quellcode zur Verfügung stellt.