最大カット問題

出典: ORWiki

【さいだいかっともんだい (maximum cut problem)】

無向グラフ(V, E) \,において, 各枝e_{ij} \in E\ (i,j\in V,\ i\ne j) \,に非負整数w_{ij} \,が重みとして付与されている. このとき

\sum_{i \in X,\,\, j \in V-X}\ w_{ij}


を最大にするX\subset V \,を求める問題. つまり, V \,を2つの部分集合に分割する組合せ(カット)のうち, それらの部分集合間の枝に付与された重みの総和が最大となる分割を求める.

"http://www.orsj.or.jp/~wiki/wiki/index.php/%E6%9C%80%E5%A4%A7%E3%82%AB%E3%83%83%E3%83%88%E5%95%8F%E9%A1%8C" より作成