最大カット問題のソースを表示

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

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

[[スタイル検討]]

<!-- 和の記号の下に改行した式を入力 -->

<math>
\sum_{\tiny\begin{array}{c} i\in X\\ j\in V-X \end{array}}\ w_{ij} 
\,</math>


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