Graphenalgorithmen: Einführung

Aktives Lernen eignet sich besonders gut für Graphenalgorithmen, weil Schüler durch physische und visuelle Modellierungen abstrakte Konzepte wie Knoten, Kanten und Traversierungen greifbar machen. Die Kombination aus Gruppenarbeit, Simulationen und Programmierung fördert das Verständnis für die Struktur und Funktion von Graphen, die für viele technische und alltagsnahe Probleme grundlegend sind.

• Klasse 11
• Informatik in der Oberstufe: Algorithmen, Daten und Gesellschaft
• 4 Aktivitäten
• 30 Min.–50 Min.

Lernziele

1. Modellieren Sie reale Probleme, wie z.B. soziale Netzwerke oder Routenplanung, mithilfe von Graphen (Knoten und Kanten).
2. Vergleichen Sie die Funktionsweise und Anwendungsbereiche der Breitensuche (BFS) und Tiefensuche (DFS) zur Traversierung von Graphen.
3. Analysieren Sie die Effizienz von BFS und DFS für verschiedene Aufgabenstellungen, z.B. das Finden des kürzesten Weges in einem ungewichteten Graphen.
4. Demonstrieren Sie die Darstellung von Graphen mittels Adjazenzlisten und Adjazenzmatrizen in Pseudocode.
5. Erklären Sie die Bedeutung von Graphen für die Struktur und Analyse von sozialen Netzwerken und Navigationssystemen.

Concept-Mapping

⏱ 45 Min.·Kleingruppen

Gruppenmodellierung: Städtenetzwerk bauen

Schüler erhalten Kartenkarten als Knoten und Fäden als Kanten, um ein Städtenetzwerk zu modellieren. Sie markieren Startknoten und traversieren mit BFS und DFS, notieren besuchte Knoten. Abschließend diskutieren sie Anwendungen in Navigationssystemen.

Vorbereitung & Details

Wie lassen sich reale Probleme mithilfe von Graphen modellieren?

Moderationstipp: Während der Gruppenmodellierung des Städtenetzwerks fragen Sie gezielt nach zyklischen Strukturen und lassen Sie Schüler diese markieren, um ungerichtete von gerichteten Graphen zu unterscheiden.

Setup: Tische für große Papierformate oder Wandflächen

Materials: Begriffskarten oder Haftnotizen, Plakatpapier, Marker, Beispiel für eine Concept Map

• Verstehen
• Analysieren
• Erschaffen
• Selbstwahrnehmung
• Selbststeuerung

Planspiel

⏱ 30 Min.·Partnerarbeit

Planspiel: Murmel-Traversierung

Verwenden Sie einen Graphen aus Pappkarton mit Löchern als Knoten. Murmeln rollen für BFS (alle Nachbarn zuerst) oder DFS (tief zuerst). Gruppen protokollieren Pfade und vergleichen Ergebnisse.

Vorbereitung & Details

Vergleichen Sie Breitensuche (BFS) und Tiefensuche (DFS) bei der Traversierung von Graphen.

Moderationstipp: Beobachten Sie bei der Murmel-Traversierung, ob Schüler die schichtweise Ausbreitung von BFS und die Pfadvertiefung von DFS aktiv nachvollziehen oder nur mechanisch wiederholen.

Setup: Flexibler Raum für verschiedene Gruppenstationen

Materials: Rollenkarten mit Zielen und Ressourcen, Spielwährung oder Token, Rundenprotokoll

• Anwenden
• Analysieren
• Bewerten
• Erschaffen
• Sozialbewusstsein
• Entscheidungsfähigkeit

Concept-Mapping

⏱ 50 Min.·Partnerarbeit

Programmierpraxis: Einfache Traversierung

Schüler implementieren BFS und DFS in Python mit einer Adjazenzliste. Testen Sie mit einem sozialen Netzwerk-Beispiel. Paare debuggen gegenseitig und visualisieren Pfade mit Matplotlib.

Vorbereitung & Details

Analysieren Sie die Bedeutung von Graphen in sozialen Netzwerken und Navigationssystemen.

Moderationstipp: Bei der Programmierpraxis achten Sie darauf, dass Schüler nicht nur Code schreiben, sondern ihre Implementierung mit Beispielgraphen aus der Simulation vergleichen und anpassen.

Setup: Tische für große Papierformate oder Wandflächen

Materials: Begriffskarten oder Haftnotizen, Plakatpapier, Marker, Beispiel für eine Concept Map

• Verstehen
• Analysieren
• Erschaffen
• Selbstwahrnehmung
• Selbststeuerung

Fishbowl-Diskussion

⏱ 35 Min.·Ganze Klasse

Fishbowl-Diskussion: Reale Modelle analysieren

Präsentieren Sie Graphen aus Facebook oder Google Maps. Whole class diskutiert Modellierung, traversiert manuell und bewertet BFS/DFS-Eignung.

Vorbereitung & Details

Wie lassen sich reale Probleme mithilfe von Graphen modellieren?

Setup: Innenkreis mit 4–6 Stühlen, umgeben von einem Außenkreis

Materials: Diskussionsimpuls oder Leitfrage, Beobachtungsbogen

• Analysieren
• Bewerten
• Sozialbewusstsein
• Selbstwahrnehmung

Dieses Thema unterrichten

Erfahrene Lehrkräfte beginnen mit einer klaren Struktur: Zuerst werden Graphen als Modellierungsproblem eingeführt, bevor Algorithmen als Lösungsstrategien dienen. Vermeiden Sie es, beide Algorithmen gleichzeitig zu erklären, da dies die Unterschiede verwischt. Nutzen Sie Schülerfragen als Anker für Vertiefungen, etwa wenn jemand fragt, warum BFS in sozialen Netzwerken schneller Informationen verbreitet. Die Forschung zeigt, dass Lernende durch wiederholtes Anwenden und Erklären der Algorithmen ein tieferes Verständnis entwickeln, als durch reine Theorievermittlung.

Was Sie erwartet

Am Ende der Einheit können Schüler Graphen als Adjazenzlisten oder -matrizen darstellen, die Unterschiede zwischen BFS und DFS erklären und beide Algorithmen manuell sowie in einfachen Programmen anwenden. Sie erkennen, wann welcher Algorithmus sinnvoll ist und identifizieren typische Fehlerquellen in der Modellierung oder Implementierung.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Während der Gruppenmodellierung des Städtenetzwerks hören Sie Schüler sagen: 'Graphen haben doch immer Pfeile und keine Kreise.'

Was Sie stattdessen lehren sollten

Fordern Sie die Gruppe auf, einen einfachen Kreis aus vier Städten zu zeichnen und zu markieren, ob die Verbindungen ungerichtet (z.B. Straßen) oder gerichtet (z.B. Einbahnstraßen) sind. Diskutieren Sie gemeinsam, warum Zyklen in realen Modellen häufig vorkommen.

Häufige Fehlvorstellung

Während der Murmel-Simulation zur Traversierung beobachten Sie, dass Schüler annehmen: 'BFS und DFS geben immer dieselbe Reihenfolge aus.'

Was Sie stattdessen lehren sollten

Bitten Sie die Schüler, die Murmel-Simulation mit demselben Graphen, aber unterschiedlichen Startknoten zu wiederholen und die Ergebnisse zu vergleichen. Fragen Sie nach: 'Was ändert sich, wenn wir bei einem anderen Knoten beginnen?'

Häufige Fehlvorstellung

Während der Programmierpraxis zur Adjazenzmatrix hören Sie Schüler sagen: 'Matrizen sind immer schneller als Listen.'

Was Sie stattdessen lehren sollten

Geben Sie den Schülern einen Graphen vor, bei dem die Matrix fast leer ist (z.B. nur 3 von 100 Knoten verbunden), und lassen Sie sie die Speicherauslastung beider Darstellungen berechnen und vergleichen.

Ideen zur Lernstandserhebung

Lernstandskontrolle

Nach der Gruppenmodellierung des Städtenetzwerks geben Sie jedem Schüler einen Graphen mit 5 Knoten und 6 Kanten. Sie erstellen eine Adjazenzliste und führen eine manuelle Tiefensuche ab Knoten A durch. Sammeln Sie die Ergebnisse und prüfen Sie, ob Schüler Zyklen erkannt und die Traversierungsreihenfolge korrekt notiert haben.

Diskussionsfrage

Nach der Murmel-Simulation zur Traversierung stellen Sie die Frage: 'Warum könnte BFS in einem sozialen Netzwerk effizienter sein als DFS, um eine Nachricht an alle Freunde zu verbreiten?' Lassen Sie Schüler ihre Antworten in Kleingruppen diskutieren und mit den Ergebnissen der Simulation vergleichen.

Kurze Überprüfung

Während der Programmierpraxis zeigen Sie eine einfache Adjazenzmatrix und fragen: 'Welche Knoten sind direkt verbunden?' Wiederholen Sie dies für eine Adjazenzliste. Bitten Sie Schüler, die Antworten auf einem Whiteboard zu notieren und kurz zu erläutern, wie sie die Verbindungen abgelesen haben.

Erweiterungen & Unterstützung

• Fordern Sie Schüler auf, einen Graphen mit mindestens einem Zyklus zu konstruieren und beide Algorithmen anzuwenden, um zu zeigen, wie Zyklen die Traversierung beeinflussen.
• Bei Unsicherheiten in der Modellierung geben Sie Schülern ein konkretes Beispiel (z.B. ein U-Bahn-Netz) und lassen Sie sie die Adjazenzliste schrittweise vervollständigen.
• Vertiefen Sie die Effizienzanalyse, indem Sie Schüler große Graphen (z.B. mit 20 Knoten) in Adjazenzmatrizen und -listen darstellen und Speicherbedarf sowie Zugriffszeiten vergleichen.

Schlüsselvokabular

Graph	Eine Datenstruktur, die aus einer Menge von Knoten (Eckpunkten) und einer Menge von Kanten besteht, die Paare von Knoten verbinden.
Knoten (Vertex)	Ein Element in einem Graphen, das oft als Punkt oder Kreis dargestellt wird. Repräsentiert Objekte oder Entitäten.
Kante (Edge)	Eine Verbindung zwischen zwei Knoten in einem Graphen, oft als Linie dargestellt. Repräsentiert Beziehungen oder Verbindungen.
Breitensuche (BFS)	Ein Algorithmus zur Traversierung von Graphen, der schichtweise alle erreichbaren Knoten von einem Startknoten aus erkundet.
Tiefensuche (DFS)	Ein Algorithmus zur Traversierung von Graphen, der versucht, so tief wie möglich entlang jedes Zweiges zu gehen, bevor er zurückkehrt.
Adjazenzliste	Eine Methode zur Darstellung eines Graphen, bei der für jeden Knoten eine Liste der benachbarten Knoten gespeichert wird.