Graphen in der Schule mit Python und Jupyter-Notebooks

Abstract

Graphen spielen eine große Rolle in vielen Alltagssituationen sowie in der wissenschaftlichen Informatik. Sie sind Teil der Informatik-Lehrpläne (mindestens der Leistungskurse) der gymnasialen Oberstufe. Beispielsweise findet man das Thema im schulinternen Lehrplan von NRW[1]: 1. Analyse von Graphen in verschiedenen Kontexten (a) Grundlegende Begriffe (Graph, gerichtet – ungerichtet, Knoten, Kanten, Kantengewicht) (b) Aufbau und Darstellung von Graphen anhand von Graphenstrukturen in verschiedenen Kontexten (Adjazenzmatrix, Adjazenzliste) 2. Die Datenstruktur Graph im Anwendungskontext unter Nutzung der Klassen Graph, Vertex und Edge. (a) Erarbeitung der Klassen Graph, Vertex und Edge und beispielhafte Anwendung der Operationen (b) Bestimmung von Wegen in Graphen im Anwendungskontext (Tiefensuche, Breitensuche) (c) Bestimmung von kürzesten Wegen in Graphen im Anwendungskontext (Backtracking, Dijkstra). (d) Bestimmung von minimalen Spannbäumen eines Graphen im Anwendungskontext. Die im Folgenden aufgeführten Teile dieses Artikels sind entstanden, um Graphen im Unterricht für die Schülerinnen und Schüler erfahrbar zu machen, zum Beispiel unter Nutzung von Python und Jupyter-Notebooks. Dazu wurden entwickelt: • zwei Python-Bibliotheken, mit denen die Verwaltung von ungerichteten Graphen einfach gelingt. • eine für die Schülerinnen und Schüler geeignete sehr kurze Einführung in die Begriffswelt von Graphen. • ein Jupyter-Notebook, das den Schülerinnen und Schülern als Arbeitsmaterial vorgelegt wird.

Keywords

• Python
• Graphen
• Jupyter-Notebook