240033 Proseminar zur Graphentheorie (PS) (WiSe 2022/2023)

Die Graphentheorie ist ein Teilgebiet der Kombinatorik mit vielfältigen Bezügen zu verwandten Disziplinen der Mathematik, z.B.\ zur Algebra oder Stochastik.
Graphen spielen aber auch in vielen Anwendungsgebieten eine wichtige Rolle, beispielsweise beim Berechnen von kürzesten Wegen in Navigationssystemen.

Im Proseminar untersuchen wir Graphen in der Theorie und Praxis.
Auf der theoretischen Seite beweisen wir beispielsweise, dass sich Landkarten immer mit höchstens 5 Farben so färben lassen, dass benachbarte Länder mit verschiedenen Farben gefärbt sind.
In der angewandten Richtung besprechen wir unter anderem wie ein Lieferdienste eine möglichst kurze Route berechnet, um alle Pakete auszuliefern.
Im Laufe des Seminars werden wir diverse Aspekte der Graphentheorie beleuchten und dadurch verstehen, weshalb Graphen zentrale Objekte der reinen und angewandten Mathematik sind.

Bibliography

• Martin Aigner und Günter M. Ziegler, Das BUCH der Beweise, 5. Auflage, Springer Berlin, Heidelberg, 2018.
• Sven O. Krumke und Hartmut Noltemeier, Graphentheoretische Konzepte und Algorithmen, 3. Auflage, Vieweg+Teubner Verlag Wiesbaden, 2012.