Problem der topologischen Sortierung eines gerichteten Graphs (optional)
Begriffe: gerichtete Kante, Zyklus, Grad eines Knoten (Ausgangsgrad, Eingangsgrad), Abhängigkeitsgraph
Beim Euler-Kreis suchte man einen zyklischen Pfad, der alle Kanten des Graphen umfasst. Für viele andere Anwendungen ist es aber auch schon interessant, ob es überhaupt einen Zyklus gibt. Ein ungerichteter Graph ohne Zyklen ist ein Baum, mit dem zum Beispiel Hierarchien gut dargestellt werden können. Interessanter wird es, wenn man gerichtete Graphen verwendet.
Bildquelle: Henne-Ei-Problem: Verklemmung bei topologischer Sortierung (eigene Abbildung) ZPG Informatik [CC BY-NC-SA 3.0 DE], aus 2_unterrichtsverlauf.odt
Stellt man mit dem Graphen Abhängigkeiten von Aktionen dar (z.B. muss man zuerst Socken anziehen, bevor man die Schuhe anzieht), erhält man einen Abhängigkeitsgraph. Enthält der Graph keine Zyklen, dann gibt es mindestens eine Reihenfolge, in der man die Tätigkeiten durchführen muss, um alle Abhängigkeiten zu berücksichtigen. Man erhält eine sogenannte topologische Sortierung4 . Enthält der Graph Zyklen, ist dies unmöglich, es entsteht eine Verklemmung, da für keine Aktion alle Voraussetzungen erfüllt sind. Relevant ist dies z.B. beim Zugriff auf Ressourcen von parallel laufenden Prozessen oder beim Einfügen in eine Datenbank, bei der zu jedem Zeitpunkt die referenzielle Integrität gewährleistet sein soll.
Diese Problemstellung stellt die Richtung einer Kante in den Vordergrund und führt eine neue Interpretation von Graphen (Abhängigkeitsgraph) ein. Da gerichtete Kanten an anderen Beispielen deutlich gemacht werden können und Abhängigkeitsgraphen nicht im Bildungsplan gefordert sind, kann diese Anwendung auch entfallen. Es ist aber sinnvoll, wenn im Unterricht nicht nur Kartengraphen eingesetzt werden, da dies die Vielfalt der Anwendungsmöglichkeiten nicht ausreichend wiedergibt.
Gelöst wird das Problem, indem man bei jedem Knoten den Eingangsgrad als Wert einträgt. Wenn der Graph nicht zyklisch ist, muss es mindestens einen Knoten geben, der den Wert 0 hat. Diesen "entfernt" man aus dem Graph, d.h. man reduziert die Werte aller von ihm abhängigen Knoten um 1. Dadurch muss es mindestens einen weiteren Knoten mit Wert 0 geben. Dies wiederholt man, bis man alle Knoten entfernt hat. Die Reihenfolge des Entfernens ist die topologische Sortierung des Graphen.
Auch hier können Sie wieder die verschiedenen Unterrichtsformen zur Erarbeitung des Algorithmus einsetzen. Variieren Sie die Unterrichtsform.
4 Topologische Sortierung bezeichnet in der Mathematik eine Reihenfolge von Dingen, bei der vorgegebene Abhängigkeiten erfüllt sind. Seite „Topologische Sortierung“. In: Wikipedia, Die freie Enzyklopädie. URL: https://de.wikipedia.org/w/index.php?title=Topologische_Sortierung (abgerufen: 21. September 2020)
Unterrichtsverlauf: Herunterladen [odt][298 KB]
Weiter zu Problem des kürzesten Pfades in ungewichteten Graphen