Graphen: Darstellung und Grundlagen

Aktives Handeln verankert abstrakte Konzepte wie Graphen in realen Szenarien und macht Beziehungen zwischen Knoten und Kanten greifbar. Durch das Bauen, Vergleichen und Programmieren von Graphen entwickeln Schülerinnen und Schüler ein intuitives Verständnis für die Grundlagen, das über theoretische Erklärungen hinausgeht.

• Klasse 13
• Informatik Oberstufe: Komplexe Systeme und Theoretische Grundlagen
• 4 Aktivitäten
• 30 Min.–60 Min.

Lernziele

1. Klassifizieren Sie gegebene Netzwerke anhand ihrer Eigenschaften (ungerichtet, gerichtet, einfach, gewichtet).
2. Vergleichen Sie die Speicherplatz- und Zeitkomplexität von Adjazenzmatrizen und Adjazenzlisten für verschiedene Graphentypen.
3. Analysieren Sie die Struktur eines gegebenen sozialen Netzwerks und modellieren Sie es als Graphen.
4. Erklären Sie die Konzepte von Knoten, Kanten und ihre Bedeutung für die Darstellung von Beziehungen.
5. Demonstrieren Sie die Anwendung von Graphenmodellen zur Lösung eines einfachen Problems, z. B. Routenplanung.

Concept-Mapping

⏱ 45 Min.·Kleingruppen

Graphenbau: Freundschaftsnetzwerke

Schüler zeichnen ein Klassennetzwerk mit Knoten für Mitschüler und Kanten für Freundschaften. Sie klassifizieren als ungerichtet oder gerichtet und notieren Eigenschaften. In der Reflexion diskutieren sie Vor- und Nachteile der Visualisierung.

Vorbereitung & Details

Erklären Sie die Konzepte von Knoten, Kanten und Graphentypen.

Moderationstipp: Fordern Sie während 'Graphenbau: Freundschaftsnetzwerke' gezielt auf, Knoten und Kanten mit konkreten Beispielen zu benennen, um den abstrakten Charakter zu betonen.

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

Concept-Mapping

⏱ 30 Min.·Partnerarbeit

Vergleich: Matrix vs. Liste

Paare erstellen für einen Graphen eine Adjazenzmatrix und eine Adjazenzliste. Sie messen Speicherbedarf und simulieren Nachbarschaftsabfragen. Abschließend vergleichen sie Zeit- und Platzkomplexität in einer Tabelle.

Vorbereitung & Details

Vergleichen Sie Adjazenzmatrizen und Adjazenzlisten zur Graphendarstellung.

Moderationstipp: Nutzen Sie bei 'Vergleich: Matrix vs. Liste' eine Whiteboard-Diskussion, um gemeinsam die Vor- und Nachteile beider Darstellungsformen zu sammeln und sichtbar zu machen.

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

Concept-Mapping

⏱ 60 Min.·Kleingruppen

Programmier-Challenge: Graphen modellieren

Gruppen implementieren einen einfachen Graphen in Python mit Listen oder Dictionaries. Sie laden reale Daten, z. B. aus einem Social-Media-Beispiel, und testen Traversierungen. Gemeinsam debuggen sie und präsentieren Ergebnisse.

Vorbereitung & Details

Analysieren Sie, wie reale Netzwerke wie soziale Medien als Graphen modelliert werden können.

Moderationstipp: Lassen Sie in 'Programmier-Challenge: Graphen modellieren' die Schülerinnen und Schüler ihre Lösungen in Kleingruppen präsentieren, um Lernfortschritte durch Peer-Feedback zu verstärken.

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

Concept-Mapping

⏱ 50 Min.·Ganze Klasse

Netzwerk-Analyse: reale Daten

Die Klasse analysiert ein öffentliches Dataset wie Flugverbindungen als Graph. Individuen berechnen Gradzahlen, teilen in Plenum und diskutieren Implikationen für Algorithmen.

Vorbereitung & Details

Erklären Sie die Konzepte von Knoten, Kanten und Graphentypen.

Moderationstipp: Bei 'Netzwerk-Analyse: reale Daten' achten Sie darauf, dass die Datenauswahl die Vielfalt der Graphentypen widerspiegelt, um unterschiedliche Anwendungsfälle zu erkunden.

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

Dieses Thema unterrichten

Erfahrene Lehrkräfte beginnen mit anschaulichen Beispielen aus dem Alltag, um Graphen als Modelle für Netzwerke zu etablieren. Sie vermeiden es, sich in theoretischen Definitionen zu verlieren, und setzen stattdessen auf handlungsorientierte Aufgaben, die das abstrakte Denken fördern. Wichtig ist, dass Visualisierungen als Hilfsmittel genutzt werden, ohne dass sie die einzige Darstellungsform bleiben. Durch gezielte Fragen und Gegenüberstellungen von Darstellungsformen wird das Verständnis für die Struktur von Graphen geschärft.

Was Sie erwartet

Erfolgreich gelernt haben die Schülerinnen und Schüler, wenn sie Graphen als Modelle für Netzwerke erkennen und selbstständig zwischen ungerichteten und gerichteten Graphen, Listen und Matrizen unterscheiden können. Sie sollen zudem einfache Algorithmen anwenden und die Eignung der Darstellungsformen begründen.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Während 'Graphenbau: Freundschaftsnetzwerke' wird beobachtet, dass einige Schülerinnen und Schüler Graphen als bloße Zeichnungen missverstehen.

Was Sie stattdessen lehren sollten

Lenken Sie die Aufmerksamkeit auf die abstrakte Natur der Graphen, indem Sie die Schülerinnen und Schüler auffordern, ihre Netzwerke zunächst als Listen von Knoten und Kanten zu beschreiben, bevor sie diese visualisieren.

Häufige Fehlvorstellung

Während 'Vergleich: Matrix vs. Liste' wird bemerkt, dass Schülerinnen und Schüler Matrizen generell als effizienter einstufen.

Was Sie stattdessen lehren sollten

Lassen Sie die Schülerinnen und Schüler mit vorgegebenen Graphen experimentieren und die Speicherplatzausnutzung beider Darstellungsformen vergleichen, um das Verständnis für die Abhängigkeit von der Graphendichte zu fördern.

Häufige Fehlvorstellung

Während 'Programmier-Challenge: Graphen modellieren' wird festgestellt, dass Schülerinnen und Schüler unbewusst von bidirektionalen Kanten ausgehen.

Was Sie stattdessen lehren sollten

Fordern Sie die Schülerinnen und Schüler auf, ihre Graphenmodelle mit gerichteten Kanten zu testen, indem sie reale Szenarien wie Web-Links oder Einbahnstraßen verwenden.

Ideen zur Lernstandserhebung

Lernstandskontrolle

Nach 'Graphenbau: Freundschaftsnetzwerke' bitten Sie die Schülerinnen und Schüler, für ein vorgegebenes Netzwerk (z. B. ein U-Bahn-Netz) zu entscheiden, ob ein gerichteter oder ungerichteter Graph geeignet ist, und dies kurz zu begründen.

Kurze Überprüfung

Während 'Vergleich: Matrix vs. Liste' zeigen Sie eine kleine Adjazenzmatrix und eine Adjazenzliste zu einem einfachen Graphen. Fragen Sie: 'Welche Kante ist in der Liste nicht enthalten?' oder 'Welche Knoten sind mit Knoten 3 verbunden, basierend auf der Matrix?'

Diskussionsfrage

Nach 'Netzwerk-Analyse: reale Daten' stellen Sie die Frage: 'Wie würden Sie ein Musik-Empfehlungssystem als Graphen modellieren? Welche Knoten und Kanten wären nötig, und warum wäre ein gewichteter Graph sinnvoll?'

Erweiterungen & Unterstützung

• Fordern Sie leistungsstarke Schülerinnen und Schüler auf, für das Freundschaftsnetzwerk aus Activity 1 einen einfachen Algorithmus zur Berechnung der durchschnittlichen Anzahl von Freunden zu implementieren.
• Unterstützen Sie Lernende bei 'Netzwerk-Analyse', indem Sie ihnen vorgefertigte Tabellen mit Daten zur Verfügung stellen, die sie schrittweise in Graphen umwandeln können.
• Vertiefen Sie das Thema mit einer Recherche zu Graphenalgorithmen wie Dijkstras oder BFS und deren Anwendung auf reale Netzwerke wie soziale Medien oder Verkehrsnetze.

Schlüsselvokabular

Knoten (Vertex)	Ein Punkt in einem Graphen, der ein Objekt oder eine Entität repräsentiert, z. B. eine Person in einem sozialen Netzwerk oder eine Stadt auf einer Landkarte.
Kante (Edge)	Eine Verbindung zwischen zwei Knoten, die eine Beziehung oder Interaktion darstellt, z. B. eine Freundschaft zwischen zwei Personen oder eine Straße zwischen zwei Städten.
Adjazenzmatrix	Eine quadratische Matrix, die angibt, ob Paare von Knoten in einem Graphen verbunden sind. Sie eignet sich gut für dichte Graphen.
Adjazenzliste	Eine Sammlung von Listen, wobei jede Liste die Nachbarknoten eines bestimmten Knotens enthält. Sie ist speichereffizient für spärliche Graphen.
Gerichteter Graph	Ein Graph, bei dem die Kanten eine Richtung haben, was eine einseitige Beziehung zwischen Knoten anzeigt, z. B. das Folgen auf Twitter.