Fachbereich Mathematik 
  UHH > Faculties > MIN-Faculty > Mathematics > Staff > Max Pitz   STiNE |  KUS-Portal |  Sitemap Search Help es gibt keine deutsche Version dieser Seite  

Graphentheorie 1,   SoSe 2019

Dr. Max Pitz

Vorlesungstermine

  • Dienstags, 10:15 - 11:45 Uhr, Geomatikum H5
  • Freitags, 8:30 - 10:00 Uhr, Geomatikum H6
  • Übungstermine

  • Dienstags, 12:15 - 13:45 Uhr, Geomatikum 434 (Carl Bürger)
  • Freitags, 12:15 - 13:45 Uhr, Geomatikum 431 (Ruben Melcher)
  • Inhalt

    Die Graphentheorie ist eines der jüngsten und zugänglichsten Gebiete der Mathematik. Hier begegnet man vom ersten Tag an mathematischen Problemen, die man im Prinzip ohne weitere Voraussetzungen selbst bearbeiten könnte. Die Vorlesung folgt dem Buch Graphentheorie / Graph Theory (Springer, Graduate Text in Mathematics 173) von Reinhard Diestel. Dort ist der netto-Vorlesungsstoff (Definitionen, Aussagen, Beweise) vollständig zu finden, so dass in der Vorlesung niemand diesen Grundstoff mitschreiben muss und sich auf den dort gebotenen Mehrwert konzentrieren kann: woher die Begriffe kommen, welchem Ziel sie dienen, welche Ideen den Beweisen zugrundeliegen und welche scheinbar offensichtlicheren Ideen nicht funktionieren, und weshalb nicht.

    Voraussetzungen

    Die Vorlesung wendet sich typischerweise an Hörer im 4. Semester, setzt aber nur Grundbegriffe aus dem 1. Semester voraus. Vorherige oder gleichzeitige Teilnahme an der Vorlesung "Diskrete Mathematik" ist nicht Voraussetzung.

    Organisation

    Zur Vorlesung gibt es Übungen, die durchaus über den Vorlesungsstoff hinausgehen können und eine Spielwiese für eigene Beweisversuche bieten. Zur Vorlesung gibt es ein paralleles Proseminar. Dieses behandelt dann wöchentlich jeweils eine besonders interessante Übungsaufgabe außerhalb des Kanons, die zu lösen jeder Teilnehmer ernsthaft versuchen sollte. Das Proseminar dient dazu, die Darstellung von Mathematik einzuüben: sowohl ausformuliert schriftlich als auch in freiem mündlichen Vortrag.

    Übungsblätter

    Die Übungsblätter erscheinen im wöchentlichen Rhythmus. Sie werden Ihre Lösungen in den Übungen mündlich präsentieren. Hierzu tragen Sie sich jeweils am Dienstag vor der Vorlesungen in eine Liste ein, welche Aufgaben Sie gelöst haben und bereit sind, vorzutragen. Bestimmte Aufgaben sind extra gekennzeichnet, und sollen schriftlich abgegeben werden. Denken Sie beim Vortragen an das Schema: Situation -- Complication -- Solution, d.h. erinnern Sie Ihre Kommilitonen kurz daran, was eigentlich das Problem / die Aufgabe war, wo eventuell die Schwierigkeit der Aufgabe liegt, und erst dann, wie Ihre Lösung aussieht.

    Leistungsnachweis

    Bestehen der schriftlichen/mündlichen Prüfung. Für die Prüfungszulassung wird eine erfolgreiche Teilnahme an der Übung vorausgesetzt (Erreichen von jeweils 50% der in den schriftlichen und der in den rein mündlichen Aufgaben erreichbaren Punkte. Wenn Sie eine Woche wegen Krankheit verpassen, wird diese Woche bei Vorlegen eines Attests (kurze Email an den Übungsleiter) von den 50% rausgerechnet.) Allgemeine Tipps zum Ablauf, zur Vorbereitung, und zum Prüfungsstoff gibt es hier. Vorläufige Prüfungszeiträume sind die zweite Augusthälfte (19.-30. August) sowie die erste Oktoberwoche (30. September - 4 Oktober).

    Material

    • R. Diestel: Graphentheorie (5. Auflage), Springer 2017. Die deutsche Auflage ist eine Übersetzung großer Teile der englischen und deckt den Stoff dieser Vorlesung ab. Die englische Ausgabe enthält zusätzlich Material für die Master-Vorlesung "Graphentheorie II", das in der deutschen nicht enthalten ist. (Kaufen Sie sich das Buch erstmal nicht; zu den verschiedenen Möglichkeiten dafür sage ich in der ersten Vorlesung mehr.)
    • R. Diestel, Graph Theory (5th ed'n), GTM 173, Springer 2017. Online verfügbar aus dem Uni-Netzwerk.
    • Grundlegende Begriffe für die erste Vorlesungswoche.
    • Deutsch-englisches Glossar.

    Logbuch

    Dx.x sowie Ex.x beziehen sich auf die Kapitel in der deutschen bzw. englischen Version des Buches.
    • 2. April: Historisches zur Graphentheorie: Die Brücken von Königsberg, platonische Körper und Hamiltonische Kreise, 4-Farben Problem. Grundlegende Definition der Graphentheorie (D0.1; E1.1) sowie Start Satz von Euler (D0.8.1; E1.8.1).
    • 5. April: Ende Satz von Euler. Grapheneigenschaften und -invarianten. Auswirkung von Minimalgrad auf andere Grapheneigenschaften. (D0.2, D0.3 bis Prop. 0.3.1; E1.2, E1.3 bis Prop. 1.3.1).
    • 9. April: Taillenweite, Umfang und Durchmesser, Prop. D0.3.2; E1.3.2. Zusammenhang und Kantenzusammenhang (Kap D0.4 bis Prop. D0.4.2 inklusive; E1.4 bis E.1.4.2).
    • 12. April: Maders Theorem (Satz D0.4.3; E1.4.3). Spannbäume, Baumordnung und normale Spannbäume (Kap D0.5 bis D0.5.5 exklusive; Chapter E1.5 bis E1.5.5).
    • 16. April: Zwei Existenzbeweise für normale Spannbäume (Ende Kap D0.5/E1.5). Bipartite Graphen und 2-Färbungen (Kap D0.6/E1.6). Interessant: Tim Gowers über Färbungen.
    • 23. April: Paarungen in bipartiten Graphen. Alternierende Wege und Verbesserungswege. Satz von König (D1.1.1; E2.1.1). Satz von Hall (D1.1.2; E2.1.2), erster Beweis.
    • 26. April: Satz von Hall, zweiter Beweis. Petersen's 2-Faktor Satz. Stabile Paarungen und das Gale-Shapley Theorem. Start 1-Faktor Satz von Tutte. (D1.1.2-D1.1.6 bis D1.2.1; E1.1.2-E1.1.6 bis E1.2.1)
    • 30. April: Ende 1-Faktor Satz von Tutte. Satz von Dilworth. Satz von Gallai Milgram. (D1.2.1, D1.5.1 und D1.5.2; D2.2.1, D2.5.1 und D2.5.2) Konstruktion der 2-zh Graphen. (D2.1.1; E3.1.1)
    • 3. Mai: Blöcke und der Block-Graph (D2.1.4; E3.1.4). Zwei Konstruktionsmethoden aller 3-zh Graphen (D2.2.1 - D2.2.4; E3.2.1 - E3.2.4)
    • 7. Mai: Der Mengersche Satz (D2.3.1; E3.3.1) (Nullter und erster Beweis) und seine Korollare (D2.3.4 - 2.3.5; E3.3.4-3.3.5). Interessant: Karl Mengers Originalarbeit (Satz δ) mit der Beweislücke in Zeile 3+4 auf Seite 102).
    • 10. Mai: Der Mengersche Satz (D2.3.1; E3.3.1) (Zweiter Beweis). Beweisidee für Eulerformel, K_5 und K_3,3 sind nicht planar (D3.2.9 bis 3.2.10; E4.2.9 bis E4.2.10). Polygonzüge und topologische Voraussetzungen (Kap D3.1; E4.1). Für Experten: Thomassens Beweis des Jordanschen Kurvensatzes (aus dem Uni-Netzwerk).
    • 14. Mai: Mehr zu ebenen Graphen (Kapitel D3.2 bis Proposition D3.2.7; E4.2 bis E4.2.7).
    • 17. Mai: Maximal ebene Graphen und Dreiecksgraphen. Eulerformel sowie K_5 und K_3,3 sind nicht planar zum Zweiten (D3.2.8 bis 3.2.11; E4.2.8 bis E4.2.11). Kuratowski für 3-zh Graphen. (Kapitel D3.4 bis Proposition D3.4.3; E4.4 bis E4.4.3).
    • 21. Mai: Der Fünf-Farben-Satz (Kapitel D4.1; E5.1). Eckenfärbungen und Greedy-Algorithmus. Anfang Satz von Brooks (Kapitel D4.2 bis 4.2.4; E5.2 bis 5.2.4).
    • 24. Mai: Ende Satz von Brooks. Erdös, Hajos, König (D4.2.4 bis 4.3.1; E5.2.4 bis 5.3.1).
    • 28. Mai: Satz von Vizing (D4.3.2; E5.3.2). Listenfärbungen (Kapitel D4.4 bis 4.4.3; E5.4 bis 5.4.3).
    • 31. Mai: Satz von Galvin (D4.4.4; E5.4.4). Netzwerke, Flüsse und das Max-Flow-Min-Cut Theorem (Kapitel D5.2; E6.2).
    • 4. Juni: Hadwiger Vermutung und Wagners Struktursätze (Kapitel D6.3; E7.3). Minorenerzwingung durch hohen Durchschnittsgrad (D6.2.1 (in Form von 2.5.1), 6.2.2; E7.2.1 und 7.2.2).
    • 4. Juni: Satz von Turan, Erdös-Stone und Korollare. (Kapitel D6.1; E7.1).

     
      Seitenanfang  Impress 2019-06-07, Max Pitz