MathLabs

組合せ論と離散数学

グラフ彩色と四色定理

隣接するものが異なる色になるよう頂点や領域に色を割り当てること。すべての平面地図は4色で塗り分けられる。

直観直感的なイメージ:地図の彩色

隣り合う国が必ず異なる色になるように、政治地図上の国々に色を塗ることを想像してほしい。これがまさにグラフ彩色問題である。各地域を頂点にし、二つの地域が隣接するたびに二つの頂点を辺で結ぶ。正当な彩色とは、すべての辺の両端が必ず異なる色になるように各頂点に色を割り当てることである。これを可能にする最小の色数を彩色数と呼び、χ(G)\chi(G) と書く。

隣接する頂点が異なる色になるよう4色で彩色された頂点を示すグラフネットワークウィジェット。
有効な4彩色を施した平面地図グラフ:隣接する領域は同じ色にならない。

中高正当な彩色と彩色数

定義: 正当な彩色、彩色数

グラフ GG の正当な kk 彩色とは、隣接するどの二頂点も同じ色にならないように、各頂点に kk 色のうちの一つを割り当てる関数である。彩色数 χ(G)\chi(G) は、正当な kk 彩色が存在する最小の kk である。同様に、χ(G)\chi(G) は V(G)V(G) 全体を分割するのに必要な独立集合(互いに隣接しない頂点の集合)の最小個数でもある。

χ(G)=min⁡{k∈N:G is properly k-colorable}\chi(G) = \min\{k \in \mathbb{N} : G \text{ is properly } k\text{-colorable}\}

ここで kk は自然数全体を動き、GG は彩色対象のグラフ、χ(G)\chi(G) はその結果としての最小値である。使いやすい上界は貪欲アルゴリズムから得られる:頂点を任意の順に並べ、各頂点にそれ以前の隣接頂点がまだ使っていない最初の色を割り当てる。どの頂点も隣接頂点は高々 Δ(G)\Delta(G) 個しかないので、この方法は Δ(G)\Delta(G) + 1 色を超えて必要とすることはなく、χ(G)≤Δ(G)+1\chi(G) \le \Delta(G) + 1 が得られる。

χ(G)≤Δ(G)+1\chi(G) \le \Delta(G) + 1
よく使われるグラフ族の彩色数と彩色多項式
グラフ族彩色数彩色多項式
完全グラフ KnK_nnnP(Kn,k)=k(k−1)(k−2)⋯(k−n+1)P(K_n,k) = k(k-1)(k-2)\cdots(k-n+1)
nn 頂点の木 TT22 (n≥2n \ge 2 のとき)P(T,k)=k(k−1)n−1P(T,k) = k(k-1)^{n-1}
nn が奇数のサイクル CnC_n33P(Cn,k)=(k−1)n+(−1)n(k−1)P(C_n,k) = (k-1)^n + (-1)^n(k-1)
任意の平面グラフ高々 44(四色定理)一般には閉じた式がない

大学彩色多項式

彩色数だけでなく、GG の正当な kk 彩色の個数そのものを正確に数えることもできる。この個数は kk に関する多項式であり、彩色多項式 P(G,k)P(G,k) と呼ばれる。これは削除・縮約の漸化式を満たす:GG の任意の辺 ee を選び、それを削除して G−eG-e を得るか、あるいは縮約(両端点を一つにまとめる)して G/eG/e を得ると、P(G,k)=P(G−e,k)−P(G/e,k)P(G,k) = P(G-e,k) - P(G/e,k) が成り立つ。完全グラフ KnK_n では、すべての頂点が異なる色を持たねばならないので P(Kn,k)=k(k−1)(k−2)⋯(k−n+1)P(K_n,k) = k(k-1)(k-2)\cdots(k-n+1) となる。nn 頂点の木 TT については、漸化式より P(T,k)=k(k−1)n−1P(T,k) = k(k-1)^{n-1} が得られる。最初の頂点は kk 色のいずれでもよく、以降の各頂点(一本の辺で接続)は親の色以外ならどれでもよいからである。

P(G,k)=P(G−e,k)−P(G/e,k)P(G,k) = P(G-e,k) - P(G/e,k)
P(Kn,k)=k(k−1)(k−2)⋯(k−n+1)P(K_n,k) = k(k-1)(k-2)\cdots(k-n+1)

大学重要な定理

定理: 五色定理

任意の平面グラフ GG は χ(G)≤5\chi(G) \le 5 を満たす。

なぜ正しいのか?

これは四色定理へのはるかに易しい準備運動であり、初等的な帰納法と局所的な色の入れ替え(ケンペ鎖)という巧妙な手法だけを用い、コンピュータの助けを必要としないため、読者はすべての手順を手で検証できる。

証明

基底段階。GG の頂点数が5以下なら、各頂点に異なる色を与える。使う色は高々5色なので主張は成り立つ。

帰納段階の準備。頂点数が nn 未満の任意の平面グラフが5彩色可能であると仮定し、GG を nn 頂点の平面グラフとする。任意の単純平面グラフは E≤3V−6E \le 3V - 6 を満たす(この辺数の上界はオイラーの公式から証明される)ので、次数の総和は高々 2(3n−6)=6n−122(3n-6) = 6n-12、すなわち 6n6n より小さい。したがって平均次数は6未満であり、次数が高々5であるような頂点 vv が存在する。

vv を除くと n−1n-1 頂点のより小さな平面グラフが得られ、帰納法の仮定によりそれは正当な5彩色を持つ。vv の隣接頂点が高々4個であれば、それらは高々4色しか使っていないので、vv に使える色が一つ残り、証明が終わる。

残る場合は deg(v)=5(v) = 5 であり、vv の5個の隣接頂点にちょうど1回ずつ5色すべてが現れる場合である。平面上の描画で vv の周りに現れる巡回順に隣接頂点を第一、第二、第三、第四、第五と呼び、それぞれ色1、2、3、4、5が塗られているとする。色1または3の頂点全体からなる部分グラフ H1,3H_{1,3} を考える。第一の頂点と第三の頂点が H1,3H_{1,3} の異なる連結成分にあるなら、第一の頂点を含む成分全体で色1と3を入れ替える。これは色1または3の頂点にしか触れないので正当な彩色のままであり、第一の頂点は今や色3となるため、色1が vv に使える。

そうでなければ第一の頂点と第三の頂点は H1,3H_{1,3} の同じ連結成分にあり、色1と3が交互に現れる道で結ばれている。この道は vv および第一・第三の頂点への二本の辺とともに、平面内で閉曲線をなし、(ジョルダン曲線定理により、vv の周りの巡回順が第一、第二、第三、第四、第五であることから)第二の頂点と第四の頂点を分離する。したがって色2と4が交互に現れる道は第二の頂点と第四の頂点を結ぶことができない。なぜならそのような道は色1-3の閉曲線を横切らねばならないからである。そこで第二の頂点を含む H2,4H_{2,4} の成分全体で色2と4を入れ替える。これにより色2が vv に使えるようになる。

いずれの場合も vv はどの隣接頂点とも衝突せずに5色のうちの一つを受け取り、GG-v の彩色を GG 全体に拡張できる。帰納法により、任意の平面グラフについて χ(G)≤5\chi(G) \le 5 が成り立つ。

定理: 四色定理

任意の平面グラフ GG は χ(G)≤4\chi(G) \le 4 を満たす。

なぜ正しいのか?

これは1852年にフランシス・ガスリーが提起した元々の地図彩色問題への答えである。任意の平面地図には常に4色で十分であり、この上界は最良である。実際、互いにすべて隣接する4つの領域を持つ地図のような平面グラフは本当に4色すべてを必要とする。

証明

最小反例への帰着。もし定理が偽であれば、5色以上を必要とする平面グラフのうち頂点数が最小のものを取る。平面性を保ったまま辺を追加すると必要な色数は増えることはあっても減ることはないので、この最小反例は極大平面グラフ(三角形分割)であるとしてよく、そこでは外側の面も含めすべての面がちょうど3辺で囲まれている。

放電法の準備。各頂点 vv に初期電荷 6−deg⁡(v)6 - \deg(v) を割り当てる。V−E+F=2V - E + F = 2 と 2E=∑vdeg⁡(v)2E = \sum_v \deg(v) および 3F≤2E3F \le 2E(各面は少なくとも3辺を持つ)を組み合わせると、すべての頂点にわたる電荷の総和はちょうど 1212 になり、したがって厳密に正である。放電法はその後、固定された規則に従って隣接する頂点の間で局所的に電荷を移動させ、総和は変えない。放電後にどこに正の電荷が残らざるを得ないかを解析すると、グラフのどこかに、低次数の頂点とその特定の近傍パターンが必ず現れることが分かる。これら有限個のパターンを不可避配置と呼ぶ。なぜなら、任意の平面三角形分割には少なくとも一つが必ず現れるからである。

被約性。ある配置が被約であるとは、それが仮定上の最小反例の中に現れるとき、その配置を除去または縮約して得られる小さいグラフのどんな4彩色も、必ず全体のグラフの4彩色へと再び拡張できることをいい、これは最小性と矛盾する。AppelとHakenは1976年、1,936個の不可避配置からなる彼らのリスト(後に1997年にRobertson、Sanders、Seymour、Thomasにより633個へ整理された)のすべてが被約であることを、1000時間を優に超える計算機時間を用いて計算機的に検証した。これにより四色定理は、証明が本質的に計算機による検証に依拠した最初の大定理となり、その後独立に再検証され、2005年にはGonthierによってCoq証明支援系の中で一行ずつ形式的に検証された。

結論。すべての不可避配置が被約であるため、最小反例は存在しえない。すなわちどの平面グラフも5色以上を必要とせず、したがって任意の平面グラフ GG について χ(G)≤4\chi(G) \le 4 が成り立つ。

大学実世界での応用と具体例

グラフ彩色は、互いに衝突するために分離しなければならない作業と、衝突しないため資源を共有できる作業がある状況で常に現れる。コンパイラはこれを使って限られた数のCPUレジスタをプログラム変数に割り当てる(レジスタ割り当て):同じ時点で共に「生きている」二つの変数には辺を張り、正当なレジスタ割り当てはまさに正当な彩色である。大学はこれを使って期末試験の日程を組む:同じ学生が受講する二つの科目には辺を張り、必要な最小の試験時限数はその衝突グラフの彩色数である。無線ネットワークはこれを使って送信機に電波周波数を割り当て、近くにある(干渉し合う)送信機同士が同じ周波数を共有しないようにする。

例: 4個の一時変数へのレジスタ割り当て

コンパイラがループ内で4つの一時変数 a,b,c,da, b, c, d を管理しているとする。それらの生存区間は次のように重なる:aa は bb、cc と重なる;bb は aa、cc、dd と重なる;cc は aa、bb、dd と重なる;dd は bb、cc とのみ重なる。衝突グラフを作り、必要なCPUレジスタの最小数を求めよ。

解答

グラフを作る。頂点は a,b,c,da, b, c, d;辺は ab,ac,bc,bd,cdab, ac, bc, bd, cd(挙げた重なりから)であり、aa と dd は決して重ならないので辺 adad はない。

三角形を探す。頂点 a,b,ca, b, c は互いに隣接している(abab、acac、bcbc がすべて存在)ので、このグラフには三角形が含まれ、少なくとも3個のレジスタが必要である:2色ではどんな2彩色も互いに隣接する3頂点のうち2つを同じ色にせざるを得ないため、三角形を正当に彩色することは決してできない。

3色(レジスタ)1,2,31, 2, 3 を試す。a=1a=1、b=2b=2、c=3c=3 とする(三角形をなすため互いに異なることが強制される)。次に dd を調べる:dd は bb(色2)と cc(色3)に隣接するが aa には隣接しないので、dd は安全に色1を取れる。

結論。彩色 a=1,b=2,c=3,d=1a=1, b=2, c=3, d=1 は正当であり、3個のレジスタで十分であり、三角形 {a,b,c}\{a,b,c\} があるため3個は必要でもある。必要なレジスタの最小数は3である。

例: できるだけ少ない試験時限での試験日程

ある大学は5つの科目 1,2,3,4,51, 2, 3, 4, 5 を開講している。いくつかの組は少なくとも一人の履修学生を共有しており、同時に試験できない:組 (1,2)(1,2)、(1,3)(1,3)、(2,3)(2,3)、(2,4)(2,4)、(3,4)(3,4)、(4,5)(4,5) が衝突し、他のすべての組は共通の学生を持たない。どの学生も二つの試験を同時に受けずに済むために必要な最小の試験時限数を求めよ。

解答

グラフとしてモデル化する。頂点 1,2,3,4,51,2,3,4,5 は科目であり、衝突する各組に辺を引く:12,13,23,24,34,4512, 13, 23, 24, 34, 45。必要な最小の試験時限数は、まさにこの衝突グラフの χ(G)\chi(G) に等しい。なぜなら二つの科目が時限を共有できるのは隣接していないときに限るからである。

下界を求める。頂点 1,2,31, 2, 3 は互いに隣接している(12,13,2312, 13, 23 がすべて存在)ので三角形をなす;どの三角形でも2色では足りないので、少なくとも3時限が必要である。

3時限を試す。科目 11 を時限A、科目 22 を時限B、科目 33 を時限C に割り当てる(三角形のため互いに異なることが強制される)。科目 44 は 22(時限B)と 33(時限C)に衝突するが 11 には衝突しないので、科目 44 は時限Aに入れられる。科目 55 は 44(時限A)にのみ衝突するので、科目 55 は時限B(またはC)に入れられる。

結論。時限A ={1,4}= \{1, 4\}、時限B ={2,5}= \{2, 5\}、時限C ={3}= \{3\} は衝突のない有効な日程であり、三角形 {1,2,3}\{1,2,3\} があるため3が最適である。したがって3個の試験時限が必要かつ十分である。

5頂点の完全グラフ K5K_5 の彩色数 χ(G)\chi(G) はいくつか。

グラフ GG の最大次数が Δ(G)\Delta(G) =4= 4 であるとする。貪欲彩色の境界が保証する χ(G)\chi(G) の上界はいくつか。

AppelとHakenが、何千もの不可避配置をコンピュータで検証することに依拠した四色定理の最初の証明を発表したのは何年か。

ある大学が試験の衝突をグラフ GG としてモデル化する:各科目が頂点であり、両方を履修する学生がいるときに二つの科目を辺で結ぶ。可能な最小の試験時限数は何に等しいか。

参考文献

  1. Kenneth Appel, Wolfgang Haken (1977). Every Planar Map Is Four Colorable, Part I: Discharging
  2. Neil Robertson, Daniel P. Sanders, Paul Seymour, Robin Thomas (1997). The Four-Colour Theorem
  3. Georges Gonthier (2008). Formal Proof—The Four-Color Theorem
  4. Reinhard Diestel (2017). Graph Theory