最大カット問題
2007年7月12日 (木) 15:16時点における122.17.2.240 (トーク)による版 (新しいページ: ''''【さいだいかっともんだい (maximum cut problem)】''' 無向グラフ$(V,\: E)$において, 各枝$e_{ij}\in E\: (i,j\in V,\: i\ne j)$に非負整数$w_{ij}$が...')
【さいだいかっともんだい (maximum cut problem)】
無向グラフ$(V,\: E)$において, 各枝$e_{ij}\in E\: (i,j\in V,\: i\ne j)$に非負整数$w_{ij}$が重みとして付与されている. このとき
\[ \sum_{\tiny \begin{array}{c} i\in X\\ j\in V-X \end{array}}\: w_{ij} \]
を最大にする$X\subset V$を求める問題. つまり, $V$を2つの部分集合に分割する組合せ(カット)のうち, それらの部分集合間の枝に付与された重みの総和が最大となる分割を求める.