組合せとグラフの理論（塩田）第8回 (1)　重み付きグラフ
戻る / 次へ

重み付きグラフ

　今日扱うグラフは全て連結で、かつ、次に定義する「重み付きグラフ」であるとします。
Def.1　全ての辺 $e$ に「重み」と呼ばれる数 $w(e)$ が設定されているグラフを 「重み付きグラフ」と呼ぶ。
Ex.2　重みは辺の横に書き入れます。
この重み付きグラフは、隣接行列では
$\left( \begin{array}{cccc} 0 & 1 & 0 & 2 \\ 1 & 0 & 3 & 4 \\ 0 & 3 & 0 & 5 \\ 2 & 4 & 5 & 0 \\ \end{array} \right)$
のように表します。 （多重辺ありの場合と紛らわしいようですが、 普通、重み付きグラフと多重辺は同時には使いませんので、状況で判断します。）
※　例えば地図を表すグラフであれば、重みとして
  • 距離
  • 所要時間
  • 高速料金
などを設定することができて、 「最短距離でたどり着けるルート」、 「最短時間でたどり着けるルート」、 「一番安い高速料金でたどり着けるルート」 ということが考えられるようになります。

戻る / 次へ