imported>Georg Hügler am 19. November 2022 um 18:43 Uhr

2022-11-19T18:43:11Z

Neue Seite

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]].

== Gewichtsfunktionen ==
Kantengewichte sind im Allgemeinen durch eine '''Kantengewichtsfunktion''' gegeben. Eine solche Gewichtsfunktion ist eine Abbildung der Form

:<math>d \colon E \to \mathbb{R}</math>,

die jeder Kante eine [[reelle Zahl]] als Gewicht zuordnet. Das Kantengewicht einer Kante <math>e \in E</math> wird dann mit <math>d(e)</math> oder <math>d_e</math> bezeichnet.

== 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]]

== Einzelnachweise ==
<references />

[[Kategorie:Graphenklasse]]

Kantengewichteter Graph - Versionsgeschichte

imported>Georg Hügler am 19. November 2022 um 18:43 Uhr