最大カット問題

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

無向グラフ構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (V, E) \,} において, 各枝$e_{ij}\in E\ (i,j\in V,\ i\neq j)\,$に非負整数$w_{ij}\,$が重みとして付与されている. このとき

$\sum _{\begin{array}{c}i\in X\\j\in V-X\end{array}}\ w_{ij}\,$

スタイル検討

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