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


Ein Weg in einem Graphen heißt Zyklus, wenn ist.

Den konstanten Weg und den einen Weg der Form betrachten wir als triviale Zyklen.


Ein Kreis in einem Graphen ist ein Zyklus der Länge 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.


Ein Graph heißt Rundgang, wenn es in ihm einen Kreis gibt, der alle Knotenpunkte und alle Kanten genau einmal durchläuft.

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


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

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 .


Der Umfang eines zyklischen Graphen ist die längste Länge eines Kreises in .

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.