• Graphentheorie

Knacknuss

Graphen-Bibliothek

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