# 最小グラフ二分割問題
:::{container} prog-cpp
無向グラフ $G=(V,E)$（$n$ ノード,$n$ は偶数）が与えられたとき,**最小グラフ二分割**問題は,ノード集合 $V$ を**等しいサイズ**（$\lvert S\rvert=\lvert\overline{S}\rvert=n/2$）の2つの互いに素な部分集合 $S$ と $\overline{S}$ に分割し,分割を横断する辺の数を**最小化**することを目的とします.
この問題は[最大カット](../example/graph/maximum-cut.md)と2つの点で異なります：
1. 分割は**均等**（同サイズの半分）でなければなりません.
2. 横断辺の数を（最大化ではなく）**最小化**します.
最小グラフ二分割は NP 困難であり,回路分割,並列計算,グラフベースのデータクラスタリングなどの応用があります.
## QUBO 定式化
ノードに $0,1,\ldots,n-1$ のラベルが付いているとします.
$n$ 個のバイナリ変数 $x_0, x_1, \ldots, x_{n-1}$ を導入し,$x_i=1$ はノード $i$ が $S$ に属することを表します.
### 目的関数
分割を横断する辺の数は以下の通りです：
$$
\text{objective} = \sum_{(i,j)\in E}\Bigl(x_i\bar{x}_j + \bar{x}_ix_j\Bigr)
$$
この値を**最小化**します.
### 制約
分割は均等でなければなりません：
$$
\text{constraint} = \Bigl(\sum_{i=0}^{n-1} x_i = \frac{n}{2}\Bigr)
$$
この制約式は充足されたとき 0 になります.
### QUBO 式
最終的な QUBO 式は,目的関数と制約をペナルティ重み $P$ で組み合わせます：
$$
f = \text{objective} + P \times \text{constraint}
$$
ここで $P$ は十分大きく（例えば $P = \lvert E\rvert + 1$）,最適解で均等制約が常に満たされるようにします.
## Hi-QUBO プログラム
以下の Hi-QUBO プログラムは,16 ノードのグラフに対する最小グラフ二分割問題を解きます：
```{literalinclude} /../programFiles/cppPrograms/example/graph/bisection-program1.cpp
:language: cpp
:caption: bisection-program1.cpp
```
このプログラムでは,目的関数がカットを横断する辺の数をカウントし,制約が各パーティションに正確に $N/2$ ノードが含まれることを強制します.
ペナルティ重み $P = M + 1$ により,均等制約が常に満たされます.
最大カット問題では最大化のために目的関数を符号反転しますが,ここでは目的関数を直接最小化します.
### 出力結果
```{include} /../programFiles/markDown/example/graph/bisection.md
:start-after:
:end-before:
```
ソルバーは横断辺が 6 本のみの均等分割を見つけます.
結果のグラフは描画され,ファイル `bisection.svg` に保存されます：
:::
:::{container} prog-python
無向グラフ $G=(V,E)$（$n$ ノード,$n$ は偶数）が与えられたとき,**最小グラフ二分割**問題は,ノード集合 $V$ を**等しいサイズ**（$\lvert S\rvert=\lvert\overline{S}\rvert=n/2$）の2つの互いに素な部分集合 $S$ と $\overline{S}$ に分割し,分割を横断する辺の数を**最小化**することを目的とします.
この問題は[最大カット](../example/graph/maximum-cut.md)と2つの点で異なります：
1. 分割は**均等**（同サイズの半分）でなければなりません.
2. 横断辺の数を（最大化ではなく）**最小化**します.
最小グラフ二分割は NP 困難であり,回路分割,並列計算,グラフベースのデータクラスタリングなどの応用があります.
## QUBO 定式化
ノードに $0,1,\ldots,n-1$ のラベルが付いているとします.
$n$ 個のバイナリ変数 $x_0, x_1, \ldots, x_{n-1}$ を導入し,$x_i=1$ はノード $i$ が $S$ に属することを表します.
### 目的関数
分割を横断する辺の数は以下の通りです：
$$
\text{objective} = \sum_{(i,j)\in E}\Bigl(x_i\overline{x_j} + \overline{x_i}x_j\Bigr)
$$
この値を**最小化**します.
### 制約
分割は均等でなければなりません：
$$
\text{constraint} = \Bigl(\sum_{i=0}^{n-1} x_i = \frac{n}{2}\Bigr)
$$
この制約式は充足されたとき 0 になります.
### QUBO 式
最終的な QUBO 式は,目的関数と制約をペナルティ重み $P$ で組み合わせます：
$$
f = \text{objective} + P \times \text{constraint}
$$
ここで $P$ は十分大きく（例えば $P = \lvert E\rvert + 1$）,最適解で均等制約が常に満たされるようにします.
## PyQBPP プログラム
以下の PyQBPP プログラムは,16 ノードのグラフに対する最小グラフ二分割問題を解きます：
```{literalinclude} /../programFiles/pythonPrograms/example/graph/bisection-program1.py
:language: python
:caption: bisection-program1.py
```
このプログラムでは,目的関数がカットを横断する辺の数をカウントし,制約が各パーティションに正確に $N/2$ ノードが含まれることを強制します.
ペナルティ重み $P = M + 1$ により,均等制約が常に満たされます.
最大カット問題では最大化のために目的関数を符号反転しますが,ここでは目的関数を直接最小化します.
### 出力結果
```{include} /../programFiles/markDown/example/graph/bisection.md
:start-after:
:end-before:
```
ソルバーは横断辺が 6 本のみの均等分割を見つけます.
## matplotlib による可視化
以下のコードは `matplotlib` と `networkx` を用いて最小グラフ二分割の解を可視化します：
```{literalinclude} /../programFiles/pythonPrograms/example/graph/bisection-program2.py
:language: python
:caption: bisection-program2.py
```
2つの均等な分割は赤と青で表示されます.カット辺（分割を横切る辺）は赤でハイライトされます.
:::