【さいだいかっともんだい (maximum cut problem)】
無向グラフ ( V , E ) {\displaystyle (V,E)\,} において, 各枝 e i j ∈ E ( i , j ∈ V , i ≠ j ) {\displaystyle e_{ij}\in E\ (i,j\in V,\ i\neq j)\,} に非負整数 w i j {\displaystyle w_{ij}\,} が重みとして付与されている. このとき
∑ i ∈ X , j ∈ V − X w i j {\displaystyle \sum _{i\in X,\,\,j\in V-X}\ w_{ij}}
を最大にする X ⊂ V {\displaystyle X\subset V\,} を求める問題. つまり, V {\displaystyle V\,} を2つの部分集合に分割する組合せ(カット)のうち, それらの部分集合間の枝に付与された重みの総和が最大となる分割を求める.
において, 各枝
に非負整数
が重みとして付与されている. このとき
を求める問題. つまり, 
を2つの部分集合に分割する組合せ(カット)のうち, それらの部分集合間の枝に付与された重みの総和が最大となる分割を求める.