研究成果 > アルゴリズムのデモ > 最小カット問題

最小カット問題とは

例えば，100人の学生がいて，これを二つのグループに分けるとします．二人の学生の間には，出身地や趣味な どにより結びつきの強さが数値で表わされているとします．このとき，それぞれのグループ内における結びつき が強くなるように，言い換えると，二つのグループ間の結びつきの数値が最小になるようにしたいとします（グ ループ内の人数は同じでなくてよい）．

この問題をグラフを使って表します．グラフとはいくつかの節点（点）の集まりと点と点をつなぐ枝（辺）の集 まりからなります．枝には数値がついています．グループ分けの例では，一人の学生が一つの節点に対応し，二 人の学生間の結びつきが，対応する 2節点間の枝の数値に対応します（結びつき度が 0であれば枝をつけないこ とにします）．すると問題は，グラフの節点の集合を二つの集合に分けて，二つの集合間にまたがる枝の数値の 和を最小にする問題になります．このような分割を最小カットといいます．

デモの説明： 永持-茨木法

このデモでは永持，茨木により提案されたアルゴリズムを実行します（この方法は最小カットを正確に計算する 方法としては現在世界最速の計算性能を持っています）．

まず，この方法は，グラフの節点に番号を 1,2,3,... とつけています． 最初に好きな節点に 1をつけ，その後は以下のルール M に従って節点を選んでいきます．

ルール M： 「残りの節点の中で，すでに選ばれた節点の集まりに最も結びつきの強い（枝の数値の和が最大である）節点を選ぶ」
ルール M でつけられた番号を最大隣接順序と言います．

デモでは，最初の節点に選びたいところでクリックをすると，その節点の色が水色に変わり，1の番号がつきま す．もう一度クリックをすると，1番の節点に最も結びつきの強い節点が水色に変わり，2の番号がつきます．再 度クリックをすると，1, 2の節点に最も結びつきの強い節点が選ばれ 3の番号がつきます．クリックを繰り返す と最後の点にまで番号がつき，最大隣接順序が得られます．

最大隣接順序の性質

この番号付けにおいて，最後の二つの節点（A, Bとする）に対しては，節点 A と節点 B を別々のグループに分 けるような分割の中では，最後の節点１個とそれ以外の節点を分けるのが，最も分割の両側にまたがる枝の数値 和が小さくなることが証明されています．デモでは赤い枝としてこれらの枝が表示されます．

この性質では，最後の二つの節点を別々のグループに入れたらという条件のもとでの最小カットですので，求め たい最小カットではないかもしれません．そこで，いまの最小カットの値を保存しておきます（デモでは画面左 上に，A-BCDEF [140] のように表示がでます．これは，節点 A と節点 B, C, D, E, F に分割する最小カットの 値が 140であることを意味します．）

次にやるべきことは，最後の二つの節点（A, Bとする）が必ず同じグループに入るような分割の仕方を調べるこ とです．ここで，後の計算で，２節点A,Bが決して分離されないように，A と B とを 1個の節点にまとめてしま います．デモでは最大隣接順序が求まった後に，自動的に最後の番号の 2節点が 1個に併合されますのでこの様 子を確認してください．

以上で，アルゴリズムの１反復分の作業の説明が終わりました．後はこの作業を繰り返すだけです．つまり，

(1) 最大隣接順序を計算し，
(2) 最後の２節点を分離する最小カットを記録し，
(3) この２節点を１個の節点に併合する
という作業をグラフがただ 一つの節点になるまで繰り返して，記録した値のうちで最も小さい値をもつものを （求めるべき）最小カットとすればよいだけです．

遊び方

好きな節点をクリックして 1番の節点として下さい．クリックを続けるとすべての節点に番号がつきます．節点 は番号に従って時計回りの位置に再配置されます．最後の節点とそれ以外の節点の間にまたがる枝が赤色で表示 されます．もう一度クリックをすると，最後の２節点が併合されます．これを繰り返してください．最後に求め るべき最小カットが画面右上の記録から選択され，もとのグラフにおいて赤い枝として表示されデモが終了しま す．

デモの動きの速度を変えるには画面中央下のからnormal（中速），quick（高速），slow（低速）を選択してください．

画面中央下にある Resetボタンを押すと最初のグラフに戻ります．