最大カット問題

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

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

スタイル検討

構文解析に失敗 (不明な関数「\tiny」): {\displaystyle \sum_{\tiny\begin{array}{c} i\in X\\ j\in V-X \end{array}}\ w_{ij} \,}

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