Kantenzüge, Wege und Kreise
Einen Graphen erkunden wir entlang seiner Kanten. Wir definieren hierzu:
Definition (Kantenzug, geschlossen, offen, besuchte Ecken und Kanten)
Sei G = (E, K) ein Graph. Eine Folge a0, …, an in E heißt ein Kantenzug der Länge n in G von a0 nach an, falls ai ai + 1 ∈ K für alle i < n.
Gilt a0 = an, so heißt der Kantenzug geschlossen. Andernfalls heißt er offen.
Die Ecken a0, …, an heißen die besuchten Ecken und die Kanten ai ai +1 die besuchten Kanten des Kantenzuges.
Eine einzelne Ecke a gilt immer als Kantenzug der Länge 0.
Im oben dargestellten Graphen ist z. B. a, d, a, b, a ein geschlossener Kantenzug der Länge 4. Er besucht die Ecken a, b, d und die Kanten a d und a b.
Ecken und Kanten können in einem Kantenzug mehrfach besucht werden. Für einfache Besuche führen wir eigene Begriffe ein:
Definition (Weg, einfacher Kantenzug)
Ein Kantenzug a0, …, an in einem Graphen heißt ein Weg, falls er keine Ecke zweimal besucht, d. h. es gilt ai ≠ aj für alle i < j ≤ n. Er heißt ein einfacher Kantenzug, falls keine Kante zweimal besucht wird, d. h. es gilt
ai ai + 1 ≠ aj aj + 1 für alle i < j < n.
Jeder Weg ist offenbar ein einfacher Kantenzug. Die Umkehrung ist i. A. falsch. Im Graphen oben ist zum Beispiel b, c, d, a, b, e ein einfacher Kantenzug, aber kein Weg.
Schließlich definieren wir noch Kreise:
Definition (Kreis)
Ein geschlossener Kantenzug a0, …, an, a0 mit n ≥ 2 in einem Graphen G heißt ein Kreis in G mit (n + 1)-vielen Ecken, falls a0, …, an ein Weg ist.
Ein Graph G heißt kreisfrei, falls es keinen Kreis in G gibt.
Weiter heißt ein Graph G ein Kreis, wenn es einen Kreis a0, …, an, a0 in G gibt, der alle Kanten besucht.
Die kleinsten Kreise eines Graphen sind also bei dieser Definition „Dreiecke“ der Form a, b, c, a. Ein Kantenzug a, b, a gilt nicht als Kreis.
Obiger Graph enthält einen Kreis mit 4 Ecken, etwa a, b, c, d, a. Dagegen gibt es keinen Kreis, der die Ecke e enthält.
Die Graphen Cn sind Kreise. Der Graph Cn wird auch als der kanonische Kreis mit n Ecken bezeichnet. In Cn ist der Kantenzug 1, …, n, 1 ein Kreis mit n Ecken.