TUM – TUM – Menü

Routenplanung

Graphen sind ein sehr häufig benutztes Modell zur Beschreibung struktureller Zusammenhänge. Sie bestehen aus Knoten, welche mit Kanten (sowohl gerichtet als auch ungerichtet) verbunden sind. Einige prominente Beispiele für den Einsatz von Graphen sind:
  • Routenplanung
    Hier stellen Knoten wichtige Punkte (Kreuzungen, Städte) dar und Kanten entsprechen Verbindungsstraßen. Eine Einbahnstraße wird durch eine gerichtete Kante dargestellt.
  • Kommunikationsnetzwerke (z.B. Telefon, Internet)
    Knoten sind hier Telefone, Modems, Server, Provider und mehr, Kanten die Datenleitungen.
  • Gantt-Diagramme zur Ablaufplanung
    Knoten entsprechen Abschnitten des Projekts, gerichtete Kanten den Abhängigkeiten zwischen den Abschnitten.
  • Abbildung hierarchischer Strukturen

Die Behandlung dieser Modelle mit den Mitteln der algorithmischen Graphentheorie stellt ein wichtiges Teilgebiet der Mathematik und Informatik dar. Einige wichtige Algorithmen aus diesem Gebiet sollen hier vorgestellt werden, sowohl als anschauliche Java-Applets als auch durch ihren Pseudo-Code.

Wir haben begonnen, die Algorithmen zu "renovieren", didaktisch zu überarbeiten und die Java-Applets durch aktuelle Web-Technologien zu ersetzen. Die ersten fertigen Beispiele dafür sind der Bellman-Ford - Algorithmus, der Dijkstra - Algorithmus und der A* - Algorithmus, die restlichen Applets werden nach und nach folgen.

Vorgestellt werden die Algorithmen:

Research Unit M9


Department of Mathematics
Boltzmannstraße 3
85748 Garching b. München
Germany
phone:+49 89 289-16858
fax:+49 089 289-16859
sekretariat-m9ma.tum.de

Professors

Prof. Dr. Peter Gritzmann
Applied Geometry and Discrete Mathematics

Prof. Dr. Andreas S. Schulz
Mathematics of Operations Research
(affiliated member of M9)

Prof. Dr. Stefan Weltge
Discrete Mathematics

News

Jan 25th, 2019
Case Studies 2019: Preliminary Meeting on Wed, Feb 6th, at 16:00 in room MI 03.06.011.