⏧ Graphentheorie - fiebig.schule

☰

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.¹

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.

☰

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.

Beispielgraph auf PlantUML

@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) Unten siehst du Teile einer Adjazenzliste und einer Adjazenzmatrix. Vervollständige beide, damit jeweils beide den obigen Graphen vollständig abbilden.

AdjazenzlisteCode für PlantUMLAdjazenzmatrix

Code für Adjanzenzliste auf PlantUML

@startuml
skinparam linetype ortho
skinparam rectangle {
  RoundCorner 10
}
 
' ===== Hauptliste =====
rectangle "Bielefeld Hbf" as H1
rectangle "Herford Hbf" as H2
rectangle "Gütersloh Hbf" as H3
rectangle "..." as H4
H1 --> H2
H2 --> H3
H3 --> H4
 
' ===== Unterliste von L1 =====
rectangle "Herford Hbf | 10" as L1A
rectangle "..." as L1B
H1 -right-> L1A
L1A -right-> L1B
 
' ===== Unterliste von L2 =====
rectangle "Bielefeld Hbf | 10" as L2A
rectangle "..." as L2B
rectangle "..." as L2C
H2 -right-> L2A
L2A -right-> L2B
L2B -right-> L2C
 
' ===== Unterliste von L3 =====
rectangle "..." as L3A
H3 -right-> L3A
@enduml

\begin{array}{c|cccc} & \mathbf{Bielefeld\ Hbf} & \mathbf{Herford\ Hbf} & \mathbf{Gütersloh\ Hbf} & \mathbf{...} \\ \hline \mathbf{Bielefeld\ Hbf} & 0 & 5 & 10 \\ \mathbf{Herford\ Hbf} & 5 & 0 & 7 \\ \mathbf{Gütersloh\ Hbf} & 10 & 7 & 0 \\ \mathbf{...} & ... & ... & ... \\ \end{array}

👥 b) Überlegt, wann sich eine Adjanzenzliste und wann eine Adjazenzmatrix für die Speicherung von Graphen eher eignet. Recherchiere zu den Fachbegriffen dünne und dichte Graphen.

Merke 📝

dünne Graphen -> dünnbesetzte/schwachbesetzte Matrix (engl. sparse) -> besser: Adjanzenzliste
dichte Graphen -> vollbesetzte Matrix (engl. dense)

☰

Vorlagen der Struktogramme für Breiten- und Tiefensuche

🔒

Verwende die NRW-Abiturklassen Graph, Vertex, Edgeund List.

Links

Animationen

☰

👤 a) Erkunde mit Hilfe der folgenden Abfolge von Graphen, wie der Dijkstra-Algorithmus den kürzesten Weg ermittelt: inf-schule: Dijsktra-Algorithmus an einem Beispiel

👤 b) Führe den Dijkstra-Algorithmus auf dem unten abgebildeten Graphen mit Startknoten a aus. Ergänze dazu die interaktive Tabelle. Notabene: Bei gleich hohen Kosten wird (in diesem Fall) als nächster aktueller Knoten derjenige Knoten gewählt, der weiter vorn im Alphabet steht.

💁 Tipp: Auf dieser Seite der TU München ist der Graph als „Standardgraph“ hinterlegt und du kannst schrittweise den Dijsktra-Algorithmus durchspielen.

Akt. Knoten	$a$	$b$	$c$	$d$	$e$	$f$	Liste nach Bearb. des akt. Knotens (unsortiert)
	$\underline{0, – }$	$\infty, –$	$\infty, –$	$\infty, –$	$\infty, –$	$\infty, –$	$a$
a		$\underline{10, \ a}$	{t{20, a}}	$\infty, –$	$\infty, –$	$\infty, –$	b, c
{t{b}}			$\underline{20, \ a}$	{t{60, b}}	{t{20, b}}	$\infty, –$	{t{c, d, e}}
c				{t{40, c}}	{t{20, b}}	$\infty, –$	{t{d, e}}
e				{t{40, c}}		{t{21, e}}	{t{d, f}}
{t{f}}				{t{40, c}}			{t{d}}
d							–

👤 c) Überführe das unten bereitgestellte Struktogramm des Dijkstra-Algorithmus in Java-Code.

🔒

👤 d) Teste deinen Algorithmus mit Hilfe des obigen Standardgraphen. Die Implementierung des Graphen findest du unten.

    Graph myGraph = new Graph();
    String[] vertexNames = {"a", "b", "c", "d", "e", "f"};
    for (String s : vertexNames) {
        myGraph.addVertex(new Vertex(s));
    }
    myGraph.addEdge(new Edge(myGraph.getVertex("a"), myGraph.getVertex("b"), 10));
    myGraph.addEdge(new Edge(myGraph.getVertex("a"), myGraph.getVertex("c"), 20));
    myGraph.addEdge(new Edge(myGraph.getVertex("b"), myGraph.getVertex("d"), 50));
    myGraph.addEdge(new Edge(myGraph.getVertex("b"), myGraph.getVertex("e"), 10));
    myGraph.addEdge(new Edge(myGraph.getVertex("c"), myGraph.getVertex("d"), 20));
    myGraph.addEdge(new Edge(myGraph.getVertex("c"), myGraph.getVertex("e"), 33));
    myGraph.addEdge(new Edge(myGraph.getVertex("d"), myGraph.getVertex("e"), 20));
    myGraph.addEdge(new Edge(myGraph.getVertex("d"), myGraph.getVertex("f"), 2));
    myGraph.addEdge(new Edge(myGraph.getVertex("e"), myGraph.getVertex("f"), 1));

Beachte, dass die Abiturklasse Graph ungerichtete Graphen modelliert. Der obigen Algorithmus erstellt also folgenden Graphen:

Ungerichtete Graphen lassen sich auch als gerichtete Graphen mit Kanten in beide Richtungen interpretieren:

☰

👤 Bearbeite die folgenden Aufgaben zu Graphen im Sachzusammenhang.

🔒

☰

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
Comics: xkcd: Depth and Breadth, xkcd: DFS, xkcd: Königsberg

Graphentheorie

001 🟪 Fachbegriffe zum Leben erwecken

Aufgabe 1

Aufgabe 2

010 🟦 Speicherung von Graphen

Aufgabe 1

Aufgabe 2

Merke 📝

011 🟩 Graphentraversierungen

Vorlagen der Struktogramme für Breiten- und Tiefensuche

Links

100 🟨 Dijkstra-Algorithmus

101 🟧 Aufgaben im Sachzusammenhang

110 🟥 Programmierprojekt

Material

Fußnoten