頂点彩色数
ソースコード
nachia/graph/chromatic-number.hpp
主な機能
グラフの頂点彩色数を求める。
頂点彩色数とは、隣接する $2$ 頂点に同じ色を塗らないようにしてすべての頂点を塗るとき、使う色の最小個数である。
関数
ChromaticNumber
int ChromaticNumber(std::vector<std::vector<int>> adjacency_matrix);
- $1 \leq n \leq 31$
adjacency_matrixは $n \times n$ の行列- 頂点 $i$ と頂点 $j$ を結ぶ辺があるとき $\text{adjacency_matrix}[i][j]=1$ 、ないとき $\text{adjacency_matrix}[i][j]=0$
- $\text{adjacency_matrix}[i][i]=0$ （自己ループはない）
- $\text{adjacency_matrix}[i][j]=\text{adjacency_matrix}[j][i]$
- 条件付きで $\color{red}{O(2^n)}$ 時間
グラフの頂点彩色数を返す。
__GNUC__ が定義されている場合、 __builtin_parity 関数を呼び出す。そうでない場合、相当する演算を $O(2^n)$ 回行う。