efinf:blc2016:graphen:graphen [https://fginfo.ksbg.ch Fachgruppe Informatik der KSBG]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
===== 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.