彩色多項式の話【ABC294-Ex問題】

 

この記事でやること

ABC294-Ex問題 にてグラフ彩色の通り数に関する問題が出題され、その際彩色多項式なるものを勉強したので備忘録として残しておきます。

 

彩色多項式とは

グラフ G の k-彩色の通り数を k に関する多項式で表したものです。

これを P_{G}(k) と表すことにします。

 

木の彩色多項式

n 頂点の木 T に対し、彩色多項式は

P_{T}(k) = k(k-1)^{n-1}

と表せます。これは、適当な根を取って自由に色を決め、そこから親と異なる色を順に塗っていけることからすぐにわかります。

 

彩色多項式の漸化式

彩色多項式 P_{G}(k) と辺 e \in V(G) について、以下の漸化式が成立します：

P_{G}(k) = P_{G-e}(k) - P_{G \backslash e}(k)

※ G-e は G から e を除いたグラフ、 G \backslash e は G を e について縮約したグラフ

 

証明

グラフ G-e の k-彩色の通り数を考える。 e = (u, v) としたとき、

  1. u, v を異なる色に彩色する場合：
    • G の k-彩色と1対1対応するため、 P_{G}(k) 通り。
  2. u, v を同じ色に彩色する場合：
    • G \backslash e の k-彩色と1対1対応するため、 P_{G \backslash e}(k) 通り。

以上より、 P_{G-e}(k) = P_{G}(k) + P_{G \backslash e}(k) であり、漸化式が得られる。 \square

 

単純連結グラフの彩色多項式

与えられたグラフに対し、閉路に含まれる1辺を e として漸化式を適用することを木になるまで繰り返すことで得られます。*1縮約の際に多重辺ができる場合は、重複を除いて単純性が崩れないように注意しましょう。

 

ACコード

Submission #39887705 - AtCoder Beginner Contest 294

 

参考文献

https://ocw.hokudai.ac.jp/wp-content/uploads/2016/01/GraphTheory-2005-Note-10.pdf

*1:連結性を保つために閉路上の辺を選んでいます。また、この解法の計算量についてはあまりよくわかっていません。最悪ケースをかなり緩く見積もるモデルでの測定値が10^9程度の状態数となっており、実際はもっと少ないはずなので十分間に合うだろう推測しております。