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.

¹⁾

Diese Abhängigkeiten machen es schwer zu entscheiden, in welcher Reihenfolge man die Gebäude bauen sollte, damit sie nicht ungenutzt herumstehen.

Gib (wenn möglich) eine sinnvolle Baureihenfolge der Gebäude an.

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

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

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:

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:

Du kannst das selbst ausprobieren, indem du die folgende Datei aufbausimulation-graph-fischerhuette.zip herunterlädst und auspackst. Du erhältst die Datei Aufbausimulation-Graph-Fischerhuette.excalidraw. Diese kannst du in 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: aufbausimulation-graph.zip - man kann sehr gut erkennen, wie ein Zyklus im Graph eine topologische Sortierung unmöglich macht.

Öffne im Graphentester das Beispiel 02_topologischesortierung/02_aufbausimulation2.csv. Untersuche die Situation mit Hilfe des bereits im Graphentester implementierten Algrithmus "Topologogische Sortierung".

Formuliere den Algorithmus als Pseudocode.

Hilfestellung: Verbale Beschreibung des Algorithmus

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

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<Knoten> 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);
}

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.

• 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?

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)

²⁾ 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.

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