Schriftzug: Fachbereich Mathematik 
  UHH > Fakultäten > MIN-Fakultät > Mathematik > Personen > Mathias Schacht   STiNE |  KUS-Portal |  Sitemap Suchen Hilfe there is no english version of this page  

Vorlesung: Graphentheorie

Dozent: Prof. Mathias Schacht

Termine

  • 19.10.2010 (erste VL)
  • 29.10.2010 (erste UE)
VL Dienstag 10:15 - 11:45 Geomatikum, H4
Freitag 10:15 - 11:45 Geomatikum, H4
UE Freitag 08:30 - 10:00 Geomatikum, H3

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 (5. Semester), 9SP
  • Vertiefungs- und Spezialvorlesung, Master, 12SP (letztmalig; höhere Anforderungen bei den Übungsaufgaben und in der Prüfung)
  • 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, so dass in der Vorlesung niemand mitschreiben muss.
  1. Grundbegriffe (19.10.-29.10.)
    • Kapitel 0.1-0.6 und 0.8 aus [D-De]
  2. Paarungen & Überdeckungen (29.10.-05.11.)
    • Kapitel 1.1, 1.2 und 1.5 aus [D-De]
  3. Zusammenhang (09.11.-16.11.)
    • Kapitel 2.1-2.3 aus [D-De]
  4. Graphen in der Ebene (19.11.-26.11.)
    • Kapitel 3.1, 3.2 und 3.4 aus [D-De]
  5. Färbungen (30.11., 10.12-14.12.)
    • Kapitel 4.1-4.3 aus [D-De]
  6. Unendliche Graphen (03.12.-07.12.)
  7. Netzwerke (14.12.-17.12.)
    • Kapitel 5.1 und 5.2 aus [D-De]
  8. Hamiltonkreise (04.01.-07.01.)
    • Kapitel 8 aus [D-De]
  9. Extremale Graphentheorie (11.01.-21.01.)
    • Kapitel 6.1, Proposition 6.2.2 und Hadwiger-Vermutung aus [D-De]
  10. Ramseytheorie für Graphen (21.01.-25.01.)
    • Kapitel 7.1 aus [D-De]
  11. Zufallsgraphen (28.01.-01.02.)
    • Kapitel 9.1, 9.2 und 9.3 (bis Korollar 9.3.3) aus [D-De]
  12. Wohlquasiordnungen und Minoren (04.02.)
    • Kapitel 10.1 und 10.2 aus [D-De]
Folien der VL (Stand 15.02.11).

Übungen

In den Übungen wird der Stoff der Vorlesung vertieft und es werden die Übungaufgaben besprochen und von den Studierenden vorgetragen. Erforderlich für das Bestehen der Übung im Bachelor (9SP) ist die Lösung von insgesamt 50% der normalen und der leichten (mit Minus markierten) Übungsaufgaben, wobei die normalen Aufgaben mit 2 Punkten bewertet werden und die leichten mit nur einem Punkt. Die schweren Aufgaben (mit + markiert) gehen in die Summe der verlangten Punkte beim Bachelor nicht ein, können aber zur Aufbesserung des Punktekontos zusätzlich genutzt werden. Jede dieser Plusaufgaben bringt bei vollständig präsentierter Lösung 6 Punkte, kann also drei normale oder sechs einfache Aufgaben ersetzen. (Damit ist es im Bachelor möglich, mehr als 100% zu erlangen.) Für das Bestehen der Übung im Master (12SP) ist es erforderlich 50% aller Punkte zu erreichen.

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, 4te Auflage, 2010
  • R. Diestel: Graph Theory, Springer, 4th ed., 2010

 
  zurück Seitenanfang  Impressum 2011-02-15, Mathias Schacht