彩色多項式とは？ わかりやすく解説

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/28 15:48 UTC 版)

「グラフ彩色」の記事における「彩色多項式」の解説

彩色多項式(chromatic polynomial)とは、与えられたグラフを与えられた色数内で彩色したときの彩色の組合せ数を求める式である。例えば、右図のグラフは3色で彩色すると12通りの彩色が可能である。2色では彩色できない。4色では 24 + 4×12 = 72 通りである。4色を使った彩色は24通りで、4色のうちの3色を使った彩色はそれぞれ12通りなので、このような計算になる（4色を4つの頂点に割り当てる場合は、任意の組み合わせが可能である）。従って、このグラフの彩色数を表にすると次のようになる。 色数 1 2 3 4 … 彩色の組み合わせ数 0 0 12 72 … 彩色多項式は、 P ( G , t ) {\displaystyle P(G,t)} で表され、グラフ G {\displaystyle G} を t {\displaystyle t} 色で彩色したときの色の組合せ数である。名前が示すとおり、ある G {\displaystyle G} についての彩色多項式は、 t {\displaystyle t} に関する多項式となる。例に挙げたグラフでは、 P ( G , t ) = t ( t − 1 ) 2 ( t − 2 ) {\displaystyle P(G,t)=t(t-1)^{2}(t-2)} となる。 彩色多項式は彩色数と共に、 G {\displaystyle G} の彩色可能性についての情報をもたらす。実際、彩色数 χ は彩色多項式の根ではない最小の正の整数である。 χ ( G ) = min { k : P ( G , k ) > 0 } {\displaystyle \chi (G)=\min\{k\colon P(G,k)>0\}} この概念を最初に使ったのは George David Birkhoff と D. C. Lewis であり、四色定理の証明を試みる過程で用いた。 特定のグラフに関する彩色多項式三角形 K 3 {\displaystyle K_{3}} t ( t − 1 ) ( t − 2 ) {\displaystyle t(t-1)(t-2)} 完全グラフ K n {\displaystyle K_{n}} t ( t − 1 ) ( t − 2 ) {\displaystyle t(t-1)(t-2)} ... ( t − ( n − 1 ) ) {\displaystyle (t-(n-1))} n {\displaystyle n} 頂点の木 t ( t − 1 ) n − 1 {\displaystyle t(t-1)^{n-1}} 閉路グラフ C n {\displaystyle C_{n}} ( t − 1 ) n + ( − 1 ) n ( t − 1 ) {\displaystyle (t-1)^{n}+(-1)^{n}(t-1)} ピーターセングラフ t ( t − 1 ) ( t − 2 ) ( t 7 − 12 t 6 + 67 t 5 − 230 t 4 + 529 t 3 − 814 t 2 + 775 t − 352 ) {\displaystyle t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)} 彩色多項式には次のような属性がある。 P ( G , 0 ) = 0 {\displaystyle P(G,0)=0} P ( G , 1 ) = 0 {\displaystyle P(G,1)=0} （ G {\displaystyle G} に辺がある場合） P ( G , t ) = 0 {\displaystyle P(G,t)=0} （ t < χ ( G ) {\displaystyle t<\chi (G)} の場合） G {\displaystyle G} が n {\displaystyle n} 個の頂点、 m {\displaystyle m} 個の辺、 k {\displaystyle k} 個の連結成分 G 1 , G 2 , {\displaystyle G_{1},G_{2},} …, G k {\displaystyle G_{k}} から成るとき、 P ( G , t ) {\displaystyle P(G,t)} の次数は n {\displaystyle n} である。 P ( G , t ) {\displaystyle P(G,t)} における t n {\displaystyle t^{n}} の係数は 1 である。 P ( G , t ) {\displaystyle P(G,t)} における t n − 1 {\displaystyle t^{n-1}} の係数は − m {\displaystyle -m} である。 t 0 , t 1 , {\displaystyle t^{0},t^{1},} … t k − 1 {\displaystyle t^{k-1}} の係数は全てゼロである。 t k {\displaystyle t^{k}} の係数はゼロではない。 P ( G , t ) = P ( G 1 , t ) P ( G 2 , t ) {\displaystyle P(G,t)=P(G_{1},t)P(G_{2},t)} ⋯ P ( G k , t ) {\displaystyle P(G_{k},t)} 全ての彩色多項式の係数は符号が交互に変化する。 P ( G , t ) = t ( t − 1 ) n − 1 {\displaystyle P(G,t)=t(t-1)^{n-1}} であるときのみ、 n {\displaystyle n} 頂点のグラフ G は木である。 単位元で評価された導関数 P ′ ( G , 1 ) {\displaystyle P'(G,1)} は「彩色不変量(chromatic invariant)」 θ ( G ) {\displaystyle \theta (G)} である。

※この「彩色多項式」の解説は、「グラフ彩色」の解説の一部です。
「彩色多項式」を含む「グラフ彩色」の記事については、「グラフ彩色」の概要を参照ください。