グラフ彩色とパス表現

無向グラフについて、k色のうちいずれかをそれぞれの頂点に割り当てたとき、全ての辺の両端が異なる色ならばそのグラフをk-彩色可能といいます。平面埋め込み可能なグラフは全て4-彩色可能というのが、有名な四色定理です。

さて各頂点がある埋込みの中の位置を表していると考えると、隣接する位置の色が異なる、つまり互いに区別できるという解釈ができます。しかし、図の左上の水色の頂点がふたつの桃色の近傍をもっているように、微小な領域での「向き」を一意に区別することはできません。

そこで、それを可能にする彩色を考えてみると、次のように表現できます。

すべての頂点について、自身とその近傍の色が全て異なる

k色でこの条件を満たせるグラフを、ここでは仮にk-追跡可能と呼ぶことにしましょう(この条件の一般的な名称を知っている方がいたら教えてもらえると嬉しいです)。また、グラフGの彩色、追跡それぞれの最小色数をχ(G)、τ(G)と書くことにします。

さて、k-追跡可能グラフの特徴をいくつか考えてみましょう。

k-彩色可能性との関係

明らかに、k-追跡可能ならばk-彩色可能です。一方その逆は成り立ちません。例えば平面グラフは任意の次数を持ち得てかつχ<=4ですが、最大次数がnのときτ>=n+1である必要があります。一般にτ>=max(χ,n+1)と言えるでしょう。

パスの表現

さてこの命名の由来ですが、k-追跡可能なとき、ある頂点の近傍は{1..k}のいずれかを用いて一意に表現できます。よって長さnの任意のパスは起点となる頂点ひとつと{1..k}^nで表せます。これはグラフ上を移動するエージェントのようなものを考えるときには有用な性質です。なぜなら、局所的にグラフを見ているときに、そのパスの表現に必要な情報量が全体の頂点数、そもそも有限か無限かにも依存しなくなるからです。(有限のτを考えているとき、辺の数=O(頂点数)となります)

格子の構成

さて頂点集合をZ^nとし、マンハッタン距離が1の二点を近傍とする格子Lnを考えてみます。次数はいたるところで2dで、座標の成分の和のパリティによって2-彩色可能です(図左)。τ(Ln)はどうなるでしょうか。

これはまず一次元の直線を考えてみるとよくわかります。各点において右と左そして自分自身を区別するのに最低三色必要で、これを座標に沿って循環的に割り当てていくと全体をカバーできます。個人的には、同期セルオートマタの非同期化( http://jsdo.it/xanxys/ascwlife )の時に、時間を三状態の「位相」で表したことが思い出されます。では、二次元の場合はどうでしょう。この場合は各軸を独立に見てそれぞれに三色を割り当てる、つまり全体では九色使うと3x3の繰り返し要素がつくれます(図右)。

同様に次元が高いLnについても、3^n色使えば充分です。つまり2n+1<=τ<=3^nとなるのですが、3^nより少ない色数で追跡可能になるかどうかはよくわかりません。