Gewicht (Graphentheorie)
Als Gewicht bezeichnet man in der Graphentheorie eine reelle Zahl, die einem Knoten (als Knotengewicht) oder einer Kante (als Kantengewicht) zugeordnet wird. Man erhält dann einen knoten- bzw. kantengewichteten Graph. So kann beispielsweise ein Straßennetz als Graph modelliert werden, bei dem Entfernungen oder Fahrzeiten den Kantengewichten entsprechen. Mit Hilfe dieses Modells kann dann beispielsweise ein kürzester oder längster Pfad berechnet werden.
Knotengewichteter Graph
Als knotengewichteten Graph bezeichnet man in der Graphentheorie einen Graphen, dessen Knoten ein Knotengewicht in Form einer reellen Zahl zugeordnet wird. Ein Graph,
dessen Kanten gewichtet sind, heißt kantengewichteter Graph.
Zu einem knotengewichteten Graphen gehört also neben der Angabe der Knoten- und Kantenmenge auch die Angabe einer Funktion, die von den Knoten in die
Menge der reellen Zahlen abbildet.
© biancahoegel.de
Datum der letzten Änderung: Jena, den: 10.02. 2019