大域最小カット(Global Minimum Cut)

問題

連結無向グラフのカットのうち最小のものを求める。

実装

ソースコード(IdeOne)

解説

• 乱択アルゴリズムによる実装。
• 一辺をランダムに選んで縮約していく。
• 最後に2点残る。これらの点に縮約された点が大域最小カットである可能性は以上。
• 頂点の数をとし、回アルゴリズムを繰り返すとき、大域最小カットが得られない確率は以下となる。
• 決定的アルゴリズムの素朴な実装は始点を任意に選び、カットアルゴリズムを回使用して最小値をとったものとなる。これは多項式時間アルゴリズムである。
• このKargerによる方法をさらに改良したアルゴリズムがある。参照(pdf)
• 大域最小カット問題は画像の領域分割に使えるらしい。