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