Kantengewichte

Definition (gewichteter Graph, Gewichtsfunktion)

Ein (nichtnegativ) gewichteter Graph ist ein Graph G = (E, K) zusammen mit einer Gewichts- oder Längenfunktion w : K → ℝ⁺₀, wobei ℝ⁺₀ = { x  ∈  ℝ | x ≥ 0 }. Für alle k  ∈  K heißt w(k) das Gewicht oder die Länge von k unter w. Wir notieren einen gewichteten Graphen auch als Tripel (G, K, w).

In einem Ecken-Kanten-Diagramm schreiben wir die Gewichte an die Kanten:

Ein gewichteter Graph. Es gilt zum Beispiel w(36) = w(63) = 2

Es ist oft nützlich, w(ab) = ∞ für alle a, b  ∈  E mit ab  ∉  K zu setzen, d. h. nicht vorhandene Kanten haben das symbolische Gewicht ∞. Ist eine Eckenaufzählung e₁, …, e_n festgelegt, so ist die Gewichtsfunktion w durch die Gewichts-Matrix A mit den Einträgen A(i, j) = w(e_ie_j) für alle i, j  ∈  { 1, …, n } bestimmt. Die Gewichts-Matrix des obigen Graphen lautet zum Beispiel:

A = $( \begin{matrix} \infty & 1 & \infty & 2 & 3 & \infty \\ 1 & \infty & 4 & \infty & \infty & \infty \\ \infty & 4 & \infty & 5 & 4 & 2 \\ 2 & \infty & 5 & \infty & 8 & 9 \\ 3 & \infty & 4 & 8 & \infty & \infty \\ \infty & \infty & 2 & 9 & \infty & \infty \end{matrix} )$

Lassen wir Schlingen zu, so können auch reelle Zahlen (einschließlich der 0) auf der Hauptdiagonalen stehen. Setzen wir alle ∞-Einträge gleich 0 und alle anderen Einträge gleich 1, so ergibt sich die Adjazenz-Matrix von G.

Für einen gewichteten Graphen sind Begriffe wie Kantenzug, Weg, Kreis, erreichbar, Zusammenhangskomponente, zusammenhängend und viele weitere genau wie früher erklärt. Die Gewichtsfunktion spielt für diese Begriffe keine Rolle. Mit Hilfe einer solchen Funktion können wir aber eine gewichtete Länge für Kantenzüge und damit einen gewichteten Abstand einführen:

Definition (Gewicht, gewichtete Länge eines Kantenzugs)

Sei G = (E, K, w) ein gewichteter Graph, und sei Z = a₀, …, a_n ein Kantenzug in G. Dann setzen wir

ℓ_w(Z) = w(a₀a₁) + … + w(a_n − 1a_n).

Die reelle Zahl ℓ_w(Z) heißt das Gewicht oder die gewichtete Länge von Z.

Definition (gewichteter Abstand)

Sei G = (E, K, w) ein gewichteter Graph. Für alle a, b  ∈  E mit a ∼ b setzen wir

d_w(a, b) =

„das minimale Gewicht eines Kantenzugs von a nach b in G“.

Für a, b  ∈  E mit non(a ∼ b) setzen wir d_w(a, b) = ∞.

Wir nennen d_w(a, b) den gewichteten Abstand der Ecken a und b in G.

Für alle voneinander erreichbaren Ecken a und b gilt also

d_w(a, b) = min({ ℓ_w(Z) | Z ist ein Kantenzug von a nach b in G }.

Ein Kantenzug zwischen zwei Ecken mit minimalem Gewicht ist wieder automatisch ein Weg. Gilt w(k) = 1 für alle Kanten k, so stimmen die neuen Begriffe mit den alten überein. Jeden Graphen (E, K) können wir als gewichteten Graphen (E, K, w) mit einer konstanten Gewichtsfunktion w auffassen, die jeder Kante das Gewicht 1 zuweist.

Beispiel

Im obigen Graphen hat der Kantenzug Z = 1, 2, 3, 6, 3 das Gewicht

ℓ_w(Z) = 1 + 4 + 2 + 2 = 9.

Für die Ecken 1 und 6 gilt

d(1, 6) = 2, d_w(1, 6) = 7.

Der Weg 1, 4, 6 ist ein kürzester Weg von 1 nach 6, aber kein leichtester Weg von 1 nach 6. Die Länge dieses Weges ist 2, sein Gewicht 11. Dagegen ist 1, 2, 3, 6 ein Weg von 1 nach 6 mit minimalem Gewicht. Seine ungewichtete Länge ist 3, seine gewichtete Länge 7.

Eine gewichtete Abstandsfunktion erfüllt die drei grundlegenden Eigenschaften eines Abstands, wobei wir die Nullbedingung abschwächen müssen, wenn die Null als Gewicht einer Kante auftaucht. Denn für Ecken a, b mit w(ab) = 0 ist d_w(a, b) = 0, aber a ≠ b. Wir versammeln:

Satz (Eigenschaften des gewichteten Abstands)

Sei G = (E, K, w) ein gewichteter Graph. Dann gilt für alle a, b, c  ∈  E:

(1)	a = b impliziert d_w(a, b) = 0(schwache Nullbedingung)

(2)	d_w(a, b) = d_w(b, a) (Symmetrie)

(3)	d_w(a, c) ≤ d_w(a, b) + d_w(b, c)(Dreiecksungleichung)

(4)	Ist w positiv, so gilt „genau dann, wenn“ in (1).

(5)	d(a, b) = ∞ genau dann, wenn d_w(a, b) = ∞

(6)	Gilt w(k) ≥ 1 für alle Kanten k, so ist d_w(a, b) ≥ d(a, b).

Klar, aber von Bedeutung ist:

Satz (Optimalität von Teilstücken)

Sei G = (E, K, w) ein gewichteter Graph, und sei Z = a₀, …, a_n ein Weg von a₀ nach a_n in G mit minimalem Gewicht. Dann gilt für alle i < j ≤ n:

a_i, …, a_j ist ein Weg von a_i nach a_j mit minimalem Gewicht in G.

Beweis

Andernfalls könnten wir das Gewicht von Z durch Verändern eines Teilstücks noch verbessern.

Bevor wir uns der Frage der Berechnung gewichteter Abstände zuwenden, noch einige Bemerkungen zum Wertebereich unserer Gewichtsfunktionen.

Bemerkung

(1)

Sind alle Gewichte rationale Zahlen, so können wir sie mit ihrem Hauptnenner m skalieren. Dadurch werden alle Gewichte positive natürliche Zahlen, und die neue gewichtete Abstandsfunktion ist das m-fache der alten. In den folgenden Beispielen sind die Gewichte der Einfachheit und Übersichtlichkeit halber durchweg natürliche Zahlen.

(2)

Auch negative Kantengewichte sind sinnvoll, aber im Hinblick auf Abstandsmessungen problematisch, da wir eine Kante ab mit einem negativen Gewicht beliebig oft in unterschiedlichen Richtungen durchlaufen können, um das Gewicht eines Kantenzugs von a nach b immer weiter zu verringern. Man untersucht deswegen oft nur gerichtete Graphen mit Gewichten in ℝ. Aber auch mit gerichteten Kanten müssen Kreise mit negativem Gewicht beachtet werden, um ein mehrfaches Durchlaufen derartiger Kreise zu vermeiden. Im Zentrum stehen dann insgesamt gerichtete kreisfreie Graphen mit einer Gewichtsfunktion w : K → ℝ, sog. DAGs für „directed acyclic graphs“. Wir verweisen den Leser hierzu auf die Literatur.