Lexikon der Mathematik: bewerteter Graph
Bezeichnung innerhalb der Graphentheorie für einen Graphen G zusammen mit einer Abbildung ϱ : K(G) → ℝ.
Für k ∈ K(G) nennt man ϱ(k) Bewertung oder Länge der Kante k. Ist H ein Teilgraph von G, so wird durch
\begin{eqnarray}\varrho (H)=\displaystyle \sum _{k\in K(H)}\varrho (k)\end{eqnarray}
die Bewertung oder Länge von H definiert. Dieser Längenbegriff stimmt mit dem in nicht bewerteten Graphen überein, wenn man jeder Kante die Länge Eins zuordnet.
Ein Weg zwischen zwei Ecken x und y, dessen Länge unter allen Wegen von x nach y minimal ist, heißt kürzester Weg von x nach y. Ist C ein Kreis mit ϱ(C) < 0, so spricht man von einem Kreis negativer Länge. Analog lassen sich natürlich auch bewertete Digraphen definieren.
In den Anwendungen spielen die bewerteten Graphen und Digraphen eine wichtige Rolle. Die Längen von Kanten können dabei Entfernungen, Zeiten, Kosten, Gewinne und vieles andere bedeuten.
Copyright Springer Verlag GmbH Deutschland 2017
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.