グラフの３色塗り分け問題

 【 グラフの３色塗り分け問題 】

先に「リーマン予想」と等価な「グラフの３色塗り分け問題」があると書いたのだが、グラフの問題に置き換えたからといって、問題がやさしくなるわけではないことを、確認しておこう。

グラフの頂点を、{r(赤) , g(緑) , b(青) }の三色で塗る場合の数がいくつあるかを考えよう。
頂点の数が1つの場合には、{r}, {g}, {b}の 3通り、
頂点の数が2つの場合には、{rr}, {gg}, {bb}, {rg}, {gr}, {gb}, {bg}, {rb}, {br} の 9通り.
一般に頂点の数がn個の場合には、\(3^n\) 通りになる。

頂点の数が20個で頂点が3色に塗られたグラフの数は、\(3^{20}\)である。一つのグラフを見つけるのに1nano秒かかるとしてこの操作は、多分、数秒で終わるだろう。

nが大きくなるにつれて、この\(3^n\)は急速に増大する。n=30となると、\(3^{30}\)という数のグラフを枚挙する操作は、\(3^{30}\) nano秒の時間を要する。それは現在の宇宙が生まれてから現在までの時間の100倍以上の時間が必要になる。

n=30程度であっても、総当たりで、三色グラフを全部数え上げるのは、ほぼ、不可能だ。（「リーマン予想」を表現するグラフが、頂点数が30程度ということはないだろう。）

ただ、n個の頂点を持つグラフを3色で「塗り分けろ」というのは、同じ色を持つ頂点は辺で結ばれていてはいけないということだ。

だから、もし、誰かが頂点数30のグラフの「3色塗り分け」を与えたとしよう。この時、この「3色塗り分け」が「正しい塗り分け」になっているかの「検証」は、30個の頂点について、その頂点と辺で結ばれている隣り合う頂点が違う色であることをチェックすれば、簡単に終わる。

一般に、n個の頂点からなるグラフでは、一つの頂点に対して、辺で結ばれた頂点は多くてもn-1個しかない。辺で結ばれた頂点の色が違うことのチェックは、 高々、\(n(n-1)/2\)回のチェックで終わってしまう。これは多項式時間で検証可能である。