Euler und das Haus vom Nikolaus - Eine Einführung in die Graphentheorie

Inhalt

Das Haus vom Nikolaus zeichnen, ohne den Stift abzusetzen - das ist einfach. Aber wie findet man Rundwege in großen Städten, die kürzeste Route für den Paketboten oder gute Färbungen von Landkarten? Leonhard Euler begann mit der Beantwortung solcher Fragen schon 1736, als er in Königsberg spazieren ging - und bis heute wird daran geforscht. Nur mit Stift und Papier lösen auch wir einige Probleme aus der Graphentheorie.

Im Workshop werden die Grundbegriffe der Graphentheorie eingeführt und zur Modellierung klassischer Probleme (Routing-Algorithmen, Vier-Farben-Satz) genutzt. Anhand des Königsberger Brückenproblems wird ein Kriterium für die Existenz von Eulerkreisen in zusammenhängenden Graphen erarbeitet.