• Vorlage labyrinth.rb und Lösungsvorschlag
• Anderer Generator Code Qualität: WTF. Wer mir die Funktionsweise des Codes überzeugend erklären kann, kriegt ein Arduino-Set

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

• Graphentheorie
• Datei für Aufgabe 17, Kürzester Weg

Knacknuss

PDF-Version (z.B. für Inkscape)

• Graphen-Bibliothek, Ruby-Version
• Graphen-Bibliothek, Processing-Version (nicht direkt Eclipse-tauglich)

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

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

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

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.

• https://de.wikipedia.org/wiki/K%C3%B6nigsberger_Br%C3%BCckenproblem

1. 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?
2. 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.
3. Finden Sie einen Weg, der die Kanten eines 4D-Würfels alle genau einmal beschreitet.