5. gw_minimum_spanning_tree.exe の使用法

• アルゴリズムの名称：Minimum Spanning Trees
• 内容：グラフの全てのノードを含む部分グラフで、コストが最小の組合せを求める

【概要】

グラフの全てのノードが繋がるような部分グラフで、コストが最小の組合せを求める

1. gw_minimum_spanning_tree.exe は、全てのノードが孤立しないための最小限のエッジを選び出すようなアルゴリズムを示すデモです。
   
   gw_minimum_spanning_tree.exe を起動すると、操作ガイドが現れるので [close] を押す。
   
   
2. メニューの "Graph-> Create-> random planar" を選ぶ
   
   ダイアログが現れるので、以下の設定をする
   
   　　　　　　　 nodes = 10
   　　　　　　　 edges = 22
   　　　　　　　 layout= orthogonal
   
   
   
   
3. 自動生成されたグラフで、太い青色のエッジが、「全てのノードが繋がるためのコスト最小限のエッジ」を示している。
   
   
   
4. コストが最小であると言うことの一例として、２つの部分グラフの繋がりを調べる
   
   　　　　Group A: ノード[1], [2], [3], [4], [7], [9] ....... ６個のノード
   　　　　Group B: ノード[0], [5], [6], [8] ....... ４個のノード
   　
   Group A と Group B とを繋ぐエッジは次の６つです
   
   　　　　1) [0]-->[3], Weight= 3
   　　　　2) [0]-->[1], Weight= 7
   　　　　3) [0]-->[2], Weight= 7
   　　　　4) [6]-->[2], Weight= 7
   　　　　5) [2]-->[5], Weight= 8
   　　　　6) [3]-->[5], Weight= 4
   
   　従って、今回の接続 ([0]-->[3], Weight= 3) が、一番コストが低い。