Graphen

Nach einer motivierenden Einführung wird die Geschichte der Graphentheorie dargestellt.

Anschließend werden diverse Problemfelder vorgestellt, die mit Hilfe von Graphen modelliert, und mit Algorithmen aus der Theorie der Graphen gelöst werden können.

Schließlich werden die entwickelten Algorithmen in Java-Programmen implementiert.

Leonhard Euler wohnte in Königsberg und wollte einen besonderen Spaziergang planen. Solche Spaziergänge werden nach diesem berühmten Mathematiker heute Euler-Wege genannt.

Ob und wie man ggf. solche Euler-Wege findet, wird in diesem Abschnitt näher untersucht.

Auch Hamilton hatte ein Problem. Er suchte in Graphen nach Wegen, die jeden Knoten genau einmal enthalten. Ein solcher Weg wird Hamilton-Weg genannt.

Ob und wie man ggf. solche Hamilton-Wege findet, wird in diesem Abschnitt näher untersucht.

Kürzeste Wege

Hier werden wir uns auf die Suche nach kürzesten Verbindungen zwischen zwei Knoten eines Graphen machen. Navigationsgeräte z.B. sind ohne einen schnellen Algorithmus undenkbar.

Dabei werden wir erfahren, dass es zur Lösung einen beeindruckenden Algorithmus gibt, der von dem niederländischen Mathematiker E.W.Dijkstra entwickelt wurde.

Minimale Spannbäume

Wie kann man in einem Graphen ein kostengünstigstes Teilnetz so erstellen, dass es zwischen je zwei Knoten eine (ggf. indirekte) Verbindung gibt?

Der Algorithmus von Prim löst das Problem auf einfache Weise.

Travelling-Salesman-Problem

Bei diesem klassischen Problem geht es darum, einen Algorithmus zu finden, der die kürzeste Rundreise in einem Graphen berechnet, wobei alle Knoten besucht werden. Bisher wurde noch kein "schneller" Algorithmus gefunden.