アルゴリズムクイックリファレンス 第2版

6.1

 グラフ

■

151

6.1

 グラフ

グラフ

G

＝

(V, E)

は、節点集合

V

と各節点対上の辺集合

E

によって定義される。

普通のグラフには、次の

3

種類がある。

無向、重みなしグラフ（Undirected,unweightedgraph）

関係の方向を気にせず節点対

(u, v)

の関係をモデル化する。対称的な情

報を扱うのに役立つ。例えば、社会的ネットワークをモデル化したグラ

フでは、アリスがボブの友達なら、ボブはアリスの友達だ。

有向グラフ（Directedgraph）

節点対

(u, v)

の関係が、

(v, u)

の関係とは異なるモデル。ただし

(v, u)

が

存在するかどうかは問わない。例えば、運転指示を与えるプログラムは、

交通違反をしないように一方通行の街路の情報を格納しなければならな

い。

重み付きグラフ（Weightedgraph）

節点対

(u, v)

の関係に重み（

weight

）と呼ばれる数値が伴うモデル。値と

し

て数でないものが使われても構わない。例えば、町

A

と

B

との間の辺

は、分単位の推定運転時間、あるいは町を結ぶ通り、または高速道路の

名前を格納している。

最も高度に構造化されたグラフである有向重み付きグラフは、節点の非空集合

{v

0

, v

1

,

…

, v

n

−

1

}

、互いに異なる節点間の有向辺（すべての対で各方向に高々

1

つの

辺がある）の集合、および各辺の正の重みを定義する。アプリケーションによっては、

この重みが正でなくても構わない（例えば、負の重みは利益ではなく損失を意味す

る）が、その場合には、意 ...