faecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:start

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung
Nächste Überarbeitung		 Vorherige Überarbeitung
faecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:start [17.11.2022 09:09] – Frank Schiebelfaecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:start [11.06.2024 13:21] (aktuell) – Frank Schiebel
Zeile 1: Zeile 1:
 ====== Topologische Sortierung von Graphen ====== ====== Topologische Sortierung von Graphen ======
-{{:faecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:aufbausim.png?400  |}}((Grafik(en): Warenverkehr bei einer Aufbausimulation (alle Bilder Pixabay-Lizenz - kein Nachweis notwendig) ))+
 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: 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:
  
Zeile 8: Zeile 8:
   * Mit dem Getreide der Farm werden die Schweine gefüttert und in der Mühle das Mehl für den Bäcker gemahlen.    * 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.    * 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.  Diese Abhängigkeiten machen es schwer zu entscheiden, in welcher Reihenfolge man die Gebäude bauen sollte, damit sie nicht ungenutzt herumstehen. 
Zeile 41: Zeile 43:
 {{ :faecher:informatik:oberstufe:graphen:zpg:topologische_sortierung:aufbausimulation-graph.png?600 |}} {{ :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.+Es gibt keine topologische 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.
  
 ++++ ++++
Zeile 234: Zeile 236:
  
 Frage: **Wie viele Minuten benötigen sie für die Zubereitung der beiden Gerichte mindestens?** 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 ==== ==== Dateien ====
  
 {{simplefilelist>.:*}} {{simplefilelist>.:*}}
  • faecher/informatik/oberstufe/graphen/zpg/topologische_sortierung/start.1668676164.txt.gz
  • Zuletzt geändert: 17.11.2022 09:09
  • von Frank Schiebel