6. gw_mw_matching.exe の使用法

• アルゴリズムの名称：General Weighted Matchings
• 内容：「どの2 辺も共通の端点を持たないエッジ」の数が最大になり、且つ、コストを最大にする組合せを求める

【概要】

mw_matching は、"Max Weight Matching" のことです。

Matching は、”「どの2 辺も共通の端点を持たないエッジ」の数が最大になる組合せを求める” と言う定義です。

mw_matching は、Matching の組合せの中で、コストを最大にするものを示します。

1. メニューの "Graph-> Create-> random planar" を選ぶ
   
   ダイアログが現れるので、以下の設定をする
   
   　　　　　　　 nodes = 9
   　　　　　　　 edges = 21
   　　　　　　　 layout= circle
   
   
   
   
2. 「9 nodes, 21 edges」のグラフが自動生成される
   
   「どの2 辺も共通の端点を持たないエッジ」が４個描かれている (青色の太い線)
   また、この４つのエッジの Weight の合計が、最大となるような組合せです。
   
   　　４つのエッジの Weight の合計 = 12 + 32 + 16 + 20 = 80
   
   
   
   
3. 次に、左下にある「Weight = 12」のエッジの Weight を 16 に変更する (エッジ上のスライダーを移動させて調整する)、新たな４つのエッジの組合せが得られる。
   
   この４つのエッジの Weight の合計は 80 です。
   
   　　　　 20 + 28 + 16 + 16 = 80
   
   先程の修正前の Weight の合計と同じですが、Weight が 16 より大きくなると、新しい組合せの方が、Weight の合計が大きくなります。