====== Topologische Sortierung von Graphen ======
Bei einem Aufbausimulationsspiel kann man verschiedene Gebäude bauen. Jedes Gebäude produziert eine bestimmte Ware. Damit das Gebäude arbeiten kann, benötigt es seinerseits Waren anderer Gebäude als Rohstoff:
* Die Minen müssen mit Essen versorgt werden, das entweder Fleisch vom Metzger oder Brot vom Bäcker sein kann. Je nach Typ produzieren Minen Kohle oder Eisenerz.
* Die Eisenschmelze stellt daraus das vom Werkzeugmacher benötigte Eisen her.
* Der Werkzeugmacher heizt seine Schmiede mit Kohle und erzeugt aus dem Eisen Sensen für die Getreidefarm, Fleischermesser für den Metzger und Pickel für die Minen.
* Mit dem Getreide der Farm werden die Schweine gefüttert und in der Mühle das Mehl für den Bäcker gemahlen.
* Die Schweine werden vom Metzger geschlachtet.
{{ :faecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:aufbausim.png?400 |}}((Grafik(en): Warenverkehr bei einer Aufbausimulation (alle Bilder Pixabay-Lizenz - kein Nachweis notwendig) ))
Diese Abhängigkeiten machen es schwer zu entscheiden, in welcher Reihenfolge man die Gebäude bauen sollte, damit sie nicht ungenutzt herumstehen.
----
{{:aufgabe.png?nolink |}}
=== (A1) ===
Gib (wenn möglich) eine sinnvolle Baureihenfolge der Gebäude an.
===== Modellierung von Abhängigkeiten =====
Die Problematik der gegenseitigen Abhängigkeiten tritt in vielen Situationen auf. Es wäre also von Vorteil, mit einem Algorithmus entscheiden zu können, ob eine sinnvolle Reihenfolge gefunden werden kann und wenn ja welche.
Eine solche Reihenfolge nennt man **topologische Sortierung auf einem gerichteten Graphen**
----
{{:aufgabe.png?nolink |}}
=== (A2) ===
Modelliere die Situation im Aufbausimulationsspiel als gerichteter Graph.
* Was sind die Knoten, was die Kanten?
* Müssen die Kanten eine Richtung haben oder genügt es, Verbindungen herzustellen?
* Woran kannst du am Graphen erkennen, dass es für das Simulationsspiel keine topologische Sortierung gibt?
++++ Lösung |
{{ :faecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:aufbausimulation-graph.png?600 |}}
Es gibt keine topologiosche Sortierung, weil es nicht möglich ist, einen Graph ohne Zyklus zu finden, der eine Reihenfolge für die Gebäude angibt. das Problem sind die Verbindungen vom Metzger und vom Bäcker zu den Minen, diese können nicht ersetzt werden, damit erhält man zwei Zyklen im Graphen, die man nicht vermeiden kann.
++++
----
{{:aufgabe.png?nolink |}}
=== (A3) ===
Im Computerspiel gibt es zwei Möglichkeiten, //Verklemmungen// zu lösen.
* Weitere Gebäude werden eingeführt: z.B. eine Fischerhütte, die ohne Voraussetzung Essen (Fisch) produziert.
* Man erhält eine Anzahl von Anfangsgegenständen, mit denen man die Produktion in Gang bringen kann: z.B. 20 Pickel.
Gib an, welche Kanten des ursprünglichen Graphen (zumindest vorübergehend) entfernt werden können, wenn man die Fischerhütte hinzufügt und zu Beginn 20 Pickel zur Verfügung stehen. Zeige, dass so die Verklemmung gelöst wird und eine topologische Sortierung nun möglich ist. Zeichne den zu dieser topologischen Sortierung gehörigen Graphen.
++++ Lösung |
{{ :faecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:aufbausimulation-graph-fischerhuette.png?600 |}}
++++
===== Definition: Topologische Sortierung, Reihenfolge =====
Wenn es bei einem gerichteten Graphen eine Abfolge der Knoten des Graphen gibt, so dass für jede Kante k gilt:
Wenn k von A nach B geht, dann steht A vor B in der Abfolge, **dann existiert in diesem Graphen eine topologische Sortierung**.
Um eine **Reihenfolge** anzugeben, muss man eine Abfolge der Knoten des Graphen angeben, so dass für jede Kante k gilt:
Wenn k von A nach B geht, dann steht A vor B in der Abfolge.
Wichtig dabei ist, dass es innerhalb der Reihenfolge der Sortierung **nicht notwendig ist**, stets eine Kante von einem Knoten in der Sortierung zum nächsten zu haben. Es reicht, wenn man die Knoten von links nach rechts in einer Reihenfolge anordnen kann, so dass es keine Kanten gibt, die von rechts nach links zeigen. So kann man den Lösungsgraphen aus der vorigen Aufgabe durch Verschieben der Knoten folgendermaßen anordnen:
{{ :faecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:aufbausimulation-graph-fischerhuette-geordnet.png |}}
Das stellt eine gültige topologische Sortierung dar, auch wenn es keine Kante von der Kohle- zur Erzmine gibt. Man erkennt auf diese Weise auch sofort, dass es mehr als eine topologische Sortierung eines gerichteten Graphen geben kann, die Reihenfolge ist also nicht eindeutig:
{{ :faecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:aufbausimulation-graph-fischerhuette-geordnet2.png |}}
----
{{:aufgabe.png?nolink |}}
=== (Hands-On) ===
Du kannst das selbst ausprobieren, indem du die folgende Datei {{ :faecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:aufbausimulation-graph-fischerhuette.zip |}} herunterlädst und auspackst. Du erhältst die Datei ''Aufbausimulation-Graph-Fischerhuette.excalidraw''. Diese kannst du in [[https://excalidraw.com/|Excalidraw]] öffnen, nun kannst du die Knoten des Graphen auf einer Achse anordnen, so dass es keine Kanten gibt, die von rechts nach links zeigen.
Zum Vergleich, kannst du versuchen, dasselbe Ergebnis mit dem ursprünglichen Graphen (ohne Fischerhütte) zu erzielen: {{ :faecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:aufbausimulation-graph.zip |}} - man kann sehr gut erkennen, wie ein Zyklus im Graph eine topologische Sortierung unmöglich macht.
===== Algorithmus =====
{{:aufgabe.png?nolink |}}
=== (A4) ===
Öffne im Graphentester das Beispiel ''02_topologischesortierung/02_aufbausimulation2.csv''. Untersuche die Situation mit Hilfe des bereits im Graphentester implementierten Algrithmus "Topologogische Sortierung".
{{ :faecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:ts_gt.png?600 |}}
Formuliere den Algorithmus als Pseudocode.
++++ Hilfestellung: Verbale Beschreibung des Algorithmus |
Bei jedem Knoten wird als Wert die Anzahl der eingehenden Kanten (Eingangsgrad) eingetragen. Das ist die Anzahl der noch unerfüllten Voraussetzungen.
Danach wiederholt man folgendes:
* Suche einen noch unmarkierten Knoten, der den Wert 0 hat (= alle Voraussetzungen sind erfüllt). Füge diesen der topologischen Sortierung hinzu und markiere ihn als bearbeitet. Reduziere den Wert aller Knoten um 1, zu denen eine Kante vom aktuellen Knoten führt.
* Gibt es keinen Knoten mit dem Wert 0 und es sind noch nicht alle Knoten abgearbeitet, dann ist es nicht möglich, eine topologische Sortierung zu finden.
++++
++++ Lösung: Pseudocode |
Topologische Sortierung:
Für jeden Knoten k des Graphen:
setze den Wert des Knoten auf seinen Eingangsgrad
Setze topologische_Sortierung auf leer
Wiederhole solange es einen unmarkierten Knoten mit Wert 0 gibt
Nimm einen unmarkierten Knoten k mit Wert 0
Markiere k
Füge k der topologische_Sortierung hinzu
Für jeden Nachbarknoten n von k:
reduziere den Wert des Knoten n um 1
Ende Wiederhole
Falls noch unmarkierte Knoten übrig sind:
Ausgabe: es gibt keine topologische Sortierung
sonst:
Ausgabe: topologische_Sortierung ist gefunden
++++
----
{{:aufgabe.png?nolink |}}
=== (A5) ===
Implementiere den Algorithmus selbst in einer eigenen Klasse unter "eigene Algorithmen". Teste deinen Algorithmus an den Beispielen ''03_beispiel_obst.csv'' und ''04_beispiel_obst2.csv''.
++++ Lösungsvorschlag Algorithmus |
// Reihenfolge
String Reihenfolge = "";
// Hole alle Knoten vom Graph g
List alleKnoten = g.getAlleKnoten();
// Schleife über alle Knoten
for(Knoten k: alleKnoten) {
int Eingangsgrad = g.getEingehendeKanten(k).size();
k.setWert(Eingangsgrad);
k.setFarbe(7);
}
step();
boolean sort=true;
while(alleKnoten.size() > 0 && sort) {
Collections.sort(alleKnoten);
Knoten k = alleKnoten.remove(0);
if (k.getIntWert() == 0) {
k.setFarbe(4);
Reihenfolge += k.getInfotext() + " ";
for(Knoten n: g.getNachbarknoten(k)) {
n.setWert(n.getIntWert()-1);
}
} else {
sort=false;
}
step();
}
if (! sort) {
System.out.println("Keine Sortierung möglich!");
} else {
System.out.println(Reihenfolge);
}
++++
----
{{:aufgabe.png?nolink |}}
=== (A6) Rangliste ===
Im Tennisclub "Blau-Weiß" wird normalerweise im Laufe des Jahres eine Rangliste der Spieler
ausgespielt. Dazu spielt jeder gegen jeden. In diesem Jahr mussten aber umfangreiche
Bauarbeiten am Platz durchgeführt werden. Die Saison neigt sich nun dem Ende, es haben aber
noch nicht alle Paarungen stattgefunden. Die Tabelle gibt Auskunft, wie die Spiele nach Sätzen
ausgegangen sind. Der Eintrag in der dritten Spalte der zweiten Zeile bedeutet z.B., dass Albert
mit 1:3 gegen Boris verloren hat.
{{ :faecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:tabelle.png?600 |}}
* Modelliere die Situation als Graph. Was sind die Knoten? Was wird durch die Kanten beschrieben? Wäre es möglich die Situation durch einen ungerichteten Graphen zu modellieren?
* Verwende den Graphentester, um zu untersuchen, ob es eine Sortierung gibt. Gib, wenn möglich die Rangliste an.
* Ist die Rangliste eindeutig?
----
{{:aufgabe.png?nolink |}}
=== (A7) Gruppenarbeit ===
Für eine Gruppenarbeit bilden die Schüler einer Klasse vier Gruppen. Alle Gruppen teilten
ihre Arbeit in einzelne Aufgaben auf. Drei Gruppen konnten alle ihre Aufgaben erledigen,
aber eine Gruppe wird nicht fertig.
Die schlausten Schüler, Ada und Charles, haben die vier Gruppen analysiert.
Sie fanden heraus, dass die meisten Gruppenmitglieder auf andere warten mussten,
bevor sie mit ihrer eigenen Aufgabe beginnen konnten.
Ada und Charles haben für jede Gruppe eine Skizze gezeichnet,
die sich auf das Wesentliche konzentriert.
Ein Kreis stellt eine Person dar. Ein Pfeil von Person 1 nach Person 2 bedeutet,
dass Person 1 ihre Aufgabe erledigt haben musste, bevor Person 2 mit ihrer Aufgabe beginnen konnte.
**Welches Bild entspricht der Gruppe, die nicht fertig wurde?** (Begründe deine Antwort)
{{ :faecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:gruppenarbeit.png |}}
----
{{:aufgabe.png?nolink |}}
=== (A8) Kochplatten ===
((Aufgabe aus dem Informatik-Biber-Wettbewerb 2013. https://bwinf.de/biber/archiv/aufgabensammlung/ -- Copyright 2013 BWINF - GI e.V. (Lizenz CC-BY-SA 3.0) ))
Anna und Ben kommen hungrig nach Hause. Nun möchten sie möglichst schnell zu Abend essen. Im Kühlschrank sind Brokkoli, Fisch, Tomaten und Fleisch. Daraus wollen sie zwei Gerichte zubereiten. Die Zubereitung erfolgt in mehreren Schritten. Die meisten Schritte können Anna und Ben erst dann beginnen, wenn sie andere Schritte bereits erledigt haben.
Im Bild sind die Schritte als Kreise und die Abfolge der Schritte mit Pfeilen dargestellt.
{{ :faecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:biberkochen.png |}}
Annas und Bens Herd hat drei Herdplatten. Sie können also maximal drei Schritte gleichzeitig erledigen. Für jeden Schritt benötigen sie 5 Minuten.
Frage: **Wie viele Minuten benötigen sie für die Zubereitung der beiden Gerichte mindestens?**
++++ Lösung |
{{ :faecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:2024-03-19_15-44.png |}}
++++
==== Dateien ====
{{simplefilelist>.:*}}