Gewichtete Graphen
In der Praxis sind Graphen oft gewichtet. Das bedeutet, dass den Kanten im Graph eine reelle Zahl zugeordnet ist. Damit wird meist eine Art von Kosten für den Transport entlang dieser Kanten modelliert. So sind z. B. bei den Graphen, die Navigationssysteme verwenden, die Knoten Adressen und Kreuzungen, die Kanten Straßen und die Gewichte die durchschnittlichen Fahrzeiten auf diesen Straßen. So kann anschließend darauf aufbauend die Gesamtfahrzeit von Adresse $A$ zu Adresse $B$ optimiert werden. Es können auch mehrere Arten von Gewichten in einem Graphen auftauchen. Hat das Navigationsgerät z. B. noch Informationen zu den Kosten auf Mautstraßen gespeichert, kann es versuchen die Gesamtfahrzeit und die Gesamtmautkosten gleichzeitig zu reduzieren.
Wie der folgende Ausschnitt aus Szene 1: Einführung anhand von Graphen aus dem Alltag illustriert, können solche Kantengewichte – und auch die im vorherigen Abschnitt erwähnten, anderen Eigenschaften von Graphen – im Unterricht explorativ eingeführt werden.
Das Entscheidende hier ist, dass spezielle Graphen (insbesondere gewichtete) zur Modellierung verschiedenster Sachverhalte verwendet werden. Es soll hier im Anschluss allerdings weniger auf die allgemeine Verwendung von Graphentheorie zur Lösung praktischer Probleme eingegangen werden, sondern im Folgenden auf (Binär-)Bäume als Datenstruktur der Informatik.
Um aber einen Eindruck dafür zu bekommen, wie kompliziert Optimierung auf gewichteten Graphen werden kann, wenn die Knoten und Kantenzahl steigt, ist hier eine dynamisch-interaktive Visualisierung eines vereinfachten Navigationssystems abgebildet. Die Aufgabe besteht darin, einen Pfad zu finden, der zwei gegebene Knoten miteinander verbindet. Ein Pfad ist dabei eine Folge von Kanten, sodass zwei aufeinanderfolgende Kanten einen Knoten gemeinsam haben. Außerdem soll der Pfad so kurz wie möglich sein – die Summe aller Kantengewichte im Pfad soll also minimiert werden. Die Herausforderung hierbei besteht darin, die abstrakte Ansicht zu verwenden, welche die Datenstruktur illustriert, mit der Computer tatsächlich arbeiten. Die konkrete Ansicht, die Menschen bei der Wegfindung verwenden würden, steht Computern nicht direkt zur Verfügung.
Der gegebene Graph zeigt ein (fiktives) Autobahnnetz zwischen verschiedenen deutschen Städten.
Anleitung: Am Schieberegler rechts oben kann die Anzahl der Knoten (Städte) verändert werden. Mit einem Klick auf den grünen Neu-Knopf werden zwei Städte vorgeben lassen, die dann durch einen möglichst kurzen Pfad miteinander verbunden werden sollen. Mit einem Klick auf den Überprüfen!-Knopf, der dann zu sehen ist, kann die eigene Lösung überprüft werden. Mit den Abstrakt- beziehungsweise Konkret-Knöpfen zwischen dem gegebenen Graph, der in die Deutschlandkarte eingebettet ist, und einem unanschaulichen Graphen wechseln.
Weiterführende Informationen zur Einführung von Graphen finden Sie in (Aigner, 2015).