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.

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

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

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

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

${\displaystyle {\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}}}$

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

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

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 ${\displaystyle w(e)>0}$ sind exzitatorische Verbindungen und negative Kantengewichte ${\displaystyle w(e)<0}$ nennt hemmende (inhibitorische) neuronale Verbindungen.

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

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

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

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 ${\displaystyle (G,d)}$ beschrieben, welches neben dem Graph die gewünschte Gewichtsfunktion beinhaltet.

• Magischer Graph
• Graph (Graphentheorie)

1. ↑ Hartmut Noltemeier: Graphentheoretische Konzepte und Algorithmen. 3. Auflage. Vieweg+Teubner Verlag, Wiesbaden 2012, ISBN 978-3-8348-1849-2, S. 74 f.