Der Abstand zweier Ecken
Wir haben gesehen, dass Kantenzüge die Beschreibung von Zusammenhangseigenschaften eines Graphen ermöglichen. Darüber hinaus sind sie geeignet, eine Abstandsfunktion in einem Graphen zu erklären. Diese Funktion misst, wie weit zwei Ecken in einem Graphen voneinander entfernt sind:
Definition (Abstand)
Sei G = (E, K) ein Graph. Für alle a, b ∈ E mit a ∼ b setzen wir
d(a, b) = „die Länge eines kürzesten Kantenzugs von a nach b in G“.
Für a, b ∈ E mit non(a ∼ b) setzen wir d(a, b) = ∞. Wir nennen d(a, b) den Abstand von a und b in G.
Das „d“ steht für „Distanz“ oder „distance“. Genauer schreiben wir dG statt d, wenn wir die Abhängigkeit der Abstandsfunktion vom betrachteten Graphen hervorheben möchten. Eine Verwechslung mit dem Grad d(a) einer Ecke ist in der Regel nicht zu befürchten.
Es gilt d : E × E → ℕ ∪ { ∞ }. Ist der Graph G zusammenhängend, so sind alle Abstände endlich, sodass d : E × E → ℕ. Weiter gilt für alle Ecken a ∈ E:
N(a) = { b ∈ E | d(a, b) = 1 }, [ a ] = { b ∈ E | d(a, b) < ∞ }.
Die Nachbarecken einer Ecke sind also genau die Ecken mit Abstand 1 von der Ecke, und die Zusammenhangskomponente einer Ecke besteht genau aus den Ecken mit endlichem Abstand von der Ecke.
Bemerkung
(1) | Statt „Kantenzug“ können wir in der Definition des Abstands d(a, b) auch „Weg“ einsetzen. Denn ein kürzester Kantenzug von a nach b ist automatisch ein Weg. |
(2) | Da ein kürzester Kantenzug zwischen zwei Ecken in der Regel nicht eindeutig bestimmt ist, wäre es ungenau, von der Länge des kürzesten Kantenzugs statt der Länge eines kürzesten Kantenzugs zu sprechen. Ist etwa G = (E, K) mit E = { 1, 2, 3, 4 } und K = { 12, 13, 24, 34 } so sind 1, 2, 4 und 1, 3, 4 zwei verschiedene kürzeste Kantenzüge von 1 nach 4 in G. Es gilt d(1, 4) = 2. |
Beispiel
Wir betrachten den folgenden Graphen mit drei Zusammenhangskomponenten { 1, …, 9 }, { 10, 11 } und { 12 }:
Die Abstände d(a, b) zwischen den Ecken lassen sich aufgrund der einfachen Struktur des Graphen ablesen. Wir können sie in Form einer Tabelle angeben. Wegen d(a, b) = d(b, a) genügt es, die Tabelle halb zu füllen.
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
1 | 0 | 1 | 2 | 4 | 2 | 3 | 3 | 1 | 3 | ∞ | ∞ | ∞ |
2 | - | 0 | 1 | 3 | 1 | 2 | 2 | 2 | 2 | ∞ | ∞ | ∞ |
3 | - | - | 0 | 2 | 2 | 2 | 1 | 3 | 2 | ∞ | ∞ | ∞ |
4 | - | - | - | 0 | 3 | 2 | 1 | 4 | 2 | ∞ | ∞ | ∞ |
5 | - | - | - | - | 0 | 1 | 2 | 1 | 1 | ∞ | ∞ | ∞ |
6 | - | - | - | - | - | 0 | 1 | 2 | 2 | ∞ | ∞ | ∞ |
7 | - | - | - | - | - | - | 0 | 3 | 1 | ∞ | ∞ | ∞ |
8 | - | - | - | - | - | - | - | 0 | 2 | ∞ | ∞ | ∞ |
9 | - | - | - | - | - | - | - | - | 0 | ∞ | ∞ | ∞ |
10 | - | - | - | - | - | - | - | - | - | 0 | 1 | ∞ |
11 | - | - | - | - | - | - | - | - | - | - | 0 | ∞ |
12 | - | - | - | - | - | - | - | - | - | - | - | 0 |
Die Abstandsfunktion lässt sich in effektiver Weise algorithmisch berechnen. Entsprechende Algorithmen werden wir später kennenlernen.
Die drei grundlegenden Eigenschaften der Abstandsfunktion sind (die zweite haben wir im obigen Beispiel schon verwendet):
Satz (Eigenschaften des Abstands)
Sei G = (E, K) ein Graph. Dann gilt für alle a, b, c ∈ E:
(1) | d(a, b) = 0 genau dann, wenn a = b(Nullbedingung), |
(2) | d(a, b) = d(b, a),(Symmetrie) |
(3) | d(a, c) ≤ d(a, b) + d(b, c).(Dreiecksungleichung) |
Der Beweis sei dem Leser zur Übung überlassen.
In der Dreiecksungleichung behandeln wir den symbolischen Wert ∞ in der üblichen Weise, d. h. es gilt
n + ∞ = ∞ + n = ∞ + ∞ = ∞ für alle n ≥ 0.