ラベル付き有向グラフ

1. 有向グラフ 有向グラフは,ここでは$G$で表しますが,コンピュータや,ネットワークにもよく使われ ます。有向グラフ$G$は

   (1)

   節点の集合$P$

   (2)

   $P$の点の順序対 $(a,b)(a,bはPの点)$の集合$V$

   からなります。
   

   $a \ne b$のとき $(a,b) \ne (b,a)$です。また
   

   $$(a,b)=(c,d)　\Leftrightarrow (　a=c　かつ　b=d　）$$
   
   

   $V$は$P$の自乗直積 $P \times P= \{(a,b)\vert a,bはPの要素 \}$ の部分集合です。　すなわち,
   

   $$V \subseteq P \times P$$
   
   

   順序対$(a,b)$は向きのついた枝,あるいは弧と呼ばれ,
   

   
   (図5.1)
   

   のように表すことができます。$a$は始点,$b$は終点と呼ばれます。 このような枝のまたは弧の図をつなぎ合わせば,有向グラフ $G=(P,V)$を平面図で表すことができます。

   
   (図5.2)

   $$\begin{eqnarray*} &&P=\{ a,b,c,d,e,f \}\\ &&V=\{(a,b),(a,c),(b,d),(b,e),(c,e),(d,f),(e,f) \} \end{eqnarray*}$$
   
   
   
   
   
   

2. ラベル

   有向グラフ$G=(P,V)$の弧には,長さや,所要時間などのデータでラベル付けされているとき $G$をラベル付き有向グラフといいます。

   
   (図5.3)

3. 路

   節点の多重対 $(p_1,p_2,\cdots,p_k)$で,各 $(p_1,p_2),(p_2,p_3),\cdots,(p_{k-1},p_k)$が$V$ の元,すなわち弧であるものを 路といいます。
   

   上の図では, $(a,b,e,f),(a,c,e),(b,d,f)$などが路です。

4. 最短路問題

   $G$をラベル付き有向グラフとします。ただし,
   

   
   (図5.4)
   

   の$(b,e,f,d,b)$のように「閉じた路」は含まないものとします。
   

   さて,簡単にするため、集合$P$が$n$個の節点からなっているとして

   $P=\{1,2,\cdots,n\}$とし,夫々の弧に付けられている,ラベルはその弧の長さを 表すものとしておきます。
   

   
   (図5.5)
   

   弧をつなぎ合わせて作られる路の長さは,それを構成している弧の長さの和で 表します。例えば(図5)で路$(1,4,5,6)$の長さは,$20+20+30$で$70$です。
   

   節点1から出発して,節点nへ行くための長さ最小の路をどう求めるかという問題を考えます。(図5.5)の例では,路(1,2,5,6)が解で,長さ$50$です。
   

   $P$の点の数が少なければ,路を全て調べてみるのも一つの方法ですが,数が多くなると 実用的ではありません。