2. gw_max_flow.exe の使用法

• アルゴリズムの名称：Maximum Flow
• 内容：ネットワークにて、その系の流量を最大にする経路を求める

【概要】

ネットワークを構成するグラフにおいて、その系の流量を最大にする経路を求める

1. gw_max_flow.exe は、２つのノード間の流量を最大にするようなアルゴリズムを示すデモです
   gw_max_flow.exe を起動すると、操作ガイドが現れるので [close] を押す
   
   
2. 画面の左端で１回クリックし、次に右端で、２回目のクリックをする。
   
   画面の左側にノード [S] が生成されて、スタート・ノードとなる。
   画面の右側にノード [T] が生成されて、ターゲット・ノードとなる。
   
   
3. ノード [S] をクリックし、右上方に少し移動して、再度クリックすると、ノード [S] からエッジが伸びて、その先に新しいノードが生成される。
   
   新しいノード上で右クリックし、"label" を選び、"N1" を入力する。
   
   　　　　 ① [S] -->[N1]
   
   
4. 上記と同様にして、以下の４つのノード ([N2]～[N5]) を生成する。
   
   　　　　 ② [N1]-->[N2]
   　　　　 ③ [S] -->[N3]
   　　　　 ④ [N3]-->[N4]
   　　　　 ⑤ [N4]-->[N5]
   
   
5. ノード [N3] をクリックし、そのままノード [N2] に移動して、その上でクリックすると、[N3]-->[N2] のエッジが生成される。
   
   　　　　 ⑥ [N3]-->[N2]
   
   同様にして、以下の３つのエッジ ([N2]-->[N4], [N2]-->[T], [N5]-->[T]) を生成する。
   
   　　　　 ⑦ [N2]-->[N4]
   　　　　 ⑧ [N2]-->[T]
   　　　　 ⑨ [N5]-->[T]
   
   
6. 最終的に出来上がったグラフがノード [S] からノード [T] に至るネットワークでの最大流量を示している。例えば、[N1]-->[N2] のエッジにそった数字 5/7 は以下のような意味を持つ。
   
   　　　　　　 5 : そのエッジを流れる現在の流量
   　　　　　　 7 : そのエッジが持つキャパシティ(流せる最大流量)
   
   

• このアプリは、例えば、中東の産油国の石油輸送パイプライン・ネットワークに対応させることができます。
  スタート・ノード [S] が、石油を産出する井戸で、ターゲット・ノード [T] が、石油をタンカーに積出す港に対応します。
  各パイプライン (エッジ) の数字の分母は、そのパイプに流すことが出来る単位時間当たりの最大流量です。
  このネットワークにおいて、最大流量を得るために個々のパイプにどれだけの流量を割当てると良いかの解を求めることが出来ます。