4. gw_min_cut.exe の使用法

• アルゴリズムの名称：Minimum Cut
• 内容：２つの部分グラフに分ける組合せで、カットするコストを最小にする組合せを求める

【概要】

２つの部分グラフに分ける組合せで、カットするコストを最小にする組合せを求める

1. gw_min_cut.exe を起動する。
   
   下図に示すような「7 nodes, 8 edges」のグラフを作成する。
   
   各エッジに添えられている数字は Weight です。エッジに付属のスライダーを移動させて、Weight の値を変更できます。
   　　
   　　 [0] ～ [6] の７個のノードを作成する。
   　　 次の８個のエッジを作成する。
   
   　　　　　 ・[0] --> [1], Weight= 39
   　　　　　 ・[1] --> [2], Weight= 13
   　　　　　 ・[2] --> [3], Weight= 29
   　　　　　 ・[3] --> [4], Weight= 25
   　　　　　 ・[4] --> [6], Weight= 45
   　　　　　 ・[6] --> [5], Weight= 12
   　　　　　 ・[5] --> [0], Weight= 47
   　　　　　 ・[5] --> [2], Weight= 19
   
   
   
   
2. 生成されたグラフにおいて、赤色の２つのエッジを削除すれば、２つのサブ・グラフが得られる。
   　　　　・[0], [1], [2], [3], [5]
   　　　　・[4], [6]
   
   ２つのサブ・グラフを得るために削除したエッジの Weight の合計は 37 です。
   ２つのサブ・グラフを得るために削除できるエッジの組合せは何通りかありますが、上記の組合せ ([3]-->[4], [6]-->[5] を削除) のコスト (= 37) が最小です。
   
   
3. 次に、[5]-->[2] のエッジの Weight を 19 --> 11 に変更すると、2 つのサブ・グラフを得るために削除するエッジは、次の３つになり、Weight の合計は 36 となる。
   
   　　　　・[1] --> [2], Weight= 13
   　　　　・[6] --> [5], Weight= 12
   　　　　・[5] --> [2], Weight= 19
   
   ・もし、前回と同様の組合せ ([3]-->[4], [6]-->[5] を削除) を選んだ場合は
   
   　　　　 ・[3] --> [4], Weight= 25
   　　　　 ・[6] --> [5], Weight= 12
   
   その Weight の合計は 37 となるので、今回の組合せによるもの (= 36) より大きくなる。
   
   
   
   
4. 次に、[5]-->[0] のエッジの Weight を 47 --> 22 に変更すると、２つのサブ・グラフを得るために削除するエッジは、次ぎの２つになり、Weight の合計は 35 となる。
   
   　　　　　 ・[1] --> [2], Weight= 13
   　　　　　 ・[5] --> [0], Weight= 22