Graphen

Pfade und Kreise

Ein Weg / Pfad der Länge K von $v_1$ nach $v_{1+k}$ ist eine Folge von Knoten mit.

$V_p = \{v_1, v_2, \ldots, v_{3+k}\}$

oder als Folge von Kanten:

$E_p = \{ \{v_1, v_2\}, \{v_2, v_3\}, \ldots, \{v_k, v_{1+k}\} \}$

indem kein Knoten und keine Kante mehrfach vorkommen darf.

Ein Graph heißt zusammenhängend, wenn je 2 Knoten durch einen Pfad verbunden sind.

Ein Kantenzug bezeichnet eine Knotenfolge, bei der Knoten und Kanten mehrfach vorkommen dürfen.

Der Abstand $d_G(v_1, v_2)$ zweier Knoten $v_1$ und $v_2$ in $G$ ist definiert als die minimale Kantenanzahl eines Pfades von $v_1$ nach $v_2$.

Den größtmöglichen Abstand zweier Knoten nennt man Durchmesser von $G$ oder $diam(G)$.

Als Kreis bezeichnet man einen Pfad der Länge K von $v_1$ nach $v_{1+k}$, der um die Kante $\{v_{1+k}, v_1\}$ erweitert wird: ein Kreis der Länge $K+1$, $C_{K+1}$ (Circle). Man nennt den Pfad auch geschlossen.

Enthält ein Graph einen Kreis, so nennt man ihn kreisfrei / offen.

Ein Pfad, der alle Knoten des zugehörigen Graphen genau einmal enthält, nennt man Hamiltonpfad.

Ist der Pfad zusätzlich geschlossen, so nennen wir ihn Hamiltonkreis.