Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
efinf:blc2016:graphen:graphen [2017/01/24 09:24] Ivo Blöchliger [Begriffe] |
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, | ||
Line 12: | Line 46: | ||
* Kompletter Graph: Alle möglichen Kanten existieren. | * Kompletter Graph: Alle möglichen Kanten existieren. | ||
* Planarer Graph: Kann in der Ebene ohne Kantenüberschneidungen gezeichnet werden. | * 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 ==== | ==== Königsberger Brückenproblem ==== | ||
Line 18: | Line 63: | ||
=== Aufgaben === | === 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? | - 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. | - 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. | ||