Informatik · Klasse 13 · Datenstrukturen und Algorithmen-Analyse · 1. Halbjahr

Graphen: Darstellung und Grundlagen

Die Schülerinnen und Schüler lernen verschiedene Darstellungsformen von Graphen und deren grundlegende Eigenschaften kennen.

• KMK Bildungsstandards
• KMK: Sekundarstufe II - Daten und ihre Strukturierung
• KMK: Sekundarstufe II - Strukturieren und Vernetzen

Über dieses Thema

Graphen dienen als mathematische Modelle für Netzwerke und bestehen aus Knoten, die Objekte darstellen, und Kanten, die Beziehungen zwischen ihnen zeigen. In der Oberstufe lernen Schülerinnen und Schüler grundlegende Eigenschaften kennen: ungerichtete Graphen mit symmetrischen Kanten, gerichtete mit Pfeilen, einfache ohne Schleifen oder Mehrfachkanten sowie gewichtete Varianten. Diese Konzepte knüpfen an vertraute Strukturen wie Straßennetze oder Freundschaften an und bilden die Basis für Algorithmen in der Informatik.

Zwei gängige Darstellungsformen sind Adjazenzmatrizen, die Verbindungen in einer booleschen oder gewichteten Tabelle speichern, und Adjazenzlisten, die für jeden Knoten eine Liste seiner Nachbarn führen. Schüler vergleichen die Effizienz: Matrizen eignen sich für dichte Graphen mit schneller Zugriffszeit O(1), Listen sparen bei sparsamen Graphen Speicherplatz. Reale Anwendungen wie soziale Medien, in denen Nutzer Knoten und Follower-Beziehungen Kanten sind, machen die Relevanz klar und fördern systemisches Denken gemäß KMK-Standards.

Aktives Lernen passt hervorragend zu Graphen, weil Schüler Modelle selbst bauen, manipulieren und mit Programmiertools testen können. So entstehen tiefe Verständnisse durch Experimentieren und Diskussionen, die abstrakte Ideen konkret und nachhaltig machen.

Leitfragen

1. Erklären Sie die Konzepte von Knoten, Kanten und Graphentypen.
2. Vergleichen Sie Adjazenzmatrizen und Adjazenzlisten zur Graphendarstellung.
3. Analysieren Sie, wie reale Netzwerke wie soziale Medien als Graphen modelliert werden können.

Lernziele

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

Bevor es losgeht

Grundlegende Datenstrukturen (Arrays, Listen)

Warum: Schüler müssen mit sequenziellen und verketteten Datenstrukturen vertraut sein, um die Implementierung von Adjazenzlisten zu verstehen.

Grundlagen der Algorithmik (Zeitkomplexität)

Warum: Das Verständnis von Big O Notation ist notwendig, um die Effizienz von Graphendarstellungen zu vergleichen.

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.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Graphen sind immer visuelle Bilder.

Was Sie stattdessen lehren sollten

Graphen sind abstrakte Datenstrukturen, unabhängig von der Darstellung. Aktive Ansätze wie das Programmieren eigener Graphenklassen helfen Schülern, den Fokus auf Knoten und Kanten zu legen, statt auf Zeichnungen. Diskussionen klären, dass Visualisierungen nur Hilfsmittel sind.

Häufige Fehlvorstellung

Adjazenzmatrizen sind immer effizienter als Listen.

Was Sie stattdessen lehren sollten

Effizienz hängt von der Graphendichte ab: Matrizen bei dichten, Listen bei sparsamen Graphen. Experimente mit wachsenden Knotenanzahlen zeigen den Speicherverbrauch und machen den Vergleich greifbar. Peer-Teaching verstärkt das Verständnis.

Häufige Fehlvorstellung

Alle Kanten in Graphen sind bidirektional.

Was Sie stattdessen lehren sollten

Gerichtete Graphen haben asymmetrische Kanten. Schüler modellieren reale Szenarien wie Web-Links und testen mit Algorithmen, was die Richtung verdeutlicht. Gruppendiskussionen korrigieren intuitive Annahmen.

Ideen für aktives Lernen

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.

45 Min.·Kleingruppen

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.

30 Min.·Partnerarbeit

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.

60 Min.·Kleingruppen

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.

50 Min.·Ganze Klasse

Bezüge zur Lebenswelt

• Google Maps verwendet Graphenalgorithmen, um die schnellste oder kürzeste Route zwischen zwei Orten zu berechnen, wobei Straßen als Kanten und Kreuzungen als Knoten modelliert werden.
• Soziale Netzwerke wie Facebook oder LinkedIn stellen Nutzer als Knoten und Verbindungen (Freundschaften, Follower) als Kanten dar, um Empfehlungen und Verbindungen zu ermöglichen.
• Die Deutsche Bahn nutzt Graphenmodelle zur Optimierung von Fahrplänen und zur Verwaltung des Schienennetzes, um Verspätungen zu minimieren und die Auslastung zu maximieren.

Ideen zur Lernstandserhebung

Lernstandskontrolle

Geben Sie den Schülern eine Liste mit drei verschiedenen Netzwerkbeschreibungen (z. B. ein U-Bahn-Netz, eine Liste von E-Mails zwischen Kollegen, eine Liste von Webseiten mit Links). Bitten Sie sie, für jede Beschreibung zu entscheiden, ob ein gerichteter oder ungerichteter Graph am besten geeignet ist und warum.

Kurze Überprüfung

Zeigen Sie eine kleine Adjazenzmatrix und eine entsprechende Adjazenzliste für einen einfachen Graphen. Stellen Sie folgende Fragen: 'Welche Kante fehlt in der Adjazenzliste?' oder 'Welche Knoten sind mit Knoten 3 verbunden, basierend auf der Adjazenzmatrix?'

Diskussionsfrage

Stellen Sie die Frage: 'Stellen Sie sich vor, Sie entwerfen ein System zur Empfehlung von Musik. Wie würden Sie dieses Problem als Graphenproblem modellieren? Welche wären die Knoten und welche die Kanten? Welche Art von Graph wäre am besten geeignet und warum?'

Häufig gestellte Fragen

Was sind Knoten und Kanten in Graphen?

Knoten repräsentieren Objekte wie Personen oder Städte, Kanten die Verbindungen dazwischen, z. B. Freundschaften oder Straßen. In ungerichteten Graphen sind Kanten symmetrisch, in gerichteten folgen sie einer Richtung. Diese Elemente ermöglichen die Modellierung komplexer Netzwerke und sind zentral für Algorithmen wie Dijkstra. Schüler üben am besten mit eigenen Beispielen aus dem Alltag.

Unterschied zwischen Adjazenzmatrix und Adjazenzliste?

Eine Adjazenzmatrix speichert Verbindungen in einer n x n Tabelle mit 1 für Kanten oder Gewichten, ideal für schnelle Abfragen O(1), aber speicherintensiv bei n Knoten. Adjazenzlisten listen pro Knoten Nachbarn auf, sparsam bei wenigen Kanten, Abfrage O(Grad). Der Vergleich zeigt Trade-offs für reale Anwendungen wie Social Graphs.

Wie modelliert man soziale Medien als Graphen?

Nutzer sind Knoten, Follower-Beziehungen gerichtete Kanten, Likes oder gemeinsame Freunde ungerichtete. Plattformen wie Twitter lassen sich so analysieren: Zentralität misst Influencer, Communities via Cluster. Solche Modelle verbinden Theorie mit Praxis und bereiten auf Big-Data-Algorithmen vor.

Wie fördert aktives Lernen das Verständnis von Graphen?

Aktives Lernen macht Graphen durch Hands-on-Aktivitäten greifbar: Schüler bauen Modelle mit Karten, programmieren Strukturen oder analysieren reale Datasets. Gruppendiskussionen und Experimente wie Effizienzvergleiche korrigieren Missverständnisse und bauen Intuition auf. Diese Methoden steigern Retention und verbinden Abstraktes mit Anwendungen, passend zu KMK-Zielen.