Graphentheorie
🟪 Fachbegriffe zum Leben erwecken
☰
Aufgabe 1
Gegeben ist das folgende Uni-Skript zu Grundbegriffen der Graphentheorie: Grundbegriffe der Graphentheorie – Uni Greifswald
👤 a) Analysiere das Skript und notiere, aus welchen Elementen es besteht.
👤 b) Erstelle einen One-Pager mit allen fettgedruckten Begriffen aus dem Skript aus den Abschnitten 6.1, 6.2 (bis „Komponenten“) und 6.3 (bis „Länge eines Weges“). Zeichne zu jedem Begriff einen Graphen, der den Begriff veranschaulicht.
💁 Tipp: Recherchiee im Internet zu „Onepager Chris Hadfield“, um inspirierende Beispiele für Onepager zu finden.
Aufgabe 2
Im Informatikunterricht bedeutet „Modellierung“ im wesentlichen die Abgrenzung eines für den jeweiligen Zweck relevanten Ausschnittes der Erfahrungswelt, die Herausarbeitung seiner wichtigen Merkmale unter Vernachlässigung der unwichtigen sowie seiner Beschreibung und Strukturierung mithilfe spezieller Techniken aus der Informatik.1
Gegeben sind fünf Graphen auf inf-schule.
👤 a) Ordne möglichst viele Fachbegriffe den Graphen zu und finde für jeden Graphen ein Anwendungsbeispiel, also einen Sachzusammenhang, den der Graph modelliert.
💁 Tipp: Inspiration für Anwendungsbeispiele
👤 b) Finde im folgenden Kreuzworträtsel alle Fachbegriffe zur Graphentheorie.
🟦 Speicherung von Graphen
☰
Aufgabe 1
👤 a) Lade die passwortgeschützte HTML-Datei herunter und erkunde sie a) mit einem Browser und b) mit einem Texteditor. Finde heraus, wie der Graph gespeichert ist.
💁 Tipp: Um den Graphen digital zu erstellen, nutze den PlantUML-Editor, am besten mit Werbeblockern! Unten siehst du ein Beispielprogramm, um mit PlantUML Graphen zu erstellen.
@startuml
(1) -down-> (2)
(2) -> (5)
(5) -> (98)
(2) -> (1)
(98) -left-> (1)
@enduml👥 b) Denke dir einen Graphen aus und stelle ihn in der HTML-Datei dar. Tauscht anschließend eure Dateien aus und ermittelt, wie der Graph der anderen Person aussieht.
Aufgabe 2
👤 a) Recherchiere zu Adjazenzlisten und überführe die Adjazenzmatrix aus der HTML-Datei in eine Adjazenzliste.
👥 b) Überlegt, wann sich eine Adjanzenzliste und wann eine Adjazenzmatrix für die Speicherung von Graphen eher eignet.
Material
- Probleme lösen mit Graph Biber, Aufgabensammlung von 15 Informatik-Biber-Aufgaben
- Einführungsskript der Hochschule Konstanz
- Graph-Beispiele und interaktives Tool zum Ausführen von Graphenalgorithmen
Fußnoten
-
Gesellschaft für Informatik (GI) e.V. 2000: Empfehlungen für ein Gesamtkonzept zur Informatischen Bildung an allgemein bildenden Schulen, Bonn ↩