Ungerichteter Graph/Zyklus/Kreis/Einführung/Textabschnitt

Definition

Ein Weg ${}v_{1},\ldots ,v_{m}$ in einem Graphen ${}(V,E)$ heißt Zyklus, wenn ${}v_{1}=v_{m}$ ist.

Den konstanten Weg und den einen Weg der Form ${}u,v,u$ betrachten wir als triviale Zyklen.

Definition

Ein Kreis in einem Graphen ist ein Zyklus der Länge ${}\geq 3$ ohne Wiederholungen.

Mit der Formulierung ohne Wiederholungen meint man ohne Wiederholungen in der Knotenmenge, was insbesondere keine Wiederholungen in der Kantenmenge impliziert. Umgekehrt kann es aber Wege ohne Kantenwiederholungen geben, bei denen sich Knotenpunkte wiederholen, dies sind keine Kreise. Ein zyklischer Graph ist ein Graph mit zumindest einem Kreis.

Die Circle line von London ist für sich genommen ein Rundgang.

Definition

Ein Graph ${}G$ heißt Rundgang, wenn es in ihm einen Kreis ${}v_{1},v_{2},\ldots ,v_{m}=v_{1}$ gibt, der alle Knotenpunkte und alle Kanten genau einmal durchläuft.

Die beiden folgenden Definition ergeben nur für zyklische Graphen Sinn.

Definition

Die Taille eines zyklischen Graphen ist die kürzeste Länge eines Kreises in ${}G$.

Statt mit der kürzesten Länge eines Kreises kann man genauso gut mit der Länge eines nichttrivialen Zyklus arbeiten. Die Taille ist zumindest ${}3$.

Definition

Der Umfang eines zyklischen Graphen ${}G$ ist die längste Länge eines Kreises in ${}G$.

Hier kann man nicht mit beliebigen Zyklen arbeiten, da man diese ja mehrfach durchlaufen kann. Der Umfang ist durch die Knotenanzahl des Graphen beschränkt.