Kantengewichteter Graph

Ein kantengewichteter Graph, kurz gewichteter Graph, ist in der Graphentheorie ein Graph, in dem jeder Kante eine reelle Zahl als Kantengewicht zugeordnet ist. Kantengewichtete Graphen können gerichtet oder ungerichtet sein. Ein Graph, dessen Knoten gewichtet sind, heißt knotengewichteter Graph.

Gewichteter Graph – z. B. repräsentieren die Knoten Wörter und das Kantengewicht zwischen B und A beschreibt, dass in einem Beispieldatensatz 10× das Wort „A“ nach dem Wort „B“ gefolgt ist und die umgekehrte Wortreihenfolge nicht aufgetreten ist.

Definition – Kantengewichter Graph

Ein kantengewichteter Graph $G$ ist ein Tripel $(V,E,w)$ , wobei $V$ eine Menge von Knoten (englisch vertex/vertices), $E$ eine Menge von Kanten (englisch edge/edges) und einer Kantengewichtsfunktion

{\begin{array}{rrcl}w:&E&\rightarrow &\mathbb {R} \\&e&\mapsto &w\left(e\right)\end{array}}

eine Abbildung ist, die jeder Kante $e\in E$ ein Kantengewicht (englisch weight) $w(e)\in \mathbb {R}$ zuordnet.

Gewichtsfunktionen

Kantengewichte sind im Allgemeinen durch eine Kantengewichtsfunktion gegeben. Eine solche Gewichtsfunktion kann man allerdings nicht nur als eine Abbildung der Form $w\colon E\to \mathbb {R}$ angeben, sondern auch das Kreuzprodukt $V\times V$ der Knotenmenge $V$ als Definitionsbereich verwenden:

{\begin{array}{rrcl}w:&V\times V&\rightarrow &\mathbb {R} \\&\left(v_{1},v_{2}\right)&\mapsto &w\left(v_{1},v_{2}\right).\end{array}}

$w(v_{1},v_{2})$ gibt dabei an, wie stark die gerichtete Verbindung zwischen den Knoten $v_{1}$ und $v_{2}$ mit einer reellen Zahl gewichtet ist. Das Kantengewicht $w(v_{1},v_{2})=0$ einer Kante kann dabei so interpretiert werden, dass die Verbindung zwischen den Knoten $v_{1}$ und $v_{2}$ nicht existiert.

Bemerkung – Symmetrie der Kantengewichtsfunktion

Die Kantengewichtsfunktion muss nicht symmetrisch sein, d. h. es kann Knotenpaare $(v_{1},v_{2})\in V\times V$ geben, bei dem $w(v_{1},v_{2})\not =w(v_{2},v_{1})$ gilt.

Beispiel – Neuronale Netze

Künstliche Neuronale Netze (ANN) (Artificial Neural Network) können einen gerichteten gewichteten Graph verwenden, um die Netzstruktur zu speichern. Knoten sind dabei die Nervenzellen (Neuronen) und Verbindungen/Kanten zwischen den Nervenzellen entsprechen in der Neurophysiologie einer Synapse. Positive Kantengewichte $w(e)>0$ sind exzitatorische Verbindungen und negative Kantengewichte $w(e)<0$ nennt hemmende (inhibitorische) neuronale Verbindungen.

Metrischer Graph

Ein vollständiger kantengewichteter Graph heißt metrisch, falls für alle Knoten $a,b,c$ des Graphen

d({a,c})\leq d({a,b})+d({b,c})

gilt. Das heißt, der Weg von $a$ über $b$ nach $c$ darf nicht kostengünstiger sein als der direkte Weg von $a$ nach $c$ .^[1] Ein Beispiel für metrische Graphen sind Distanzgraphen.

Anwendungen

Für viele graphentheoretische Probleme benötigt man zusätzliche Parameter, zum Beispiel eine Kostenfunktion für die Bestimmung kürzester Pfade oder eine Kapazitätsfunktion zur Bestimmung maximaler Flüsse. Eine Probleminstanz wird in einem solchen Fall oft durch ein Tupel der Form $(G,d)$ beschrieben, welches neben dem Graph die gewünschte Gewichtsfunktion beinhaltet.