Dr. Theo Overhagen
Graphentheorie WS 2020/21
Termine
| Vorlesung | Vorlesung | Übung |
|---|---|---|
| Mittwoch, 10-12 Uhr, Beginn 28.10.2020 | Freitag 14-16 Uhr, Beginn 30.10.2020 |
Ein Graph ist eine Menge von Punkten, die möglicherweise durch Linien miteinander verbunden sind. Damit können durch Graphen Situationen mathematisch modelliert werden, in der eine „Beziehung“ zwischen bestimmten Objekten definiert ist.
Zum Beispiel kann man mit Graphen Sympathie oder Antipathie zwischen Personen beschreiben, Bindungen zwischen den Atomen innerhalb eines Moleküls, Verbindungen zwischen Gehirnzellen oder Stammbäume verschiedener Spezies. Man kann aber auch die verschiedenen Stadien eines großen Bauprojekts durch Ecken darstellen und zwei Ecken dann durch eine gerichtete Linie verbinden, wenn ein Projekt-Stadium aus einem anderen durch eine einzige Arbeitsphase hervorgeht.
Natürlich ist es auch naheliegend, Graphen zu betrachten, bei denen die Punkte verschiedene Städte darstellen und die Linien Straßen (oder Bahnlinien oder Versorgungsleitungen) zwischen diesen Städten. Damit erhält man eine anschauliche Grundlage zur Erarbeitung von Algorithmen, die zum Beispiel den kürzesten Weg zwischen zwei Städten (Navi), die größtmögliche Durchflußmenge durch ein Leitungsnetz oder die günstigste Anschlußmöglichkeit von Städten an ein zentrales Wasserwerk berechnen.
Die Bedeutung der Graphentheorie liegt in der Anwendungsmöglichkeit auf Optimierungsprobleme, und daher werden solche auch sporadisch einbezogen. Allerdings werden die angesprochenen Algorithmen nur skizziert und weder implementiert noch auf Komplexität untersucht.
Die Vorlesung richtet sich vorwiegend an Studenten im Lehramt Mathematik für Haupt-/Realschule (Master/M1HR) und für Gymnasien und
