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 natü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 Länge des Kantenzuges α . BEM: In einem Kantenzug kö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 Länge 4 zwischen v5 und v4 . α4 α3 α9 Kantenzug der Länge 5 zwischen v4 und v2 . Kantenzug der Länge 3 zwischen v2 und v3 . geschlossener Kantenzug der Länge 1 . α4 α5 α4 α4 α3 α2 geschlossener Kantenzug der Länge 4 . α1 geschlossener Kantenzug der Lä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 Länge ≥ 2 sind auch die Kanten paarweise verschieden. b) Ein Weg, der durch r Ecken verläuft, hat die Lä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 Länge 4 . ist ein Weg der Länge 3 . v3 − v5 − v1 − v4 c) Die Kantenzü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 Länge 1 . b) Ein Paar paralleler Kanten bildet einen Kreis der Länge 2 . c) In einem schlichten Graphen haben Kreise mindestens die Länge 3 . d) Ein Kreis der Länge 3 heißt auch ein Dreieck . e) Ein Kreis, der durch r Ecken verläuft, hat die Lä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 für n ∈ P5 : N folgendermaßen definiert: C1 hat eine Ecke und eine Schlinge, C2 besteht aus 2 Ecken und einer Doppelkante, fü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 für den Weg–Graphen kommt von dem englischen Wort “path” b) Der Name Cn fü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 enthä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 Länge muss keinen Kreis enthalten. Ist α eine Kante in einem Graphen G , die keine Schlinge ist, so ist (α, α) ein geschlossener Kantenzug der Länge 2 , der keinen Kreis enthält. Jedoch gilt: (3.13) SATZ: Sei G ein Graph. Dann enthält jeder geschlossene Kantenzug ungerader Länge in G einen Kreis ungerader Länge. (3.14) DEF: Ein Kreis gerader Länge in einem Graphen heißt ein gerader Kreis, und ein Kreis ungerader Länge heißt ein ungerader Kreis.
© Copyright 2024 ExpyDoc