最大カット問題

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

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

構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \sum _{i\in X,\,\,j\in V-X}\ w_{ij}}

を最大にする構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle X\subset V \,} を求める問題. つまり, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle V \,} を2つの部分集合に分割する組合せ(カット)のうち, それらの部分集合間の枝に付与された重みの総和が最大となる分割を求める.