Informationen zum Proseminar "Resultate und Anwendungen der Graphentheorie" (SS 2023)
Dozent: Dr. Ernst August Frhr. v. Hammerstein
Termin: Di 16-18, HS II, Albertstr. 23b
Voranmeldung: Interessenten melden bitte ihren Teilnahmewunsch bis spätestens zum 06.02.2023 per Mail an
ernst.august.hammerstein@stochastik.uni-freiburg.de
Graphen sind im Prinzip sehr einfache mathematische Objekte, die lediglich aus einer Menge von Knoten bzw. Ecken bestehen sowie einer Menge von (gerichteten oder ungerichteten) Kanten, die jeweils zwei Knoten verbinden. Trotz ihrer Einfachheit, die sie für viele mathematische wie auch praktische Probleme (z.B. Darstellung von Netzwerken, Abhängigkeitsstrukturen u.ä.) einsetzbar macht, ergeben sich schnell Fragen, die nicht ganz so leicht zu beantworten sind, beispielsweise: Wie viele Farben braucht man mindestens, um die Knoten eines vorgegebenen Graphen so einzufärben, dass jeweils zwei durch eine Kante verbundene Knoten verschiedene Farben haben?
In diesem Proseminar sollen einige der vielfältigen Eigenschaften von Graphen vorgestellt werden, die (hoffentlich) reizvolle Beweise und/oder Anwendungen haben. Erstere verwenden (neben ein paar kombinatorischen Überlegungen) hauptsächlich Ideen und Methoden der Linearen Algebra und sollten daher bereits mit Kenntnissen der Grundvorlesungen zugänglich sein. Das u.g. Buch von Diestel bietet eine gute Einführung sowie Grundgerüst zur Graphentheorie, einige Vorträge werden aber auch auf den anderen Quellen basieren, die mitunter schönere Beweisideen und Anwendungsmöglichkeiten beinhalten.
Aktuelles
- Am 06.06.2023 findet das Proseminar ausnahmsweise in SR 404, Ernst-Zermelo-Str. 1, statt, da der HS II durch ein ganztägiges Kolloquium belegt ist.
- Der genaue Zeitplan für die einzelnen Vorträge ist nach Absprache mit allen Teilnehmenden festgelegt und veröffentlicht.
Vortragsthemen und -Termine
| Datum | Thema | Quelle(n) |
| 18.04.23 | Einführung und Grundbegriffe | Diestel, Kap. 0.1-0.3, West, Kap. 1.1 |
| 25.04.23 | Eulergraphen und Hamiltonkreise | Diestel, Kap. 08 und 8.1-8.2 |
| 02.05.23 | Zusammenhang und Mengers Theorem | Diestel, Kap. 0.4 und (Teile von) Kap. 2.1-2.3 |
| 09.05.23 | Bipartite Graphen und das Heiratstheorem | Diestel, Kap. 0.6 und 1.1 |
| 16.05.23 | Bestimmung der Anzahl von Spannbäumen | Diestel, Kap. 0.5, Matoušek, Miniatur 21 |
| 23.05.23 | Ebene Graphen und Eulers Formel | Diestel, Kap. 3.1-3.2, Aigner/Ziegler, Kap. 13 |
| 06.06.23 | Flüsse und Netzwerke | Diestel, Kap. 5.1-5.2 und 5.4 |
| 13.06.23 | Graphenalgorithmen | West, Kap. 2.3 |
| 20.06.23 | Permanenten und Entropie | Aigner/Ziegler, Kap. 37 |
| 27.06.23 | Das Dinitz-Problem und ein 5-Farben-Satz | Aigner/Ziegler, Kap. 38 und 39 |
| 04.07.23 | Kommunikation ohne Fehler | Aigner/Ziegler, Kap. 42, Matoušek, Miniatur 28 |
| Der Satz von Turan, Museumswächter, Freunde und Politiker | Aigner/Ziegler, Kap. 40, 41, 44 | |
| 11.07.23 | Petersen-Graph und chromatische Zahl des Kneser-Graphen | Aigner/Ziegler, Kap. 43, Matoušek, Miniatur 14 |
| 18.07.23 | Die probabilistische Methode | Aigner/Ziegler, Kap. 45 |
Hinweise zur Vortragsdurchführung
Der Vortrag sollte weitgehend frei gehalten werden, entweder an der Tafel oder mit Folien. Bei Folienvorträgen sollte generell beachtet werden, dass man mit Folien i.A. deutlich schneller vorträgt, vielleicht auch mal zu schnell für die Zuhörerinnen und Zuhörer. Daher ist es oft empfehlenswert, Folien nicht zu überfrachten und schrittweise aufzubauen. Manche Gedanken, Gleichungsketten oder Beweise lassen sich womöglich an der Tafel langsamer und damit besser verständlich entwickeln. Demgegenüber können längere Definitionen, Sätze oder Formeln mit Hilfe von Folien schneller und übersichtlicher präsentiert werden.
Zur besseren Zeitplanung und -einteilung empfiehlt es sich, den eigenen Vortrag bzw. Teile davon zuhause einmal vorzusprechen, um dessen Dauer besser abzuschätzen. Probieren Sie ggf. vorab auch einmal aus, wie gut und schnell sie an der Tafel schreiben können, wenn Sie diese benutzen wollen. Typischerweise ist man dabei doch merklich langsamer als bei Schreiben auf Papier.
Gelegentliche kurze Pausen für Verständnisfragen können auch nicht schaden. Ferner kann es - je nach Vortragsthema - auch sinnvoll sein, ein Handout mit zentralen Definitionen, Sätzen und Formeln zu erstellen und vor Beginn des Vortrags auszuteilen, damit man diese während des Vortrags im Blick haben und behalten kann. Versuchen Sie, Sätze und Definitionen auch anschaulich oder durch Anwendungsbeispiele zu motivieren und sich in Ihr Publikum hineinzuversetzen: Könnten Sie selbst Ihrem Vortrag folgen, auch wenn Sie sich nicht zuvor ausführlich mit dem Thema beschäftigt hätten? Mit Blick auf potentielle Fragen der anderen Proseminarteilnehmerinnen und -Teilnehmer kann es auch nicht schaden, etwas mehr über das Vortragsthema zu wissen als man in der Präsentation erwähnt.
Bedenken Sie, dass das Ziel und die Aufgabe des Vortrags darin besteht, Ihren Kommilitoninnen und Kommilitonen etwas verständlich zu machen! Es reicht nicht, den Dozenten davon zu überzeugen, dass Sie das Thema verstanden haben.
Notwendige Vorkenntnisse
Studien- und Prüfungsleistung
Literatur
- M. Aigner, G. M. Ziegler: Das BUCH der Beweise (5. Auflage), Springer, 2018.
Aus dem Uni-Netz verfügbar unter https://www.redi-bw.de/start/unifr/EBooks-springer/10.1007/978-3-662-57767-7 - R. Diestel: Graphentheorie (3. Auflage), Springer, 2006.
Verfügbar unter http://www.math.ethz.ch/EMIS/monographs/Diestel/de/GraphentheorieIII.pdf
Von diesem Buch gibt es inzwischen auch eine 5. Auflage (von 2017) in Deutsch und Englisch, die englische ist aus dem Uni-Netz verfügbar unter http://www.redi-bw.de/start/unifr/EBooks-springer/10.1007/978-3-662-53622-3. - J. Matoušek: Thirty-three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra, AMS, 2010.
Verfügbar unter kam.mff.cuni.cz/~matousek/stml-53-matousek-1.pdf - D. B. West: Introduction to Graph Theory (Second Edition), Pearson, 2001.
Verfügbar unter athena.nitc.ac.in/summerschool/Files/West.pdf
Sprechstunde