Differences

This shows you the differences between two versions of the page.

--- efinf:blc2016:graphen:graphen [2017/01/27 09:45] – [Königsberger Brückenproblem] Ivo Blöchliger
+++ efinf:blc2016:graphen:graphen [2017/04/04 13:30] (current) – [Labyrinth-Generator] Ivo Blöchliger
@@ Line 1: / Line 1: @@
+===== Labyrinth-Generator =====
+  * Vorlage {{ :efinf:blc2016:graphen:labyrinth.rb |}} und {{ :efinf:blc2016:graphen:labyrinth-solution.rb |Lösungsvorschlag}}
+  * Anderer Generator {{ :efinf:blc2016:graphen:labgen.rb |Code Qualität: WTF}}. Wer mir die Funktionsweise des Codes überzeugend erklären kann, kriegt ein Arduino-Set ;-)
+===== Lernziele / Prüfungsstoff =====
+  * Begriffe und Definitionen kennen und anwenden, wie
+    * Knoten, Kanten, gerichtet/ungerichtet, Grad eines Knotens, Weg, Zyklus, kompletter Graph, Baum, $N^+(v)$, $N^-(v)$, zusammenhängender Graph, planarer Graph
+  * 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/anwenden.
+===== Arbeitsblätter =====
+  * {{ :efinf:blc2016:graphen:graphen.pdf |Graphentheorie}}
+  * {{ :efinf:blc2016:graphen:shortest.txt |Datei für Aufgabe 17, Kürzester Weg}}
+==== Hamiltonzyklus oder nicht? ====
+{{ :efinf:blc2016:graphen:knacknuss.txt |Knacknuss}}
+{{ :efinf:blc2016:graphen:knacknuss.pdf |PDF-Version (z.B. für Inkscape)}}
+{{:efinf:blc2016:graphen:plain.png?direct&200|}}
+  * {{ :efinf:blc2016:graphen:graph-5a.rb |Graphen-Bibliothek, Ruby-Version}}
+  * {{ :efinf:blc2016:graphen:graphlib.zip |Graphen-Bibliothek, Processing-Version (nicht direkt Eclipse-tauglich)}}
+===== Mathematische Notationen =====
+  * Knotenmenge (Vertexset) $V$. Anzahl Knoten $n=|V|$. $V$ ist oft ein Intervall natürlicher Zahlen, $\{0,1,2,\ldots,n-1\}$.
+  * 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: Für jedes Knotenpaar $i,j$ einen Eintrag $a_{i,j}$, der angibt, ob die Verbindung von $i$ nach $j$ existiert.
+  * Nachbarslisten: Für jeden Knoten $i$ eine Liste $N(i)$, die die Nachbarn von $i$ angibt. (Eventuell wird beides, $N^+$ und $N^-$ gespeichert.
+  * 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, wie z.B. die Länge der Kanten, die Koordinaten der Knoten etc.
+==== Königsberger Brückenproblem ====
+  * https://de.wikipedia.org/wiki/K%C3%B6nigsberger_Br%C3%BCckenproblem
+=== 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.