Differences
This shows you the differences between two versions of the page.
Next revision | Previous revision | ||
efinf:blc2016:graphen:graphen [2017/01/24 09:01] Ivo Blöchliger created |
efinf:blc2016:graphen:graphen [2017/04/04 15:30] (current) Ivo Blöchliger [Labyrinth-Generator] |
||
---|---|---|---|
Line 1: | Line 1: | ||
+ | ===== Labyrinth-Generator ===== | ||
+ | * Vorlage {{ : | ||
+ | * Anderer Generator {{ : | ||
+ | |||
+ | ===== Lernziele / Prüfungsstoff ===== | ||
+ | * Begriffe und Definitionen kennen und anwenden, wie | ||
+ | * Knoten, Kanten, gerichtet/ | ||
+ | * Zum Eulerzyklus: | ||
+ | * Notwendige und hinreichende Bedingungen für die Existenz eines Eulerzyklus kennen und begründen. | ||
+ | * Algorithmus zur Bestimmung eines Zyklus als Pseudocode formulieren. | ||
+ | * In einem konkreten Beispiel einen Eulerzyklus bestimmen. | ||
+ | * Zum Hamiltonzyklus: | ||
+ | * Rekursive Funktion zur Bestimmung eines Hamiltonzyklus formulieren und deren Komplexität (Grössenordnung der Anzahl Rechenschritte) abschätzen. | ||
+ | * Kürzeste Wege | ||
+ | * Algorithmus von Dijkstra auf einfachem Beispiel anwenden. | ||
+ | * Algorithmus von Dijkstra als Pseudocode formulieren und dessen Komplexität abschätzen. | ||
+ | * Begründen, warum der Algorithmus von Dijkstra für die Routenplanung im grossen Massstab nicht effizient genug ist.\ | ||
+ | * Graphensuche mit Todo-Liste | ||
+ | * Pseudo-Code wiedergeben und/oder anwenden. | ||
+ | * Unterschiedliche Arten der Handhabung der Todo-Liste verstehen/ | ||
+ | |||
+ | ===== Arbeitsblätter ===== | ||
+ | * {{ : | ||
+ | * {{ : | ||
+ | |||
+ | ==== Hamiltonzyklus oder nicht? ==== | ||
+ | {{ : | ||
+ | |||
+ | {{ : | ||
+ | |||
+ | {{: | ||
+ | |||
+ | * {{ : | ||
+ | * {{ : | ||
===== Mathematische Notationen ===== | ===== Mathematische Notationen ===== | ||
* Knotenmenge (Vertexset) $V$. Anzahl Knoten $n=|V|$. $V$ ist oft ein Intervall natürlicher Zahlen, $\{0, | * Knotenmenge (Vertexset) $V$. Anzahl Knoten $n=|V|$. $V$ ist oft ein Intervall natürlicher Zahlen, $\{0, | ||
* Kantenmenge (Edgeset) $E$. Anzahl Kanten $m=|E|$. Die Elemente sind entweder Mengen aus genau zwei Knoten (ungerichtete Graphen) oder Paare von Knoten (gerichtete Graphen). D.h. $\{2,5\}$ ist eine Kante vom Knoten 2 zum Knoten 5 und umgekehrt. $(2,5)$ hingegen ist eine gerichtete Kante (Einbahnstrasse) vom Knoten 2 zum Knoten 5. | * Kantenmenge (Edgeset) $E$. Anzahl Kanten $m=|E|$. Die Elemente sind entweder Mengen aus genau zwei Knoten (ungerichtete Graphen) oder Paare von Knoten (gerichtete Graphen). D.h. $\{2,5\}$ ist eine Kante vom Knoten 2 zum Knoten 5 und umgekehrt. $(2,5)$ hingegen ist eine gerichtete Kante (Einbahnstrasse) vom Knoten 2 zum Knoten 5. | ||
+ | |||
+ | ==== Begriffe ==== | ||
+ | * Nachbarschaft eines Knotens $v \in V$: $N^+(v) = \{u\in V \mid (v,u) \in E\}$, $N^-(v) = \{u\in V \mid (u,v) \in E\}$. $N(v) = N^+(v) \cup N^-(v)$. | ||
+ | * Grad eines Knotens $d^+(v) = |N^+(v)|$, $d^-(v) = |N^-(v)|$, $d(v) = |N(v)|$ | ||
+ | * Weg: Folge von Knoten $\{v_1, v_2, \ldots ,v_k\}$, so dass $(v_i, v_{i+1}) \in E \; \forall i=1,\ldots, k-1$. | ||
+ | * Zyklus: Weg mit $v_1=v_k$. | ||
+ | * Zusammenhängender Graph: Für alle Knotenpaare gibt es einen Weg von einen zum anderen. | ||
+ | * Baum: Zusammenhängender Graph ohne Zyklus. | ||
+ | * Kompletter Graph: Alle möglichen Kanten existieren. | ||
+ | * Planarer Graph: Kann in der Ebene ohne Kantenüberschneidungen gezeichnet werden. | ||
+ | |||
+ | |||
+ | ==== Datenstrukturen ==== | ||
+ | * Adjazenzmatrix: | ||
+ | * Nachbarslisten: | ||
+ | * Kanten: Eine Liste von Kanten mit je zwei Einträgen. | ||
+ | |||
+ | Je nach Problem und Art des Graphen ist die eine oder andere Datenstruktur effizienter. Es können auch mehrere gleichzeitig verwendet werden. | ||
+ | |||
+ | === Zusatzinformationen === | ||
+ | Je nachdem werden für die Knoten und Kanten weitere Daten gespeichert, | ||
+ | |||
+ | ==== Königsberger Brückenproblem ==== | ||
+ | * https:// | ||
+ | |||
+ | === Aufgaben === | ||
+ | - Finden Sie einen Weg, der die Kanten eines Würfels alle genau einmal beschreitet. Wie sieht es mit einem Tetraeder, Oktaeder, Dodekaeder und Ikosaeder aus? Wie sieht die Sache in einem 4-dimensionalen Würfel aus? | ||
+ | - Die Koordinaten der Eckpunkte eines Einheitsquadrates sind (0,0), (0,1), (1,1) und (1,0). Überlegen Sie sich, wie die Koordinaten eines Würfels sind und welche Eckpunkte miteinander verbunden werden. Verallgemeinern Sie auf 4 Dimensionen und schreiben Sie ein Programm, das die Knotenmenge und die Kantenmenge eines 4D-Würfels generiert. | ||
+ | - Finden Sie einen Weg, der die Kanten eines 4D-Würfels alle genau einmal beschreitet. | ||