Graphentheorie M1 HR 1 M2 GB 1 BV.G 1

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 deniert 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 Vorlesung richtet sich vorwiegend an Studenten im Fachstudium Mathematik mit Abschluß Bachelor ab 3. Semester, Studenten im Lehramt Mathematik für Gymnasien und Gesamtschulen sowie Berufskolleg (Staatsexamen/Hauptstudium Modul Geometrie bzw. Master/M2GB, elementarmath. Vertiefung). 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. Wird in der Vorlesung bekanntgegeben. Mathematik Universität Siegen WiSe 2014/15 Dr. Overhagen Theo