グラフ彩色とは、通常 頂点彩色 を意味します。各頂点に色を割り当て、隣接する頂点どうしが同じ色にならないようにします。この条件を満たすのに必要な最小の色数を 彩色数 といい、 と書きます。
直感的に言えば、色は「衝突しないラベル」です。2つの頂点の間に辺がないときに限って、その2頂点は同じ色を使えます。
1分でわかるグラフ彩色の定義
適切な彩色では、すべての辺が異なる色の2頂点を結びます。ルールはそれだけです。
したがって なら、次の2つが同時に成り立ちます。
- 色での適切な彩色が存在する
- 色だけでは適切な彩色が存在しない
だから彩色数は、たまたま1つの図で使った色数ではなく、最小値なのです。
特に断りがなければ、初学者向けの授業でいうグラフ彩色は、単純無向グラフの 頂点 を彩色することを指します。辺彩色は、ルールの異なる別の問題です。
彩色数が本当に測っているもの
色の名前自体は重要ではありません。赤・青・緑でも、 というラベルでもかまいません。
重要なのはグループ分けです。同じ色の頂点全体は、内部に辺を持たない集合になります。つまり、そのグループ内には衝突がありません。
この見方が、グラフ彩色をスケジューリングや資源割り当ての問題で役立つものにしています。1つの色はしばしば「これらの項目は同じ枠を共有できる」という意味になります。
例題：5-サイクルに3色必要な理由
辺 および をもつサイクルグラフ を考えます。
まず 色で試してみます。 に色 、 に色 を与えると、サイクルに沿って彩色は次のように決まっていきます。
ここで を見ます。 は と の両方に隣接しています。したがって、 があるので色 は使えず、 があるので色 も使えません。
つまり、 色では失敗します。
しかし 色なら可能です。適切な彩色の1つは
なので、
となります。
この例は覚えておく価値があります。なぜなら、サイクルグラフについての重要なパターンを示しているからです。偶数サイクルは 色で彩色できますが、奇数サイクルには 色必要です。
小さなグラフで彩色を考える方法
役立つ簡単な確認が2つあります。
1つ目は、避けられない衝突を探すことです。上の例では、奇数サイクルに沿って2色を交互に割り当てると、最後の頂点が使える2色のどちらとも衝突してしまいます。
2つ目は、下界を探すことです。グラフに三角形が含まれていれば、その3頂点は互いに隣接しているので、すでに 色が必要です。これで常に正確な答えが出るわけではありませんが、彩色数が少なくとも であることは示せます。
グラフ彩色の問題でよくある間違い
よくある間違いの1つは、図で近くに描かれているというだけで頂点が隣接していると思い込むことです。彩色の制約を生むのは、実際に辺がある場合だけです。
もう1つの間違いは、すべての頂点に別々の色が必要だと思うことです。隣接していない頂点は同じ色を再利用でき、効率のよい彩色では通常できるだけ色を再利用します。
また、頂点彩色と辺彩色を混同することもあります。このページでのルールは、隣接する 頂点 についてのものであり、隣接する辺についてではありません。
最後によくあるのは、必要最小色数ではなく、たまたま使った色数を答えてしまうことです。あるグラフを 色で彩色できたとしても、それだけで彩色数が だとは言えません。
グラフ彩色はどこで使われるか
代表的な応用はスケジューリングです。各頂点を試験とし、辺が「2つの試験に共通の受験者がいて同時に実施できない」ことを表すとします。このとき、1つの色は1つの時間枠を表せます。
このモデルでは、彩色数が必要な時間枠の最小数を教えてくれます。もし なら、 枠だけで有効なスケジュールを作ることはできません。
同じ考え方は地図の彩色にも現れます。そこでは隣り合う地域は異なる色でなければなりません。また、コンパイラ設計では、同時に必要となる変数どうしは同じレジスタを共有できません。
似たグラフ彩色の問題に挑戦してみよう
頂点 と辺 および をもつグラフを描いてみましょう。
まず三角形を見つけて下界を求めます。そのあと、できるだけ少ない色でグラフを彩色し、隣接する頂点が同じ色になっていないか確認してください。次のステップとしては、より大きなグラフで自分なりの問題を作り、その彩色が単に正しいだけでなく最小であることまで証明できるか試してみましょう。