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}
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.
Schreiben Sie uns!