# 最大カット問題
:::{container} prog-cpp
無向グラフ $G=(V,E)$ が与えられたとき,**最大カット**問題は,ノード集合 $V$ を2つの互いに素な部分集合 $S$ と $\overline{S}$ に分割し,一方の端点が $S$ に,他方の端点が $\overline{S}$ にある $E$ の辺の数を**最大化**することを目的とします.
ノードに $0,1,\ldots,n-1$ のラベルが付いているとします.
$n$ 個のバイナリ変数 $x_0, x_1, \ldots, x_{n-1}$ を導入し,$x_i=1$ はノード $i$ が $S$ に属することを表します ($0\le i\le n-1$).
すると,カット $(S,\overline{S})$ を横断する辺の数は以下で与えられます：
$$
\begin{aligned}
\text{objective} &= \sum_{(i,j)\in E}\Bigl(x_i\bar{x}_j + \bar{x}_ix_j\Bigr).
\end{aligned}
$$
QUBO 問題は目的関数を**最小化**するため,目的関数を**符号反転**して QUBO 式 $f$ を得ます：
$$
\begin{aligned}
f &= -\,\text{objective}.
\end{aligned}
$$
$f$ を最小化する最適な割り当ては $G$ の最大カットに対応します.
また,$\text{objective}$ の値は $S$ と $\overline{S}$ の間を横断する辺の数に等しくなります.
## 最大カット問題の Hi-QUBO プログラム
上記の定式化に基づき,以下の Hi-QUBO プログラムは 16 ノードのグラフに対する QUBO 式 $f$ を構築し,Exhaustive Solver を用いて解きます：
```{literalinclude} /../programFiles/cppPrograms/example/graph/maximum-cut-program1.cpp
:language: cpp
:caption: maximum-cut-program1.cpp
```
このプログラムは式 `objective` と `f` を作成します.`f` は `objective` の符号反転です.
Exhaustive Solver が `f` を最小化し,最適な割り当てが `sol` に格納されます.
解を可視化するために,`GraphDrawer` オブジェクト `graph` を作成し,ノードと辺を追加します.
この可視化では,$S$ に属するノード $i$（つまり $x_i=1$ のノード）が着色され,カットを横断する辺が強調表示されます.
このプログラムの出力は以下の通りです：
```{include} /../programFiles/markDown/example/graph/maximum-cut.md
:start-after:
:end-before:
```
結果のグラフは描画され,ファイル `maxcut.svg` に保存されます：
:::
:::{container} prog-python
無向グラフ $G=(V,E)$ が与えられたとき,**最大カット問題**は,ノード集合 $V$ を2つの互いに素な部分集合 $S$ と $\overline{S}$ に分割し,一方の端点が $S$ に,他方が $\overline{S}$ に属する $E$ 中の辺の数を**最大化**することを目的とします.
ノードは $0,1,\ldots,n-1$ とラベル付けされているとします.
$n$ 個のバイナリ変数 $x_0, x_1, \ldots, x_{n-1}$ を導入し,$x_i=1$ はノード $i$ が $S$ に属する場合にのみ成り立ちます（$0\le i\le n-1$）.
このとき,カット $(S,\overline{S})$ を横切る辺の数は次のように与えられます：
$$
\begin{aligned}
\text{objective} &= \sum_{(i,j)\in E}\Bigl(x_i\overline{x_j} + \overline{x_i}x_j\Bigr).
\end{aligned}
$$
QUBO 問題は目的関数を**最小化**することを目指すため,目的関数を**符号反転**して QUBO 式 $f$ を得ます：
$$
\begin{aligned}
f &= -\,\text{objective}.
\end{aligned}
$$
$f$ を最小化する最適な割り当ては,$G$ の最大カットに対応します.
## Max-Cut 問題の PyQBPP プログラム
```{literalinclude} /../programFiles/pythonPrograms/example/graph/maximum-cut-program1.py
:language: python
:caption: maximum-cut-program1.py
```
このプログラムは式 `objective` と `f` を作成します.`f` は `objective` の符号反転です.
Exhaustive Solver が `f` を最小化し,最適な割り当てが `sol` に格納されます.
このプログラムは以下の出力を生成します：
```{include} /../programFiles/markDown/example/graph/maximum-cut.md
:start-after:
:end-before:
```
## matplotlib による可視化
以下のコードは `matplotlib` と `networkx` を用いて Max-Cut の解を可視化します：
```{literalinclude} /../programFiles/pythonPrograms/example/graph/maximum-cut-program2.py
:language: python
:caption: maximum-cut-program2.py
```
2つの分割は赤と青で表示されます.カット辺（分割を横切る辺）は赤でハイライトされます.
:::