12.6 彩色
第 12.2 節では、グラフの辺を使って頂点間の親密な関係を表現した。これとは対照的に、頂点同士が衝突する関係を辺で表現することもできる。典型的な例として試験のスケジュール作成がある。
12.6.1 試験のスケジュール作成問題
タームごとに、MIT のスケジュール管理課は期末試験の時間を各講義に割り当てる。これは簡単な仕事ではない: 期末試験のある講義を複数取る学生がいる上に、特定の時間に一人の学生が受験できる期末試験は (MIT の学生であっても) 一つだけだからである。スケジュール管理課は全ての衝突を避けなければならない。もちろん、全ての期末試験を異なる時間にスケジュールすれば衝突は避けられるものの、講義は数百個あるので、そうすると期末試験を一年中実施することになってしまう！ よって、スケジュール管理課には期末試験の期間を短くすることも求められる。
この問題はグラフで簡単に表現できる。このグラフの頂点は期末試験がある講義を表し、辺は端点の講義を両方受講する学生がいる (そのため同じ時間に期末試験を実施できない) 事実を表す。例えば、講義 \(6.041\), \(6.042\), \(6.002\), \(6.003\), \(6.170\) のスケジュール作成問題を表すグラフは図 \(\text{12.11}\) のようになるかもしれない。
このグラフからは、例えば \(6.002\) と \(6.042\) の両方を受講する生徒がいるので期末試験を同時刻に実施できないと分かる。一方で、\(6.042\) と \(6.170\) の両方を受講する生徒はいないので期末試験は同時刻に実施できる。
続いて、期末試験を実施できる時間帯にそれぞれ色を割り当てる。例えば「月曜の午前」は赤、「月曜の午後」は青、「火曜の午前」は緑、などとする。こうすると、講義に対する時間帯の割り当てはグラフの頂点に対する色の割り当てに等しくなる。さらに、「一部の期末試験は同時に実施できない」という制約は「グラフで隣接する頂点は異なる色を持つ必要がある」という制約に等しくなる。そして、試験期間を短くするには可能な限り少ない色を使ってグラフに色を塗ればよい。\(3\) 個の色を使った制約を満たす色の割り当てを図 \(\text{12.12}\) に示す。
この色の割り当ては、月曜の午前に \(1\) 個 (赤い科目)、月曜の午後に \(2\) 個 (青い科目)、火曜の午前に \(2\) 個 (緑色の科目) の期末試験をそれぞれ実施するスケジュールに対応する。\(2\) 種類以下の色だけで頂点に色を塗れるだろうか？ それはできない！ グラフには三角形が含まれ、その三角形を構成する三つの頂点には異なる色を塗る必要がある。
これはグラフの彩色 (coloring) と呼ばれる問題の例である: グラフ \(G\) に対して、辺で隣接する二頂点が同じ色にならないように全ての頂点に色を割り当てる問題を言う。この条件を満たす色の割り当てを正当な彩色 (valid coloring) と呼ぶ ── 略して彩色 (coloring) とも呼ぶ。\(k\) 種類以下の色を使った彩色を持つグラフは \(k\)-彩色可能 (\(k\)-colorable) と呼ばれる。
グラフ \(G\) が \(k\) 種類の色を使った彩色を持つような \(k\) の最小値を \(G\) の彩色数 (chromatic number) と呼び、\(\chi(G)\) と表記する。
この定義から「\(G\) が \(k\)-彩色可能」と「\(\chi(G) \leq k\)」が同値だと分かる。
12.6.2 彩色数に関連する性質
彩色数に関連する単純かつ有用なグラフの性質をいくつか示す。
そのような性質の中でおそらく最も単純なのは「閉路グラフである」だろう: 偶数個の頂点を持つ閉路グラフは \(2\)-彩色可能である。つまり、任意の正整数 \(n\) に対して次の等式が成り立つ:
一方で、奇数長閉路は \(3\) 種類の色を必要とする。つまり次の等式が成り立つ:
これとは異なる単純な性質として「完全グラフ \(K_{n}\) である」がある。任意の正整数 \(n\) に対して次の等式が成り立つ:
完全グラフでは任意の二頂点が隣接するので、どの二頂点も同じ色で塗ることができない。
「二部グラフである」も彩色可能性と密接に関連する性質である。二部グラフでは「左」にある頂点に同じ色を塗り、「右」にある頂点を異なる同一の色で塗ると正当な彩色となる。逆に、彩色数が \(2\) のグラフは頂点集合を \(2\)-彩色における色の通りに「左」と「右」に分割できるので、二部グラフである。辺を持たない唯一のグラフ ── 空グラフ ── の彩色数は \(1\) なので、次の補題を得る:
空でないグラフ \(G\) に対して「\(G\) が二部グラフ」と「\(\chi (G) = 2\)」は同値である。
また、グラフの頂点の次数が小さいなら彩色数も小さいことが言える。正確には、頂点の次数に最大値に \(1\) を加えた値は彩色数の上界になる:
頂点の次数が最大で \(n\) のグラフは \((n + 1)\)-彩色可能である。
この定理の証明は \(n\) に関する数学的帰納法を使うのではないかと思ったかもしれないが、それだと上手く行かない ── その方法による証明は著者たちも知らないので、この定理の証明を練習問題にすると一部の学生の一週間を台無しにしてしまう可能性がある。グラフに関する命題の証明で数学的帰納法を使うときは、頂点または辺の個数を利用すると詰まることなく証明できる場合が多い。定理 12.6.3 の証明では、頂点の個数に関する数学的帰納法が利用できる。
証明 グラフの頂点の個数に関する数学的帰納法で示す。\(n \in \mathbb{N}\) を固定する。次の述語を帰納法の仮定とする:
ベースケース: \(k = 1\) のとき、\(1\) 個の頂点を持つグラフは頂点の次数の最大値が \(0\) であり、\(1\)-彩色可能である。よって \(P(1)\) が成り立つ。
帰納ステップ: \(P(k)\) が成り立つと仮定する。\(k + 1\) 個の頂点を持つ、頂点の次数の最大値が \(n\) のグラフを \(G\) とする。\(G\) から任意の頂点 \(v\) と \(v\) に接続する全ての辺を除去したグラフを \(H\) とすれば、\(H\) は \(k\) 個の頂点を持つ。さらに、\(H\) の頂点の次数の最大値は高々 \(n\) なので、帰納法の仮定より \(H\) に対する \((n + 1)\)-彩色が存在する。
この \((n + 1)\)-彩色に \(v\) を加えて \(G\) に対する彩色を得ることを考える。頂点 \(v\) の次数は \(n\) 以下なので、\(v\) に隣接する頂点は \(n\) 個以下である。よって色が \(n + 1\) 種類あれば、\(v\) に隣接する頂点にどんな色が塗られていたとしても、\(v\) に隣接する頂点と異なる色を割り当てられる。つまり \(G\) の \((n + 1)\)-彩色は構築可能である。 ■
定理 12.6.3 の \(n + 1\) が彩色数に等しい場合もある。例えば完全グラフ \(K_{n+1}\) では各頂点の次数が \(n\) であり、\(\chi (K_{n+1}) = n + 1\) が成り立つ。これは定理 12.6.3 が与える上界が最良であることを示す。また、頂点の次数の最大値が \(n\) であり、かつ \(K_{n+1}\) を部分グラフとして持つ任意のグラフに対しても定理 12.6.3 は彩色数の最良の上界を与える。
一方で、\(n + 1\) より格段に少ない種類の色を使った彩色が可能な場合もある。例えば図 \(\text{12.13}\) に示すスターグラフ (star graph) は頂点の次数の最大値が \(6\) であるものの、わずか \(2\) 種類の色を使った彩色が可能である。
一般に、任意のグラフに対する最小彩色の構築は非常に難しい。次項で見るように、実は彩色数の計算さえ困難である。
12.6.3 なぜ彩色を考えるのか？
現実の課題に取り組むとき彩色問題が頻繁に姿を現す理由の一つは、衝突するスケジュールを調整する状況がよくあるからである。例えば、Tom Leighton が共同創設者の一人であるインターネット企業 Akamai は数日ごとに自社が保有するサーバー (2016 年時点で \(200{,}000\) 台以上) に新しいバージョンのソフトウェアをデプロイしている。デプロイを \(1\) 台ずつ行うと完了までに \(20\) 年以上の時間がかかるので、多くのサーバーに対する同時デプロイが欠かせない。一方で、非常に重要な基礎的機能を担うために同時に更新できないサーバーの組も存在する (デプロイ作業中にサーバーはオフラインになる)。
この問題は \(200{,}000\) 個の頂点を持つグラフで衝突を表し、そのグラフに対する十数個の色を使った彩色を構築することで解決される ── つまり、デプロイのウェーブは十数個で済む！
別の例として電波基地局に対する周波数の割り当てがある。放送エリアが重なる二つの基地局が同じ周波数を使うことはできない。一方で周波数は希少で高価なので、利用される周波数の個数を最小化する必要もある。この問題を解くには、基地局を頂点に持ち、放送エリアが重なる基地局の間に辺を持つグラフに対する最小彩色を構築すればよい。
また、一部のプログラミング言語では変数に対するレジスタ割り当てで彩色問題が利用される。プログラムが変数を利用するとき、その値をまずレジスタに読み込む必要がある。レジスタに異なる値を入れて再利用することはできるものの、使用される期間が重なる二つの変数の値は異なるレジスタに読み込む必要がある。そのためレジスタを変数に割り当てるには、頂点が変数を表し、辺が使用期間の重複を表すグラフに対する彩色問題を解けばよい (「色」がレジスタとなる)。ここでも、最小の色数でグラフを彩色することが目標となる。
最後に、本書の冒頭 (命題 1.1.4) で触れた地図の彩色問題がある: 隣接する領域の色が異なるように地図に色を塗るとき、色は何種類あれば十分だろうか？ 解答が直接的な応用を持つわけではないものの、この問題は数世紀にわたってグラフ理論の研究者を苦しめ続けた。ついに 1970 年代に「どんな地図も \(4\) 色あれば必ず塗り分けられる」ことが証明された ── 発表した研究者は大きな賛辞を受けた。その証明からは、実際に \(4\) 色で地図を塗り分ける十分に効率的な手続きも得られる。
興味深いことに「与えられた平面グラフの彩色に \(4\) 色が必要か ── それとも \(3\) 色以下で十分か ── どうかを判定する効率的な手続きが存在するか？」という問題は SAT (第 3.5 節) の変装した姿であることが分かっている。つまり \(3\)-彩色可能性の難しさを証明できれば百万ドルが手に入る。平面グラフの \(3\)-彩色可能性と SAT が同程度に難しいことの証明は問題 12.31 と問題 12.32 に示した。