# 最大クリーク問題
:::{container} prog-cpp
無向グラフ $G=(V,E)$ が与えられたとき,最大クリーク問題は,$S$ 内の任意の異なる2頂点が $E$ の辺で結ばれているような最大の部分集合 $S\subseteq V$ を求めることを目的とします.
頂点に $0,1,\ldots,n−1$ のラベルが付いているとします.
$n$ 個のバイナリ変数 $x_0, x_1, \ldots, x_{n-1}$ を導入し,$x_i=1$ はノード $i$ が $S$ に属することを表します ($0\leq i\leq n−1$).
すると,$S$ のサイズは以下で与えられます：
$$
\begin{aligned}
\text{objective} &= \sum_{i=0}^{n-1}x_i.
\end{aligned}
$$
$S$ がクリークであるためには,選択されたノードのすべてのペアが辺で結ばれている必要があります.
同等に,$(i,j)\not\in E$ であるすべてのノードペア $i$ と $j$ について,$i$ と $j$ の両方を選択することはできません.
これは以下の制約で表現できます：
$$
\begin{aligned}
\text{constraint} &= \sum_{(i,j)\not\in E}x_ix_j
\end{aligned}
$$
実行可能なクリークは $constraint=0$ を満たします.
したがって,以下の QUBO 定式化 $f$（最小化対象）が得られます：
$$
\begin{aligned}
f &= -\text{objective}+2\times \text{constraint}
\end{aligned}
$$
ここで 2 はペナルティ係数です.
$f$ を最小化する最適解は最大クリークに対応し,目的関数の値は選択されたノードの数に等しくなります.
## 最大クリーク問題の Hi-QUBO プログラム
上記の定式化に基づき,以下の Hi-QUBO プログラムは 16 ノードのグラフに対する QUBO 式 $f$ を構築し,Exhaustive Solver を用いて解きます：
```{literalinclude} /../programFiles/cppPrograms/example/graph/maximum-clique-program1.cpp
:language: cpp
:caption: maximum-clique-program1.cpp
```
辺リスト `edges` から隣接行列 `adj` を構築し,与えられたノードペアがグラフの辺を形成するかどうかを判定できるようにします.
`N = 16` 個のバイナリ変数のベクトル `x` に対して,上記の QUBO 定式化に従って式 `objective`,`constraint`,`f` を構築します.
特に,`adj[i][j]` が false の場合,二次項 `x[i] * x[j]` が `constraint` に追加されます.
Exhaustive Solver を用いて `f` を最小化する最適解を求め,`sol` に格納します.`sol` における `objective` と `constraint` の値が出力されます.
`qbpp::graph::GraphDrawer` オブジェクト `graph` を作成し,選択されたクリークのノードと辺を強調表示します.
このプログラムの出力は以下の通りです：
```{include} /../programFiles/markDown/example/graph/maximum-clique.md
:start-after:
:end-before:
```
この出力から,制約を違反することなく 4 ノードの最大クリークが得られたことがわかります.
結果は以下のように `maxclique.svg` で可視化されます：
:::
:::{container} prog-python
無向グラフ $G=(V,E)$ が与えられたとき,最大クリーク問題は,$S$ 内のすべての異なる頂点対が $E$ の辺で接続されているような最大の部分集合 $S\subseteq V$ を求めることを目的とします.
頂点は $0,1,\ldots,n−1$ とラベル付けされているとします.
$n$ 個のバイナリ変数 $x_0, x_1, \ldots, x_{n-1}$ を導入し,$x_i=1$ はノード $i$ が $S$ に属する場合にのみ成り立ちます（$0\leq i\leq n−1$）.
このとき,$S$ のサイズは次のように与えられます：
$$
\begin{aligned}
\text{objective} &= \sum_{i=0}^{n-1}x_i.
\end{aligned}
$$
$S$ がクリークであるためには,選択されたすべてのノード対が辺で接続されていなければなりません.
同値的に,$(i,j)\not\in E$ であるすべてのノード対 $i$ と $j$ について,両方を選択することはできません.
これは以下の制約で表現できます：
$$
\begin{aligned}
\text{constraint} &= \sum_{(i,j)\not\in E}x_ix_j
\end{aligned}
$$
実行可能なクリークは $constraint=0$ を満たします.
したがって,以下の QUBO 定式化 $f$（最小化対象）を得ます：
$$
\begin{aligned}
f &= -\text{objective}+2\times \text{constraint}
\end{aligned}
$$
## 最大クリーク問題の PyQBPP プログラム
```{literalinclude} /../programFiles/pythonPrograms/example/graph/maximum-clique-program1.py
:language: python
:caption: maximum-clique-program1.py
```
辺リスト `edges` から隣接行列 `adj` を構築し,与えられたノード対がグラフの辺を形成するかどうかを判定できるようにします.
`N = 16` 個のバイナリ変数のベクトル `x` に対して,上記の QUBO 定式化に従って式 `objective`,`constraint`,`f` を構築します.
このプログラムは以下の出力を生成します：
```{include} /../programFiles/markDown/example/graph/maximum-clique.md
:start-after:
:end-before:
```
この出力から,制約を違反することなく4ノードの最大クリークが得られました.
## matplotlib による可視化
以下のコードは,最大クリークの解を可視化します：
```{literalinclude} /../programFiles/pythonPrograms/example/graph/maximum-clique-program2.py
:language: python
:caption: maximum-clique-program2.py
```
クリークのノードは赤で表示され,クリーク内の辺はハイライトされます.
:::