Das Kalifat Sandreich

Der Kalif des Wüstenstaates Sandreich möchte die elf Städte seines Landes mit Straßen verbinden: Aasheim, Brunnenberg, Camel City, Durstingen, Eidechsenhausen, Fatamorganingen, Geiersheim, Heisslach, Kaktusheim, Langmarschingen und Mittenimnirgendwo. Dabei soll jede Stadt mit jeder anderen über Straßen erreichbar sein. Die Straßen sollen jedoch nur entlang der bereits bestehenden alten Karavanenpfade gebaut werden, weil es nur dort ausreichend Brunnen gibt.
Lesen Sie mehr...

Ein Straßennetz für das Kalifat

Versuche doch mal, ein möglichst gutes Straßennetz zu bauen!
 Lesen Sie mehr...

Ein optimales Straßennetz im Kalifat

Lassen wir doch einmal den Computer ein optimales Straßennetz finden!
In dem folgenden Applet können zwei verschiedene Algorithmen, die Algorithmen von Prim und von von Kruskal, auf das Netz der Karawanenpfade von Sandreich angewendet werden. Die grünen Verbindungen zeigen dann ein optimales Straßennetz.
 Lesen Sie mehr...

Zwei einfache Algorithmen

Untersuche die beiden Algorithmen nun noch weiter! Zeichne dir dazu eigene Netze!
 Lesen Sie mehr...

Der Algorithmus von Prim

Einer der einfachsten Algorithmen zur Lösung des Problems minimal aufspannender Bäume ist der Algorithmus von Prim. Benannt wurde dieser Algorithmus nach Robert Prim von den Bell Labs, der ihn 1957 veröffentlichte. Unabhängig von Prim wurde dieser Algorithmus bereits 1930 von Vojtech Jarnik und später 1959 von Edsger Wybe Dijkstra entwickelt.
 Lesen Sie mehr...

Der Algorithmus von Kruskal

Ein weiterer Greedy-Algorithmus zur Berechnung eines minimalen aufspannenden Baumes ist der Algorithmus von Kruskal. Dieser 1956 von Joseph Kruskal (ebenfalls von den Bell Labs) veröffentlichte Algorithmus untersucht in jedem Schritt eine billigste unbehandelte Kante und wählt diese, falls sie keinen Kreis schließt. Anders al der Algorithmus von Prim wird also nicht von einem Knoten ausgegangen. Stattdesen startet man mit allen Knoten und verschmilzt in jedem Schritt zwei Zusammenhangskomponenten zu einer neuen, bis ein aufspannender Baum entsteht. Lesen Sie mehr...

Hintergrund: Minimale Aufspannende Bäume

Minimale aufspannende Bäume sind in vielen Anwendungsgebieten der kombinatorischen Optimierung von Bedeutung, vor allem immer dann, wenn man in einem bestehenden Netzwerk vorhandene Knoten möglichst kostengünstig verbinden will. Anwendungsbeispiele sind der Ausbau von Leitungsnetzen für die Telekommunikation, die Planung von Straßennetzen oder das Chipdesign. Da bei der Lösung dieser Probleme besonders einfache Graphen, sogenannte Bäume, eine Rolle spielen, lassen sich entsprechende Fragestellungen bereits frühzeitig in der Sekundarstufe I untersuchen. Dabei können interessante Eigenschaften dieser Graphen von Schülern selbständig entdeckt werden. Die naheliegenden Lösungsalgorithmen sind so einfach, dass sie von den Schülern selbst entdeckt und mit nur geringen Programmierkenntnissen in Visage umgesetzt werden können.
 Lesen Sie mehr...

Didaktische Hinweise zu MST

Der Lernpfad auf dieser Seite ist so gestaltet, dass er von Schülerinnen und Schülern selbständig durchgearbeitet werden kann, um die Problemstellung und zwei mögliche Lösungsalgorithmen kennenzulernen. Die Beispielaufgabe zur eigenständigen Konstruktion eines minimalen aufspannenden Baumes ist dabei auch als Einstieg in eine Lerneinheit zu diesem Thema im Klassenunterricht geeignet.
 Lesen Sie mehr...

Materialien und Literaturhinweise zu MST

Als weiterführende Literatur zur Unterrichtsvorbereitung empfehlen wir:
 Lesen Sie mehr...