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.
Hat man ein Netzwerk gegeben, so nennt man einen Baum durch alle Knoten, der nur Kanten des Netzwerks benutzt, einen aufspannenden Baum (engl: spanning tree, daher manchmal auch Spannbaum oder spannender Baum). Man kann sich vorstellen einen Regenschirm oder ein Wäschenetz aufzuspannen. Ein aufspannender Baum mit geringsten Kosten oder mit kürzester Gesamtlänge nennt man minimalen aufspannenden Baum.
Wichtig ist bei der Behandlung dieses Themenbereichs in der Schule, die Anwendungsnähe dieses Themas nicht aus den Augen zu verlieren. Hier sehen Sie vier typische Problemstellungen, bei denen minimale aufspannende Bäume eine Rolle spielen:
Hat man ein Netzwerk gegeben, so nennt man einen Baum durch alle Knoten, der nur Kanten des Netzwerks benutzt, einen aufspannenden Baum (engl: spanning tree, daher manchmal auch Spannbaum oder spannender Baum). Man kann sich vorstellen einen Regenschirm oder ein Wäschenetz aufzuspannen. Ein aufspannender Baum mit geringsten Kosten oder mit kürzester Gesamtlänge nennt man minimalen aufspannenden Baum.
Wichtig ist bei der Behandlung dieses Themenbereichs in der Schule, die Anwendungsnähe dieses Themas nicht aus den Augen zu verlieren. Hier sehen Sie vier typische Problemstellungen, bei denen minimale aufspannende Bäume eine Rolle spielen:
- Bahnstrecken-Ausbau für den ICE
Seit den 1990er Jahren werden nach und nach immer mehr Bahnstrecken der Deutschen Bahn so ausgebaut, dass sie für Hochgeschwindigkeitsfahrten des ICE geeignet sind. Es können nicht alle Strecken gleichzeitig ausgebaut werden, aber alle wichtigen Großstädte sollen möglichst schnell an das ICE-Netz angeschlossen werden. - Glasfaser-Netz der Telekom
Auch bei der Telekom hat man ein ähnliches Problem. Hier sollen nach und nach die alten Kupferdraht-Telefonleitungen durch moderne Glasfaserleitungen ausgetauscht werden. Da dies aus Kostengründen nicht sofort mit allen Leitungen geschehen kann, werden zunächst die Hauptvermittlungsstellen an das Glasfasernetz angeschlossen. - Vermietung von Telefonleitungsnetzen
Mobilfunkanbieter leiten Verbindungen von Ferngesprächen durch das Festnetz der Telekom oder anderer Telefonnetzbetreiber. Dazu mieten sie in dem bestehenden Leitungsnetz Verbindungen zwischen den Vermittlungsstellen an. Die Vermittlungsstellen sollen dabei möglichst kostengünstig verbunden werden. - Verkabelung eines Schulgebäudes für Internetanschlüsse
In einer Schule sollen die Compputer in den Klassenzimmern zu einem Netzwerk verbunden und an den Internet-Router angeschlossen werden. Dabei sollen die Kabel in den bereits montierten Kabelkanälen verlegt werden. Das soll möglichst kostengünstig erfolgen, indem die Gesamtlänge des verlegten Kabels klein gehalten wird.