Graphentheorie

Christian M. Meyer

Graphen

Definition: Ein (ungerichteter) Graph ist ein Tupel G = (V, E) bestehend aus der

Knotenmenge  V und der
Kantenmenge  E ⊆ V × V.

Nachbarschaft und Grad: Sei G = (V, E) ein Graph. Die folgenden Operationen sind für einen beliebigen Knoten v ∈ V definiert:

Nachfolgeknoten:  S(v) = {w ∈ V | (v, w) ∈ E}
Vorgängerknoten:  P(v) = {w ∈ V | (w, v) ∈ E}
Nachbarknoten:  N(v) = {w ∈ V | (v, w) ∈ E ∨ (w, v) ∈ E} = S(v) ∪ P(v)
Außengrad:  d^{+}(v) = |S(v)|  (Anzahl der in v beginnenden Kanten)
Innengrad:  d^{−}(v) = |P(v)|  (Anzahl der in v endenden Kanten)
Grad:  d(v) = d^{+}(v) + d^{−}(v)

Damit gilt: 2 ∑_{v∈V} d^{+}(v) = 2 ∑_{v∈V} d^{−}(v) = ∑_{v∈V} d(v) = 2 · |E| Graphen: Ein Graph G = (V, E) heißt

knotenendlich  ⇔ |V | < ∞
kantenendlich  ⇔ |E| < ∞
k-regulär ⇔ ∀ v ∈ V. d(v) = k (mit k ∈ ℕ_{0})
vollständig  ⇔ ∀ v, w ∈ V. (v, w) ∈ E ⇒ |E| = \frac{|V |·(|V |−1)}{2}
einfach/schlicht  ⇔ G hat weder Schlingen noch Mehrfachkanten.

Sei G′ = (V′, E′) ein weiterer Graph. G′ heißt

Teilgraph von G ⇔ G′ ⊆ G ⇔ V′ ⊆ V ∧ E′ ⊆ E
Obergraph von G  ⇔ G ⊆ G′
Clique von G  ⇔ G′ ⊆ G ∧ G′ vollständig
Partialgraph von G ⇔ G′ ⊆ G ∧ E′ = {(v, w) ∈ E | v, w ∈ V′} (auch: Untergraph von G)
isomorph zu G  ⇔ ∃ φ: V ⟶ V′. φ bijektiv. ∀ (v, w) ∈ E. (φ(v), φ(w)) ∈ E′

Zu beachten ist, dass die Inklusion ⊆ eine Ordnungsrelation auf G bildet. Knoten: Ein Knoten v ∈ V heißt

isoliert  ⇔ d(v) = 0
adjazent zu w ∈ V  ⇔ (v, w) ∈ E  (auch: v und w sind adjazent)

Kanten: Eine Kante e = (v, w) ∈ E heißt

Schlinge  ⇔ v = w
Mehrfachkante  ⇔ e = (v, w) kommt mehrfach in E vor (auch: Parallele)
inzident zu u ∈ V  ⇔ u = v ∨ u = w  (auch: e und u sind inzident)

Operationen: Für zwei Graphen G_{1} = (V_{1}, E_{1}) und G_{2} = (V_{2}, E_{2}) sind folgende Operationen definiert:

Reduktion:  G_{1} \ G_{2} := (V_{1} \ V_{2}, E_{1} \ E_{2})
Vereinigung:  G_{1} ∪ G_{2} := (V_{1} ∪ V_{2}, E_{1} ∪ E_{2})
Schnitt:  G_{1} ∩ G_{2} := (V_{1} ∩ V_{2}, E_{1} ∩ E_{2})
Ringsumme:  G_{1} ⊕ G_{2} := (V_{1} ∪ V_{2}, (E_{1} ∪ E_{2}) \ (E_{1} ∩ E_{2}))
Inversion:  G_{1}^{−1} := (V_{1}, E_{1}^{−1}) mit E_{1}^{−1} := {(w, v) | (v, w) ∈ E_{1}}

Wege: Eine Folge von Knoten p = (v_{1}, v_{2}, …, v_{n}) aus G = (V, E) mit v_{i} ∈ V für alle 1 ≤ i ≤ n heißt

Weg/Kantenzug:  ⇔ p = (v_{1}, v_{2}, …, v_{n}) ∧ ∀ v_{i}, v_{n} ∈ V. (v_{i}, v_{i+1}) ∈ E  mit 1 ≤ i < n
Kreis/Zyklus:  ⇔ p ist ein Weg ∧ v_{1} = v_{n}

Ein Weg verbindet also die Knoten v_{1} und v_{n}, indem die Knoten v_{2}, …, v_{n−1} über die entsprechenden Kanten von G besucht werden. Der Knoten v_{1} heißt hier Anfangsknoten, der Knoten v_{2} Endknoten des Weges. Man definiert:

Wegegraph zu G:  G^{+} := (V, E^{+}) mit E^{+} := {(v, w) ∈ V × V | es gibt einen Weg von v nach w}

Der Wegegraph enthält nur Wege p mit ||p|| ≥ 1. Vereinigt man alle Schlingen mit dem Wegegraphen, ergibt sich die reflexive und transitive Hülle von G:

G^{∗} := (V, E^{+} ∪ {(v, v) | v ∈ V })

Gerichtete Graphen: Ein gerichteter Graph G⃗ = (V, E) ist ein Graph, dessen Kanten eine Richtung besitzen, folglich gilt nicht länger (v, w) ∈ E ⇒ (w, v) ∈ E. Die oben eingeführten Bezeichnungen bleiben erhalten. Der zu G⃗ zugeordnete ungerichtete Graph wird mit

\overline{G} = G ∪ G^{−1} = (V, E ∪ E^{−1})

bezeichnet.

Wegeigenschaften: Ein Weg bzw. Kreis p = (v_{1}, v_{2}, …, v_{n}) ∈ G^{+} in einem Graphen G = (V, E) heißt

knoteneinfach  ⇔ ∀ i, j ∈ ℕ_{1}^{n}. i ≠ j  v_{i} ≠ v_{j}
kanteneinfach  ⇔ ∀ i, j ∈ ℕ_{1}^{n−1}. i ≠ j  v_{i} ≠ v_{j} ∧ v_{i+1} ≠ v_{j+1}
knoteneinfach  ⇔ ∀ v, w ∈ p. v ≠ w
kanteneinfach  ⇔ ∀ (v_{1}, v_{2}), (w_{1}, w_{2}) ∈ p. (v_{1}, v_{2}) ≠ (w_{1}, w_{2}) mit v_{1} ≠ w_{1}, v_{2} ≠ w_{2}
eulersch  ⇔ p ist ein kanteneinfacher Zyklus ∧ ∀ (v, w) ∈ E. (v, w) ∈ p
hamiltonsch  ⇔ p ist ein knoteneinfacher Zyklus ∧ ∀ v ∈ V. v ∈ p

Ein knoteneinfacher Weg ist gleichzeitig ein kanteneinfacher Weg. Ein eulerscher Zyklus wird auch als eulersche Linie (Kreis) bezeichnet. Entsprechend werden hamiltonsche Zyklen auch hamiltonsche Linie (Kreis) genannt. Die Länge eines Weges gibt die Anzahl der Kanten an, also ||p|| = n−1. Zwei Wege p_{1} = (v_{1}, … v_{k}) und p_{2} = (w_{1}, …, w_{ℓ}) heißen

knotendisjunkt  ⇔ ∀ v ∈ p_{1}. v ∉ p_{2}
kantendisjunkt  ⇔ ∀ (v, w) ∈ p_{1}. (v, w) ∉ p_{2}
konkateniert  ⇔ p_{1} ∘ p_{2} = (v_{1}, …, v_{k}, w_{1}, … w_{ℓ})

Zusammenhang: Sei G = (V, E) und w ∈ V. G heißt

zusammenhängend ⇔ ∀ v, w ∈ V. v ist mit w verbunden.

Ein Knoten v ∈ V heißt

verbunden mit w  ⇔ ∃ p ∈ G^{+}. p = (v, …, w)
Trennknoten  ⇔ G zusammenhängend ∧ (V \ {v}, E) nicht zusammenhängend

Ein Kante e = (v, w) ∈ E heißt

Schnittkante  ⇔ G zusammenhängend ∧ (V, E \ {e}) nicht zusammenhängend

Ein Teilgraph G′ = (V′, E′) ⊆ G heißt

Komponente von G ⇔ G′ zusammenhängend.
Gerüst von G  ⇔ G = (V, Ẽ)
Trennmenge Ṽ:  G zusammenhängend ∧ (V \ Ṽ, E) nicht zusammenhängend
Schnittmenge Ẽ:  G zusammenhängend ∧ (V, E \ Ẽ) nicht zusammenhängend

G heißt mehrfach zusammenhängend, falls |Ẽ| = 0 gilt, es also keine Schnittkanten gibt.

Satz über eulersche Graphen: Für einen Graphen G = (V, E) sind äquivalent:

(1) G ist eulersch.
(2) G ist zusammenhängend und ungerichtet ∧ ∀ v ∈ V. d(v) ist gerade
(3) G ist zusammenhängend und gerichtet ∧ ∀ v ∈ V. d^{+}(v) = d^{−}(v)

Zyklen: Ein Graph G = (V, E) heißt

zyklisch  ⇔ G hat (mindestens) einen Zyklus
azyklisch  ⇔ G hat keinen Zyklus
azyklisch  ⇒ ∃ v, w ∈ V. d^{+}(v) = 0 ∧ d^{−}(w) = 0

Planarität: Sei G′ = (V′, E′). Ein Graph G = (V, E) heißt

planar  ⇔ G lässt sich ohne Kantenkreuzungen in der Ebene darstellen.
homeomorph zu G′ ⇔ ∀ v ∈ V ⊕ V′. d(v) = 2

Färbbarkeit: Sei G = (V, E) und S eine Menge von Farben. Eine Knotenmarkierung ist gegeben durch f: V ⟶ S. Die Abbildung f heißt

Färbung  ⇔ ∀ v ∈ V. ∀w ∈ N(v). f(v) ≠ f(w)

Weitere Eigenschaften:

G ist k-färbbar  ⇔ ∃ f: V ⟶ S. f ist eine Färbung von G ∧ |S| = k
chromatische Zahl:  χ(G) = min{k ∈ ℕ | G ist k-färbbar}
Vierfarbensatz:  G ist planar ⇒ χ(G) = 4
Vollständigkeit  G ist vollständig ⇒ χ(G) = |V |

Analog definiert man Kantenmarkierungen als eine Abbildung c: V × V ⟶ S für eine beliebige Wertemenge S. Man nennt c(e) das Gewicht, die Kapazität oder die Kosten von e ∈ E.