Kantengewichteter Graph

ungerichteter Graph in dem jeder Kante eine reelle Zahl als Kantengewicht zugeordnet ist
(Weitergeleitet von Gewichteter 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.

Gewichtsfunktionen

Bearbeiten

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

 ,

die jeder Kante eine reelle Zahl als Gewicht zuordnet. Das Kantengewicht einer Kante   wird dann mit   oder   bezeichnet.

Metrischer Graph

Bearbeiten

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

 

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

Anwendungen

Bearbeiten

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   beschrieben, welches neben dem Graph die gewünschte Gewichtsfunktion beinhaltet.

Siehe auch

Bearbeiten

Einzelnachweise

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