Wanderungen in einem Graphen

 In einem Graphen können wir uns entlang einer Kante von einer Ecke zur nächsten bewegen. Wiederholte derartige Bewegungen ergeben einen Kantenzug. Es gibt verschiedene Möglichkeiten, Kantenzüge zu notieren. Wir bevorzugen im Folgenden die Angabe der besuchten Ecken in Form einer Folge. Genaueres regeln die Definitionen.

Definition (Kantenzug, besuchte Ecke und Kante)

Seien G = (E, K) ein Graph und n ≥ 0. Eine endliche Folge a0, …, an in E heißt ein Kantenzug der Länge n von a0 nach an in G, falls gilt:

a0a1, a1a2, …, an − 1an  ∈  K.

Gilt a0 = an, so heißt der Kantenzug geschlossen. Andernfalls heißt er offen. Die Ecken a0, …, an heißen die besuchten Ecken. Wir sagen auch, dass die Ecke ai zum Zeitpunkt i, im i-ten Schritt oder an der Position i besucht wird. Analog nennen wir die Kanten a0a1, …, an − 1an die besuchten Kanten des Kantenzugs. Der Besuchszeitpunkt einer Kante ai − 1 ai ist dabei i.

Definition (einfacher Kantenzug)

Sei G = (E, K) ein Graph. Ein Kantenzug in G heißt einfach, falls jede besuchte Kante nur einmal besucht wird.

Definition (Weg)

Sei G = (E, K) ein Graph. Ein Kantenzug in G heißt ein Weg, falls jede besuchte Ecke nur einmal besucht wird.

 Jeder Weg ist ein einfacher Kantenzug, die Umkehrung ist, wie die folgenden Beispiel zeigen, im Allgemeinen nicht gültig.

Beispiele

(1)

Für jede Ecke a ist a ein Kantenzug der Länge 0 (von a nach a). Der Kantenzug a besucht keine Kante. Er ist geschlossen und ein Weg. Ein geschlossener Kantenzug positiver Länge kann dagegen kein Weg sein, da er die Startecke zweimal besucht.

(2)

In einem Kantenzug a0, …, an wird die Startecke a0 zum Zeitpunkt 0 besucht, die Kante a0 a1 ist die erste besuchte Kante (der Besuchszeitpunkt ist 1).

(3)

Kantenzüge mit ai = ai + 1 existieren nicht, da unsere Graphen schlingenfrei sind. Dagegen sind Abschnitte der Form a, b, a möglich. In diesem Fall bewegen wir uns von a nach b und dann von b gleich wieder zurück nach a. Dabei wird die Kante ab zweimal besucht.

(4)

Jeder Kreis a0, …, an, a0 in einem Graphen ist ein einfacher geschlossener Kantenzug der Länge n + 1, aber kein Weg, da n ≥ 2 gilt.

(5)

Eine „8“ in einem Graphen ist ein einfacher geschlossener Kantenzug, aber kein Kreis.

(6)

Sei G = (E, K) mit E = { 1, …, 9 } und

K  =  { 12, 18, 23, 25, 37, 47, 56, 58, 59, 67, 79 }.

ema21-AbbID2-2-1

Wir betrachteten einige Kantenzüge in G und ihre Eigenschaften.

1, 2, 3, 2, 5, 8

Der Kantenzug ist offen. Er ist nicht einfach (und damit kein Weg), da die Kante 23 = 32 zweimal besucht wird (zu den Zeitpunkten 2 und 3). Der Kantenzug hat die Länge 5. Die Ecke 2 wird zweimal besucht (zu den Zeitpunkten 1 und 3).

2, 3, 7, 9, 5, 2

Der Kantenzug ist einfach und geschlossen, aber kein Weg. Er zeigt, dass der Graph einen Kreis mit fünf Ecken enthält.

8, 5, 6, 7, 9, 5, 2

Der Kantenzug ist offen und einfach, aber kein Weg. Die Ecke 5 wird zweimal besucht.

4, 7, 9, 5, 8, 1, 2, 3

Der Kantenzug ist ein Weg, der alle Ecken mit Ausnahme der 6 besucht.

1, 2, 5, 8, 1, 2, 5, 8

Der Kantenzug hat die Länge 7. Die Menge { 12, 25, 58, 81, 12, 25, 58 } der besuchten Kanten hat die Mächtigkeit 4. Das Gleiche gilt für die Menge { 1, 2, 5, 8, 1, 2, 5, 8 } der besuchten Ecken.

Die Eckenfolge 4, 7, 5, 8 ist kein Kantenzug, da dem Graphen die Kante 57 = 75 fehlt. Es gibt keinen Kantenzug der Form a, b, c, a, da der Graph kein Dreieck enthält.