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

Einzelnachweise

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

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