Mathematische Grundlagen

Definition:  Ein (gerichteter) Graph ist ein Paar G = (V, E), hierbei ist V eine endliche Menge von Knoten und E ⊆ V × V eine Relation auf V, die Menge der Kanten.

Beispiel:  G = (V, E)   mit   V = {0, 1, 2, 3, 4}   und
E = {(0,1), (0,2), (3,0), (2,0), (1,2)}

Definition:  Sei G = (V, E) ein Graph und (u, v) ∈ E eine Kante von Knoten u nach Knoten v. Dann ist v direkter Nachfolger von u und u direkter Vorgänger von v.

Der Ausgangsgrad o(u) eines Knotens u ist gleich der Anzahl seiner direkten Nachfolger, d.h.

o(u)  =  | { w |  (u, w) ∈ E } |.

Der Eingangsgrad i(u) eines Knotens u ist gleich der Anzahl seiner direkten Vorgänger, d.h.

 i(u)  =   | { v |  (v, u) ∈ E } |.

Ein Knoten u heißt isoliert wenn  o(u) = i(u) = 0  gilt.

Eine Kante (u, u) von einem Knoten u zu sich selbst heißt Schlinge.

Beispiel:  In G ist Knoten 0 direkter Nachfolger von Knoten 3; Knoten 2 hat den Ausgangsgrad 1 und den Eingangsgrad 2. Knoten 4 ist isoliert. G hat keine Schlingen.

Definition:  Ein Pfad (oder Kantenzug) in einem Graphen ist eine endliche Folge von Kanten

p  =  (u₀, v₀) ... (u_m-1, v_m-1)

mit   m ∈ ℕ₀   und   v_i-1 = u_i   für alle   i ∈ {1, ..., m-1}.

Hierbei ist m die Länge des Pfades. Wir identifizieren Kanten und Pfade der Länge 1. Der Pfad der Länge 0 heißt der leere Pfad, wir bezeichnen ihn mit λ. Der Knoten u₀ heißt Anfangs­knoten von p, der Knoten v_m-1 heißt Endknoten. Alle anderen Knoten von p heißen innere Knoten.

Beispiel:  Pfade in obigem Graphen G sind

p₁ = (3,0) (0,2) (2,0) (0,2)

p₂ = (0,1) (1,2) (2,0)

p₃ = (3,0)

p₄ = (3,0) (0,1) (1,2) (2,0)

Der Pfad p₁ hat die Länge 4, der Pfad p₃ hat die Länge 1. Im Pfad p₂ ist der Knoten 0 zugleich Anfangs- und Endknoten. In p₄ ist Knoten 0 sowohl innerer Knoten als auch Endknoten.

Definition:  Sei  p = (u₀, v₀) ... (u_m-1, v_m-1)  ein Pfad in einem Graphen G.

p heißt einfach, wenn er keine Kante mehrfach durchläuft, d.h. wenn alle (u_i, v_i) paarweise verschieden sind (i = 0, ..., m-1).

p heißt Zyklus, wenn er geschlossen ist, d.h. wenn  v_m-1 = u₀  gilt.

p heißt Weg, wenn er keinen Knoten mehrfach durchläuft, d.h. wenn alle u_i unter­einander und alle v_j unter­einander paarweise verschieden sind (i, j = 0, ..., m-1).

p heißt Kreis, wenn er ein Weg ist und geschlossen ist, d.h. ein Zyklus ist.

Beispiel:  Der Pfad p₁ aus dem vorigen Beispiel ist kein einfacher Pfad, weil er die Kante (0,2) zweimal enthält. Der Pfad p₄ ist ein einfacher Pfad, aber kein Weg, weil er den Knoten 0 mehrmals durchläuft. Der Pfad p₂ ist ein Zyklus und sogar ein Kreis.

Satz:  Sei G = (V, E) ein Graph mit n Knoten, d.h. |V| = n. Dann hat jeder Weg in G höchstens die Länge n.

Beweis:  Sei   p = (u₀, v₀) ... (u_m-1, v_m-1)   ein Pfad der Länge m > n. Dann können nicht alle u_i verschieden sein, da es nur n Knoten gibt. Also ist p kein Weg.

Satz:  Wenn es in G einen Pfad von u nach v gibt, dann gibt es auch einen Weg von u nach v.

Beweis:  Sei   p = (u₀, v₀) ... (u_m-1, v_m-1)   ein Pfad von u nach v. Aus p wird wie folgt ein Weg konstruiert:

Solange p kein Weg ist wiederhole:

Definition:  Ein gerichteter Graph T = (V, E) ist ein Baum, wenn

• er genau einen Knoten mit Eingangsgrad 0 enthält; dieser Knoten ist die Wurzel des Baumes,
• alle anderen Knoten den Eingangsgrad 1 haben, und
• er keine Zyklen enthält.

Definition:  Sei T ein Baum. Ein Knoten b heißt Blatt, wenn er keine Nachfolger hat; alle anderen Knoten heißen innere Knoten des Baumes.

Die Tiefe d(v) eines Knotens v ist die Länge des Weges von der Wurzel r nach v. Die Tiefe d(T) des Baumes ist die maximale Tiefe der Knoten.

Definition:  Ein Baum T ist ein binärer Baum, wenn jeder Knoten einen Ausgangsgrad von höchstens 2 hat.

Definition:  Ein binärer Baum T heißt fast vollständig, wenn

• alle Knoten der Tiefe  <  d(T)-1 den Ausgangsgrad 2 haben, und
• höchstens ein Knoten den Ausgangsgrad 1 hat.

Satz:  Ein voll­ständiger oder ein fast voll­ständiger binärer Baum T mit n Knoten hat eine Tiefe von

d(T))  =  int(log₂(n)).

Definition:  Ein gerichteter Graph G = (V, E) ist ein ungerichteter Graph, wenn seine Kanten­relation E symmetrisch ist, d.h. wenn gilt:

E = E ^-1.

Definition:  Sei G = (V, E) ein ungerichteter Graph ohne Schlingen.

G heißt zusammen­hängend, wenn es in G von jedem Knoten u zu jedem anderen Knoten v mindestens einen Weg gibt.

G heißt kreisfrei, wenn es in G von jedem Knoten u zu jedem anderen Knoten v höchstens einen Weg gibt.

G ist ein Baum, wenn G zusammen­hängend und kreisfrei ist, d.h. wenn es in G von jedem Knoten u zu jedem anderen Knoten v genau einen Weg gibt.

Definition:  Sei G = (V, E) ein ungerichteter Graph ohne Schlingen. Ein maximaler zusammen­hängender Teilgraph von G heißt Zusammenhangs­komponente (connected component) von G.

Definition:  Sei G = (V, E) ein ungerichteter Graph ohne Schlingen. G heißt vollständig, wenn jeder Knoten mit jedem anderen Knoten durch eine Kante verbunden ist.

Definition:  Sei G = (V, E) ein ungerichteter Graph. Ein Graph G' = (V', E') heißt Teilgraph von G, wenn er aus gewissen Knoten von G und Kanten von G zwischen diesen Knoten besteht und wenn er ungerichtet ist, d.h. wenn gilt

V' ⊆ V,

E' ⊆ E ∩ V' × V'     und

E' = E' ^-1 .

Definition:  Sei G = (V, E) ein Graph und A eine Menge. Eine Abbildung

w : V → A,

die jedem Knoten v ∈ V ein Element w(v) ∈ A zuordnet, heißt Knoten­markierung.

Definition:  Sei G = (V, E) ein (gerichteter) Graph und A eine Menge. Eine Abbildung

w : E → A,

die jeder Kante e ∈ E ein Element w(e) ∈ A zuordnet, heißt Kanten­markierung.

Beispiel:  Sei A = ℕ₀. Als Kanten­markierung w wählen wir die Abbildung, die jeder Kante des Graphen die Zahl 1 zuordnet. Die Menge ℕ₀ bildet mit der Operation + und dem neutralen Element 0 ein Monoid. Daher lässt sich die Markierung der Kanten zu einer Markierung der Pfade erweitern:

w(λ) = 0   und

w(pe) = w(p) + w(e)

für alle Pfade p und alle Kanten e.

Somit wird in diesem Beispiel jedem Pfad p durch die Markierung w(p) seine Länge zugeordnet.

Aufgabe 1:  Sei T = (V, E) ein gerichteter Graph. Beweisen Sie unter Benutzung der oben angegebenen Definition für einen (gerichteten) Baum:

T ist ein Baum genau dann, wenn es einen Knoten w ∈ V gibt, von dem aus zu allen anderen Knoten aus V jeweils genau ein Pfad hinführt.