くろょろぐ

はてダからはてブロに移行済み

方針転換

四色問題を考えるにあたって、頂点辺行列がそれなりに使える事を以前書いた。しかし頂点辺行列は位数2の体上で考える事ができるというメリットがある反面、問題を解くのに三つの連立方程式を同時に解かなければならないというデメリットがある。
四色問題を考える際には辺3彩色問題を解けばいいのだが、それを位数2の体の元で表すのはもともと無理があるわけで、一時、位数3や位数4の体を使う事も一応考えた。が、例外の扱いが面倒で、一番面倒のない位数2を選んだというのが実情である。
そもそも、頂点辺行列を使う事にこだわったのは、平面グラフに限定しない、一般の3正則グラフに適用するのに適していたからであって、もし対象を平面グラフに絞って考えるのであれば、頂点辺行列よりも、面頂点行列の方が扱いやすいはずである。
実は最初に考えたのも面頂点行列であって、この場合は辺3彩色のために頂点から見てどちら回りに彩色するかによって、各頂点に二つの値を割り振って連立方程式とすれば良い事も初めからわかっていた。そのためには各頂点に零でない位数3の体の元を割り当てる必要があるが、この方程式を解くのは難しいと判断したので、当初はこちらの方法に注目しなかったのである。

今、頂点辺行列を使う事に行き詰まりが見えてきたので、思いきって方針転換し、面頂点行列を試してみる事にした。ただ辺頂点行列での研究が無駄だったかと言えばそんな事はなく、今まできちんと理解できていなかったグラフの性質を知る事ができたので、多少の自信をもって方針転換する事ができる。

まず、面頂点行列に於いて、面というのはここではサイクルの事を指す。実際、面ではなくサイクルを使っても構わない。一般に、一次独立となるサイクルの数、すなわち次元は、最前の議論により、平面グラフの面の数と一致する事が、頂点辺行列に於ける核の次元の研究からわかっている。ちなみに、グラフが頂点を2彩色できる時、任意のサイクルが必ず偶数サイクルとなる時には次元が一つ減る事が容易に示される。
面頂点行列は、頂点数を2vで表すと、(v+1)行2v列の位数3の体{0,1,2}上の行列であり、ある行(=サイクル、面)にその頂点が含まれる時に、1又は2を配する行列となる。1にするか2にするかは、サイクルを一定の方向(右回りでも左回りでも良い)にめぐる時、各頂点に於いて分岐が左右どちらにあるかで決まる。例えば一つのサイクルにつき、右にあれば1、左にあれば2、のように決めておく。なお、一つのサイクルの中で同一ルールで値を決めてあればよく、サイクル毎にルールが違っていても問題はない。ちなみに、{0,1,2}の代わりに、{0,1,-1}のように平衡三進表現を使っても構わない(むしろその方が分かりやすいと思う)が、ここでは入力が簡単な{0.1.2}で表記するので容赦願いたい。

さて、任意のサイクルは辺を一周りすれば必ず元の色に戻るわけで、各頂点を変数と見た時、一つのサイクルに含まれる変数の値の和は必ず3の倍数、すなわち位数3の体で零とならなければならない。つまり、面頂点行列に於いて辺3彩色を求めるためには、この行列の核に含まれるベクトルのうち、どの成分も零とならないものを求めれば良い。
面頂点行列は一般にrankが(v+1)となる事は分かっており、したがって最初の(v+1)個の頂点まで対角化可能で、掃き出されて残った(v-1)個の頂点は全てパラメータとなる事がわかる。つまり、辺3彩色に於いてグラフの本質的な部分は全て、掃き出されて残った(v+1)行(v-1)列行列に集約される。この各行を多項式と考えれば、各列に割り当てられた(v-1)個の変数と各行(v+1)個の多項式の総積が(式として)恒等的に零でなければ、必ず辺3彩色可能である事が示される。つまり四色定理が証明されるというわけである。

この多項式の積の一般的な形を求めるのは複雑すぎてまず不可能と思われるので、対象を平面グラフに限定して、数学的帰納法を使う必要がある(このあたりの議論は次回に譲る)。

面頂点行列は、平面グラフに於いては、一つの列に零でない成分が必ず二つか三つある:二つになるのは平面グラフに於いては(例えば)最も外側にある頂点、つまり外周部分の頂点であり、それ以外の列はちょうど三つの零でない成分がある。各行はどう表現しても必ずサイクルに対応するため、例えば二辺国の場合は零でない成分がちょうど2個ある行となる。辺頂点行列と違い、サイクルにならないような表現は面頂点行列では存在しない。