View on GitHub

cp-library

頂点彩色数

C++ 用ライブラリ一覧に戻る

ソースコード

nachia/graph/chromatic-number.hpp

主な機能

グラフの頂点彩色数を求める。

頂点彩色数とは、隣接する $2$ 頂点に同じ色を塗らないようにしてすべての頂点を塗るとき、使う色の最小個数である。

関数

ChromaticNumber

int ChromaticNumber(std::vector<std::vector<int>> adjacency_matrix);

グラフの頂点彩色数を返す。

__GNUC__ が定義されている場合、 __builtin_parity 関数を呼び出す。そうでない場合、相当する演算を $O(2^n)$ 回行う。

参考


TOP PAGE