# グラフ彩色問題
:::{container} prog-cpp
無向グラフ $G=(V,E)$ が与えられたとき,**グラフ彩色問題**は,隣接するノードが異なる色を持つように各ノードに色を割り当てることを目的とします.
より具体的には,色の集合 $C$ に対して,すべての辺 $(u,v)\in E$ について $\sigma(u)\neq \sigma(v)$ となるような割り当て $\sigma:V\rightarrow C$ を求めます.グラフ彩色問題は QUBO 式として容易に定式化できます.
$V=\lbrace 0,1,\ldots ,n−1\rbrace$,$C=\lbrace 0,1,\ldots ,m−1\rbrace$ とします.
$n\times m$ のバイナリ変数行列 $X=(x_{i,j})$ を導入し,$x_{i,j}=1$ はノード $i$ に色 $j$ が割り当てられることを表します.
### ワンホット制約
各ノードにちょうど1つの色を割り当てる必要があるため,$X$ の各行はワンホットでなければなりません：
$$
\begin{aligned}
\text{onehot}&= \sum_{i=0}^{n-1}\Bigl(\sum_{j=0}^{m-1}x_{i,j}==1\Bigr)\\
&=\sum_{i=0}^{n-1}\Bigl(1-\sum_{j=0}^{m-1}x_{i,j}\Bigr)^2
\end{aligned}
$$
### 隣接ノードは異なる色
各辺について,その端点は同じ色を共有してはなりません.これは以下のようにペナルティ化できます：
$$
\begin{aligned}
\text{different}&= \sum_{(u,v)\in E}x_u\cdot x_v\\
&=\sum_{(u,v)\in E}\sum_{j=0}^{m-1}x_{u,j}x_{v,j}
\end{aligned}
$$
## QUBO 目的関数
これらの式を組み合わせることで,QUBO 目的関数が得られます：
$$
\begin{aligned}
f &= \text{onehot}+\text{different}
\end{aligned}
$$
この目的関数は,グラフの有効な $m$-彩色が存在する場合にのみ最小値 0 を達成します.
## Hi-QUBO による定式化
任意の平面グラフは最大4色で彩色できるため,16 ノードの平面グラフと $m=4$ 色を例として使用します.以下の Hi-QUBO プログラムがこのインスタンスを解きます：
```{literalinclude} /../programFiles/cppPrograms/example/graph/graph-color-program1.cpp
:language: cpp
:caption: graph-color-program1.cpp
```
このプログラムでは,まず $n\times m$ のバイナリ変数行列 `x` を定義し,上記の定式化に従って式 `onehot`,`different`,`f` を構築します.得られた QUBO を目標エネルギー 0 で Easy Solver を用いて解き,解を `sol` に格納します.
次に,`sol` における `onehot` と `different` の値を出力します.また,`sol(x)` に `qbpp::onehot_to_int()` を適用して,各ノードに割り当てられた色を格納する `node_color` を計算します.
最後に,`qbpp::graph::GraphDrawer` を使って彩色されたグラフを描画します.各ノード `i` は色番号 `node_color[i] + 1` で彩色されます.
関数 `qbpp::onehot_to_int()` は $[0,m−1]$ の範囲の整数ベクトルを返し,各エントリはワンホット行列の対応する行における 1 の位置を示します.行が有効なワンホットベクトルでない場合,その行に対して $−1$ を返します.
この場合,ノードの色は $-1 + 1 = 0$ となり,ノードは色 0（白）で描画されます.
### $m=4$ の結果
このプログラムの出力は以下の通りです：
```{include} /../programFiles/markDown/example/graph/graph-color.md
:start-after:
:end-before:
```
したがって,有効な 4-彩色が見つかりました：
### $m=3$ の結果
同じプログラムを $m=3$ で実行すると,以下の出力が得られます：
```{include} /../programFiles/markDown/example/graph/graph-color.md
:start-after:
:end-before:
```
このグラフは3彩色不可能（彩色数は4）であり,有効な3彩色は存在しません.そのためペナルティを最小化する解でも,ちょうど1つのノードが整合的な色を持てません（1つの行がワンホットになりません）.結果のグラフでは,ノード 7 が未彩色のままです：
:::
:::{container} prog-python
無向グラフ $G=(V,E)$ が与えられたとき,**グラフ彩色問題**は,隣接するノードが異なる色を持つように各ノードに色を割り当てることを目的とします.
より具体的には,色の集合 $C$ に対して,すべての辺 $(u,v)\in E$ について $\sigma(u)\neq \sigma(v)$ を満たす割り当て $\sigma:V\rightarrow C$ を求めます.
$V=\lbrace 0,1,\ldots ,n−1\rbrace$,$C=\lbrace 0,1,\ldots ,m−1\rbrace$ とします.
$n\times m$ のバイナリ変数の行列 $X=(x_{i,j})$ を導入し,$x_{i,j}=1$ はノード $i$ に色 $j$ が割り当てられている場合にのみ成り立ちます.
### One-hot 制約
各ノードにちょうど1つの色が割り当てられなければならないため,$X$ の各行は one-hot でなければなりません：
$$
\begin{aligned}
\text{onehot}&= \sum_{i=0}^{n-1}\Bigl(\sum_{j=0}^{m-1}x_{i,j}==1\Bigr)
\end{aligned}
$$
### 隣接ノードは異なる色
各辺について,その両端点は同じ色を共有してはなりません：
$$
\begin{aligned}
\text{different}&= \sum_{(u,v)\in E}\sum_{j=0}^{m-1}x_{u,j}x_{v,j}
\end{aligned}
$$
## QUBO 目的関数
$$
\begin{aligned}
f &= \text{onehot}+\text{different}
\end{aligned}
$$
## PyQBPP プログラム
任意の平面グラフは最大4色で彩色可能であるため,16ノードの平面グラフと $m=4$ 色を例として使用します：
```{literalinclude} /../programFiles/pythonPrograms/example/graph/graph-color-program1.py
:language: python
:caption: graph-color-program1.py
```
このプログラムでは,まず $n\times m$ のバイナリ変数の行列 `x` を定義し,次に式 `onehot`,`different`,`f` を構築します.
得られた QUBO を,`search()` に `target_energy=0` を渡して Easy Solver で解きます.
### $m=4$ の場合の結果
このプログラムは以下の出力を生成します：
```{include} /../programFiles/markDown/example/graph/graph-color.md
:start-after:
:end-before:
```
したがって,有効な4彩色が見つかりました.
### $m=3$ の場合の結果
$m=3$ で実行すると,プログラムは以下の出力を生成します：
```{include} /../programFiles/markDown/example/graph/graph-color.md
:start-after:
:end-before:
```
このグラフは3彩色不可能（彩色数は4）であり,有効な3彩色は存在しません.そのためペナルティを最小化する解でも,ちょうど1つのノードが整合的な色を持てません（すなわち,1つの行が one-hot になりません）.
## matplotlib による可視化
以下のコードは,グラフ彩色の解を可視化します：
```{literalinclude} /../programFiles/pythonPrograms/example/graph/graph-color-program2.py
:language: python
:caption: graph-color-program2.py
```
各ノードは割り当てられた色に従って彩色されます.
:::