§3: Wege und Kreise in Graphen

7
Chr. Nelius: Graphentheorie (WS 2015/16)
§3 : Wege und Kreise in Graphen
(3.1) DEF: G = (E, K) sei ein Graph, und r ≥ 1 sei eine natürliche Zahl.
a) Ein Kantenzug
α = (α1 , α2 , . . . , αr )
in G ist eine endliche Folge von Kanten der Form
Ecken v1 , v2 , . . . , vr , vr+1 aus E . Anschaulich:
α:
α1
α2
α3
α4
αi
vi − vi+1 (i = 1, 2, . . . , r)
αr−1
αr−2
aus K mit
αr
v1 − v2 − v3 − v4 − . . . − vr−1 − vr − vr+1
Man nennt α auch einen Kantenzug zwischen v1 und vr+1 .
Gilt v1 = vr+1 , so heißt α ein geschlossener Kantenzug .
b) Die Anzahl ℓ(α) der Kanten eines Kantenzuges α heißt die Länge des Kantenzuges α .
BEM: In einem Kantenzug können Ecken und Kanten mehrfach vorkommen.
(3.2) BEISPIELE: Sei G der folgende Graph:
α1
v1
v2
α2
α7
α8
v5
α6
α3
α4
α5
v4
α5
α3
α4
α9
a)
v5 − v3 − v2 − v3 − v4
b)
v4 − v1 − v1 − v2 − v3 − v2
c)
v2 − v3 − v2 − v3
d)
v1 − v1
e)
v2 − v3 − v2 − v3 − v2
f)
v1 − v5 − v3 − v2 − v1 − v1
α8
α3
α1
α4
α1
α3
α7
α2
α4
v3
Kantenzug der Länge 4 zwischen v5 und v4 .
α4
α3
α9
Kantenzug der Länge 5 zwischen v4 und v2 .
Kantenzug der Länge 3 zwischen v2 und v3 .
geschlossener Kantenzug der Länge 1 .
α4
α5
α4
α4
α3
α2
geschlossener Kantenzug der Länge 4 .
α1
geschlossener Kantenzug der Länge 5 .
8
Chr. Nelius: Graphentheorie (WS 2015/16)
(3.3) DEF: G sei ein Graph. Ein Kantenzug
α:
αr−1
αr−2
α4
α3
α2
α1
αr
v1 − v2 − v3 − v4 − . . . − vr−1 − vr − vr+1
in G heißt ein Weg in G (zwischen v1 und vr+1 ) , wenn alle Ecken v1 , v2 , . . . , vr , vr+1 paarweise
verschieden sind.
(3.4) BEM: a) In einem Weg der Länge ≥ 2 sind auch die Kanten paarweise verschieden.
b) Ein Weg, der durch r Ecken verläuft, hat die Länge r − 1 .
(3.5) BEISPIELE: Sei G der Graph aus (3.2) :
a)
b)
α5
α3
α2
α8
v5 − v3 − v2 − v1 − v4
α5
α7
α8
ist ein Weg der Länge 4 .
ist ein Weg der Länge 3 .
v3 − v5 − v1 − v4
c) Die Kantenzüge aus (3.2) sind alles keine Wege.
(3.6) DEF: Sei G ein Graph. Ein geschlossener Kantenzug
α:
α1
α2
α3
α4
αr−2
αr−1
αr
v1 − v2 − v3 − v4 − . . . − vr−1 − vr − vr+1 = v1
in G heißt ein Kreis in G , wenn r = 1 gilt oder wenn die Ecken v1 , v2 , . . . , vr und alle Kanten
α1 , α2 , . . . , αr paarweise verschieden sind.
(3.7) BEM: a) Eine Schlinge ist ein Kreis der Länge 1 .
b) Ein Paar paralleler Kanten bildet einen Kreis der Länge 2 .
c) In einem schlichten Graphen haben Kreise mindestens die Länge 3 .
d) Ein Kreis der Länge 3 heißt auch ein Dreieck .
e) Ein Kreis, der durch r Ecken verläuft, hat die Länge r .
N
(3.8) DEF: Der Weg–Graph Pn (n ∈ ) ist ein schlichter Graph mit n paarweise verschiedenen
Ecken v1 , v2 , v3 , . . . , vn und n − 1 Kanten v1 v2 , v2 v3 , v3 v4 , . . . , vn−1 vn .
Beispiele:
P1 :
P2 :
(3.9) DEF: Der Kreis–Graph Cn ist für n ∈
P5 :
N folgendermaßen definiert:
C1 hat eine Ecke und eine Schlinge, C2 besteht aus 2 Ecken und einer Doppelkante, für n ≥ 3
ist Cn ein schlichter Graph mit n paarweise verschiedenen Ecken v1 , v2 , v3 , . . . , vn und n Kanten
v1 v2 , v2 v3 , v3 v4 , . . . , vn−1 vn , vn v1 .
9
Chr. Nelius: Graphentheorie (WS 2015/16)
Beispiele:
C1 :
(3.10) BEM:
(Weg) .
C2 :
C6 :
a) Der Name Pn für den Weg–Graphen kommt von dem englischen Wort “path”
b) Der Name Cn für den Kreis–Graphen kommt von dem englischen Wort “cycle” (Kreis) .
c) Entfernt man aus einem Kreis–Graphen Cn eine Kante, so entsteht ein Weg–Graph Pn .
(3.11) SATZ: Sei G ein Graph. Dann enthält jeder Kantenzug zwischen zwei verschiedenen Ecken
u und w von G auch einen Weg zwischen u und w .
(3.12) BEM: Ein geschlossener Kantenzug gerader Länge muss keinen Kreis enthalten. Ist α eine
Kante in einem Graphen G , die keine Schlinge ist, so ist (α, α) ein geschlossener Kantenzug der
Länge 2 , der keinen Kreis enthält. Jedoch gilt:
(3.13) SATZ: Sei G ein Graph. Dann enthält jeder geschlossene Kantenzug ungerader Länge in
G einen Kreis ungerader Länge.
(3.14) DEF: Ein Kreis gerader Länge in einem Graphen heißt ein gerader Kreis, und ein Kreis
ungerader Länge heißt ein ungerader Kreis.

Download Report