Druckversion vom 02.05.2024 15:13 Uhr
Startseite Qualifikationsphase Datenstrukturen Graphen
Graphen
Grundlagen
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. |
||
Euler-Touren
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. |
||
Hamilton-Reisen
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. |
|
|
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. |
||
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. |
||
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. |