Kantengewichte

Kantengewichte bezeichnen in der Graphentheorie numerische Werte, die den Kanten eines Graphen zugeordnet werden. Sie dienen dazu, Größen wie Distanz, Kosten, Kapazität oder Wahrscheinlichkeit abzubilden. Formal wird ein gewichteter Graph G = (V, E, w) durch eine Gewichtsfunktion w: E → R beschrieben; bei gerichteten Graphen gelten gerichtete Kanten als Teilmenge A ⊆ V × V mit Gewichten w(u, v), bei ungerichteten Graphen gilt oft w(u, v) = w(v, u).

Die Länge eines Pfades P = (e1, e2, ..., ek) ist die Summe der Gewichte der auf dem Pfad liegenden Kanten: L(P) = Σ w(ei). Das kürzeste Pfadproblem zielt darauf ab, einen Pfad zwischen zwei Knoten mit minimaler Länge zu finden. In ungerichteten Graphen entspricht dies ebenfalls der Pfadlänge, wobei Start- und Zielknoten festgelegt sind.

Gewichte können positiv, null oder negativ sein. Positive Gewichte finden in vielen Anwendungen Verwendung, negative Gewichte sind jedoch problematisch, da sie negative Zyklen zulassen können, die die Berechnung kürzester Wege erschweren. Zur Bestimmung von kürzesten Wegen existieren verschiedene Algorithmen: Dijkstra-Algorithmus (benötigt nichtnegative Gewichte), Bellman-Ford (kann negative Gewichte behandeln) und Floyd-Warshall (alle Paare kürzeste Wege). Für Minimalkosten- oder Kapazitätsprobleme kommen auch Algorithmen wie Prim und Kruskal zum Einsatz, die Gewichtungen nutzen, um minimale Spannbäume zu konstruieren.

Typische Anwendungen finden sich in Transport- und Logistiknetzwerken, Telekommunikation, Energieverteilungsnetzen sowie in der Analyse sozialer Netzwerke. Gewichte können ganze oder reelle Zahlen sein; in manchen Kontexten werden auch mehrkriteriale Gewichte verwendet oder Gewichte normiert.