|
|
Graphentheorie 1, SoSe 2019
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.
Auswahl der Sätze für den Kürteil. Zu diesen Sätzen soll jeweils möglich viel gewusst werden (Vorschläge unten). Für Ihre 5-minütige Darstellung müssen Sie natürlich eigenständig Schwerpunkte setzen um innerhalb der Zeit zu bleiben.
- Menger (D2.3.1): Ein Beweis Ihrer Wahl + Zusammenhang König/Hall/Max-Flow-Min-Cut + Beispiele im Rest des Buches wo Menger nützlich ist.
- 5-Farben Satz (D4.1.2 + 4.4.2): Jeweils einen Beweis. Welche topologischen Hilfsaussagen (ohne Beweis) über Graphen in der Ebene fließen jeweils ein?
- Ramsey-Schranken für Graphen (D7.1.1 + 9.1.3): Jeweils einen Beweis. Inwiefern ist es hilfreich, eventuell unendliche Graphen zu betrachten?
Eine Liste mit Ihren Prüfungsterminen gibt es auf Stine. Bitte schreiben Sie mir ein Email, wenn Sie Fragen zu Ihrem Prüfungstermin haben.
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). Interessant: Bei reellen Kapazitätsfunktionen kann unser Beweis über die schrittweise Erhöhung von nicht-ausgelasteten Wegen fehlschlagen.
- 4. Juni: Hadwiger Vermutung und Wagners Struktursätze (Kapitel D6.3; E7.3). Minorenerzwingung durch hohe chromatische Zahl (Übung D6.19) sowie durch hohen Durchschnittsgrad (D6.2.1 (in Form von 2.5.1), 6.2.2; E7.2.1 und 7.2.2).
- 7. Juni: Satz von Turan, Erdös-Stone und Korollare. (Kapitel D6.1; E7.1).
- 11. und 14. Juni: Pfingstferien.
- 18. Juni: Satz von Ramsey für Graphen, endlich und unendlich (D7.1.1; E9.1.1). Motivation Ramsey für k-Tupel.
- 21. Juni: Satz von Ramsey für k-Tupel, endlich und unendlich, sowie Königs Unendlichkeitslemma. (Kapitel D7.1; E9.1 sowie E8.1.2).
- 25. Juni: Ramsezahlen für Graphen (D7.2.1 und 7.2.3; E9.2.1, E9.2.3). Direkter Beweis untere Ramsey-Schranke. Einführung Zufallsgraphen. Probabilistischer Beweis untere Ramsey-Schranke. (Kapitel D9.1 bis 9.1.3; E11.1 bis 11.1.3) Erwartungswert.
- 28. Juni: Ende Kapitel D9.1 sowie Kapitel D9.3: Eigenschaften fast aller Graphen sowie Erdös-Renyi-Satz (E11.1 und 11.3).
- 2. Juli: Graphen mit hoher Taillenweite und hoher chromatische Zahl: Mycielski-Konstruktion sowie Satz von Erdös. (Kapitel D9.2; E11.2).
- 5. Juli: Hamiltonische Graphen (Kapitel D8.1; E10.1): Beispiele und Gegenbeispiele. Zusammenspiel mit anderen Grapheninvarianten. Satz von Dirac (D8.1.1; E10.1.1), Proposition von Chvatal und Erdös (D8.1.2; E10.1.2) sowie Satz von Asratian und Khachatrian (D8.1.3; E10.1.3).
- 9. Juli: Satz von Chvatal (Kapitel D8.2.1; E10.2.1). Robustheit und Robustheitsvermutung. Das Quadrat eines t-zusammenhängenden Graphen ist t-robust. Statement Fleischner's Theorem (D8.3.1; E10.3.1) als Spezialfall der Robustheitsvermutung für t=2. (inklusive Übungen D8.5, 8.9 und 8.11).
- 12. Juli: Statement Tutte's Theorem (D8.1.3; E10.1.4). Tutte's Gegenbeispiel, dass 3-zh plättbare kubische Graphen Hamiltonisch sind. Sätze von Sekanina und Thomason (Übungen D8.12, 8.13).
|
