imported>Aka: Malzeichen, Abkürzung korrigiert, Halbgeviertstrich, typografische Anführungszeichen, Kleinkram

2026-01-31T12:05:31Z

Malzeichen, Abkürzung korrigiert, Halbgeviertstrich, typografische Anführungszeichen, Kleinkram

Neue Seite

[[Datei:CPT-Graphs-directed-weighted-ex1.svg|mini|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.]]
Ein '''kantengewichteter Graph''', kurz '''gewichteter Graph''', ist in der [[Graphentheorie]] ein [[Graph (Graphentheorie)|Graph]], in dem jeder [[Kante (Graphentheorie)|Kante]] eine [[reelle Zahl]] als '''[[Gewicht (Graphentheorie)|Kantengewicht]]''' zugeordnet ist. Kantengewichtete Graphen können [[Gerichteter Graph|gerichtet]] oder ungerichtet sein. Ein Graph, dessen [[Knoten (Graphentheorie)|Knoten]] gewichtet sind, heißt [[knotengewichteter Graph]].

== Definition – Kantengewichter Graph ==
Ein kantengewichteter [[Graph (Graphentheorie)|Graph]] <math>G</math> ist ein Tripel <math>(V, E, w)</math>, wobei <math>V</math> eine [[Mengenlehre|Menge]] von ''Knoten'' ({{enS|vertex/vertices}}), <math>E</math> eine Menge von ''Kanten'' ({{enS|edge/edges}}) und einer Kantengewichtsfunktion
:<math>
\begin{array}{rrcl}
w: & E & \rightarrow & \mathbb{R} \\
& e & \mapsto & w\left( e \right)
\end{array}

</math>
eine Abbildung ist, die jeder Kante <math>e\in E</math> ein Kantengewicht ({{enS|weight}}) <math> w(e)\in \mathbb{R} </math> zuordnet.

=== Gewichtsfunktionen ===
Kantengewichte sind im Allgemeinen durch eine '''Kantengewichtsfunktion''' gegeben. Eine solche Gewichtsfunktion kann man allerdings nicht nur als eine Abbildung der Form <math>w \colon E \to \mathbb{R}</math> angeben, sondern auch das Kreuzprodukt <math>V\times V</math> der Knotenmenge <math>V</math> als Definitionsbereich verwenden:
:<math>
\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}

</math>
<math>w(v_1,v_2)</math> gibt dabei an, wie stark die gerichtete Verbindung zwischen den Knoten <math>v_1</math> und <math>v_2</math>
mit einer [[reelle Zahl|reellen Zahl]] gewichtet ist. Das Kantengewicht <math>w(v_1,v_2)=0</math> einer Kante kann dabei so interpretiert werden, dass die Verbindung zwischen den Knoten <math>v_1</math> und <math>v_2</math> nicht existiert.

=== Bemerkung – Symmetrie der Kantengewichtsfunktion ===
Die Kantengewichtsfunktion muss nicht symmetrisch sein, d. h. es kann Knotenpaare <math>(v_1,v_2)\in V\times V</math> geben, bei dem <math>w(v_1,v_2)\not=w(v_2,v_1)</math> gilt.

=== Beispiel – Neuronale Netze ===
[[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 [[Nervenzelle]]n entsprechen in der [[Neurophysiologie]] einer [[Synapse]]. Positive Kantengewichte <math>w(e) > 0 </math> sind [[exzitatorisch]]e Verbindungen und negative Kantengewichte <math>w(e) < 0 </math> nennt hemmende ([[inhibitorisch]]e) neuronale Verbindungen.

== Metrischer Graph ==
Ein [[Vollständiger Graph|vollständiger]] kantengewichteter Graph heißt '''metrisch''', falls für alle [[Knoten (Graphentheorie)|Knoten]] <math>a,b,c</math> des Graphen

:<math>d({a,c}) \leq d({a,b}) + d({b,c})</math>

gilt. Das heißt, der [[Weg (Graphentheorie)|Weg]] von <math>a</math> über <math>b</math> nach <math>c</math> darf nicht kostengünstiger sein als der direkte Weg von <math>a</math> nach <math>c</math>.<ref>{{Literatur |Autor=Hartmut Noltemeier |Titel=Graphentheoretische Konzepte und Algorithmen |Auflage=3 |Verlag=Vieweg+Teubner Verlag |Ort=Wiesbaden |Datum=2012 |ISBN=978-3-8348-1849-2 |Seiten=74 f.}}</ref> Ein Beispiel für metrische Graphen sind [[Distanzgraph]]en.

== Anwendungen ==
Für viele graphentheoretische Probleme benötigt man zusätzliche Parameter, zum Beispiel eine Kostenfunktion für die Bestimmung [[Kürzester Pfad|kürzester Pfade]] oder eine Kapazitätsfunktion zur
Bestimmung [[Flüsse und Schnitte in Netzwerken|maximaler Flüsse]]. Eine Probleminstanz wird in einem solchen Fall oft durch ein [[Tupel]] der Form <math>(G,d)</math> beschrieben, welches neben dem Graph die gewünschte Gewichtsfunktion beinhaltet.

== Siehe auch ==
* [[Magischer Graph]]
* [[Graph (Graphentheorie)]]

== Einzelnachweise ==
<references />

[[Kategorie:Graphenklasse]]

Kantengewichteter Graph - Versionsgeschichte

imported>Aka: Malzeichen, Abkürzung korrigiert, Halbgeviertstrich, typografische Anführungszeichen, Kleinkram