Metanavigation
Universität Hamburg - der Forschung, der Lehre, der Bildung, zur Homepage
Fachbereich Mathematik
FachbereichMathematik
Suche
Suche
Inhalt
Foto: UHH/Denstorf
Sie sind hier:UHH > MIN-Fakultät > Fachbereich Mathematik > Homepages

Homepages

(hier geht es zur ggf. vollständigeren Homepage im alten Layout)
(this way to the possibly more complete Homepage in the old layout)

Vorlesung: Graphentheorie

Dozent: Prof. Mathias Schacht

Termine

  • 02.04.2013 (erste VL)
  • 11.04.2013 (erste UE)
VL Dienstag 12:15 - 13:45 Geomatikum, H5
Donnerstag 14:15 - 15:45 Geomatikum, H6
UE Donnerstag 16:00 - 17:30 Geomatikum, H6

Leistungsnachweis

  • Bestehen der mündlichen Prüfung (erfolgreiche Teilnahme an der Übung wird vorausgesetzt)
  • Prüfungstermine werden am Ende der Vorlesung vereinbart

Einordnung

  • Vertiefungsmodul, Bachelor (4. Semester), 9LP
  • 4+2 SWS
  • Graphentheorie und Diskrete Mathematik

Voraussetzungen

Die Vorlesung setzt nur Grundbegriffe aus den Anfängervorlesungen des ersten Studienjahres voraus. Vorherige Teilnahme an der Vorlesung „Diskrete Mathematik” ist nicht nötig.

Überblick

Die Graphentheorie ist eines der jüngsten und zugänglichsten Gebiete der Mathematik. Ohne, wie in den klassischen Disziplinen oft unumgänglich, zunächst ein umfassendes Instrumentarium an Begriffsapparat und Techniken beherrschen lernen zu müssen, begegnet man hier von Anfang an mathematischen Problemen, die man im Prinzip ohne weitere Voraussetzungen selbst bearbeiten könnte. Hierzu soll die Vorlesung sowohl einladen, als auch den ordnend-motivierenden Rahmen darstellen.

Inhalte

In der Vorlesung werden die Leitprobleme und grundlegenden Sätze der Graphentheorie vorgestellt. Die Vorlesung folgt dabei größtenteils der deutschen Ausgabe des Buches Graphentheorie von Reinhard Diestel, so dass in der Vorlesung niemand mitschreiben muss.
  1. Grundbegriffe (02.04.-11.04.)
    • Kapitel 0.1-0.6 und 0.8 aus [D-De]
  2. Paarungen & Überdeckungen (11.04.-19.04.)
    • Kapitel 1.1, 1.2 und 1.5 aus [D-De]
  3. Zusammenhang (26.04.-03.05.)
    • Kapitel 2.1-2.3 aus [D-De]
  4. Graphen in der Ebene (03.05.-16.05.)
    • Kapitel 3.1, 3.2 und 3.4 aus [D-De]
  5. Färbungen (16.05.-04.06.)
    • Kapitel 4.1-4.4 aus [D-De]
  6. Netzwerke (04.06.-06.06.)
    • Kapitel 5.1 und 5.2 aus [D-De]
  7. Extremale Graphentheorie (11.06.-13.06.)
    • Kapitel 6.1, Proposition 6.2.2 und Hadwiger-Vermutung aus [D-De]
  8. Ramseytheorie für Graphen (18.06.)
    • Kapitel 7.1 aus [D-De]
  9. Hamiltonkreise (20.06.)
    • Kapitel 8 aus [D-De]
  10. Zufallsgraphen (25.06.-27.06.)
    • Kapitel 9.1, 9.2 und 9.3 (bis Korollar 9.3.3) aus [D-De]
  11. Unendliche Graphen (02.07.)
  12. Wohlquasiordnungen und Minoren (09.07.-11.07.)
    • Kapitel 10.1 und 10.2 aus [D-De]

Übungen

Die Übungen werden von Prof. Christian Reiher geleitet. Es wird der Stoff der Vorlesung vertieft und es werden die Übungaufgaben besprochen und von den Studierenden vorgetragen. Erforderlich für das Bestehen der Übung ist die Lösung von insgesamt 50% der normalen und der schweren (mit Plus markierten) Übungsaufgaben, wobei die normalen Aufgaben mit einem Punkt und die schweren mit zwei Punkten bewertet werden. Die leichten Aufgaben (mit Minus markiert) werden nicht gewertet und sind nur zum Einstieg gedacht. Es wird voraussichtlich 12 Übungsblätter mit jeweils zwei bis drei normalen, ein oder zwei schweren Aufgaben, sowie einigen leichten Aufgaben geben.

Literatur

  • B. Bollobás: Modern Graph Theory, Springer, 2nd ed., 1998
  • J. A. Bondy & U. S. R. Murty: Graph Theory, Springer, 2008
  • R. Diestel: Graphentheorie, Springer, 4. Auflage, 2010
  • R. Diestel: Graph Theory, Springer, 4th ed., 2010