Einleitung
Mit Einführung des neuen Bildungsplans ist das Thema "Graphen" neu hinzugekommen. Graphen vervollständigen die Sammlung von Datenstrukturen, die bisher aus Listen und Bäumen bestand 1. Graphen sind für eine Vielzahl von Anwendungen eine geeignete Modellierung, für die viele Standardalgorithmen zur Verfügung stehen. Der Bildungsplan sieht vor diese Algorithmen "von Hand" durchzuführen oder im Leistungsfach auch mit Hilfe einer geeigneten Bibliothek zu implementieren.
Die Aufgabe des Unterrichts besteht also darin,
- die Begrifflichkeiten im Zusammenhang mit Graphen aufzubauen,
- den Schülerinnen und Schülern das Modellieren einer Anwendungssituation mit Hilfe eines Graphen nahezubringen
- Algorithmen auf Graphen anzuwenden, zu entwickeln oder zu implementieren.
Herangehensweise
Es sind verschiedene Herangehensweisen an einen Algorithmus vorstellbar. Sie sollten in Ihrem Unterricht unterschiedliche Methoden einsetzen.
Ausgehend von einem konkreten Anwendungsfall steht am Anfang immer die Modellierung der Ausgangssituation als Graph. Dazu müssen die Schülerinnen und Schüler unwichtige von wichtigen Informationen unterscheiden und festlegen, welche Bedeutung Knoten und Kanten für die Anwendungssituation haben. In Zuge der Modellbildung muss auch festgelegt werden, ob mit einem gerichteten und/oder gewichteten Graphen gearbeitet werden muss. Gegebenenfalls kann man auch schon festlegen, welche Bedeutung der an einem Knoten bzw. einer Kante gespeicherte Wert haben soll.
Für die konkrete Situation notwendige Fachbegriffe sollten an dieser Stelle eingeführt werden. Die Schülerinnen und Schüler können sie in Form eines Glossars festhalten. Dann entsteht im Laufe der Unterrichtseinheit eine Sammlung der wichtigsten Fachbegriffe. Achten Sie bei der Auswahl der behandelten Graphen-Probleme darauf, dass alle vom Bildungsplan vorgeschriebenen Fachbegriffe eingeführt werden: Knoten, Kanten, Knotengrad, Kreis/Zyklus, gerichtet/ungerichtet, gewichtet/ungewichtet, zyklisch/azyklisch.
1 Eigentlich sind natürlich Listen und Bäume spezielle Graphen.
Unterrichtsverlauf: Herunterladen [odt][298 KB]