スケジューリング問題

図1 打ち合せたいペア

彩色の研究紹介をする前に、スケジューリング問題という問題を考えましょう。

会社には様々なプロジェクトがあり、複数のプロジェクトに参加している人もいます。
今、ＡさんとＢさんが打ち合わせをしたいのですが、ＡさんはＣさんとも打ち合わせをしなくてはなりません。
同様に、ＢさんはＣさんともＤさんとも打ち合わせをしたいですし、ＣさんはＤさんと打ち合わせをしたいです。
つまり、打ち合わせをしたいペアを挙げると、

（Ａ，Ｂ）（Ａ，Ｃ）（Ｂ，Ｃ）（Ｂ，Ｄ）（Ｃ，Ｄ）

となります。

図2 スケジューリング

では、この４人が全ての打ち合わせを終了し、早く帰宅するためにはどのようにスケジュールを組めばよいでしょう？
ただし、各ペアの打ち合わせはちょうど１時間かかるものとします。

スケジュールを考えましょう。
まず１時間目に（Ａ，Ｂ）ペアの打ち合わせをすると、その間ＡさんとＢさんが入っているペア（Ａ，Ｃ）（Ｂ，Ｃ）（Ｂ、Ｄ）は打ち合わせをすることができません。しかし、ＡさんもＢさんも入っていないペア（Ｃ，Ｄ）は同時刻に打ち合わせをすることができます。
２時間目に（Ａ，Ｃ）ペアが打ち合わせをすると、先ほどと同じように同時刻に打ち合わせができるのは（Ｂ，Ｄ）ペアだけになります。
そして、最後の３時間目に、残った（Ｂ，Ｃ）ペアの打ち合わせをします。

スケジューリング問題とグラフ

さて、ここまでの話をもっとわかりやすくできないでしょうか？今の例では人数が４人ですから、先ほどのようになんとか手作業でスケジュールを組むことができます。しかし、人数が１００人、１０００人と膨れ上がってきたら… そこで登場するのがグラフであり、その理論の中でも彩色問題であるのです。

図3 グラフの例 図4 グラフとスケジューリング問題の対応

グラフとは、点集合と辺集合で定義されるものです。 例えば、下の図1を見てください。ここで｛v1, v2, v3, v4}は点集合と呼ばれ、{e1, e2, e3, e4, e5}は辺集合と呼ばれます。

実はこのグラフ、先ほどのスケジューリング問題に対応させることができるのです。下の図2のように、Ａさんを点v1に対応させ、同様にＢさんを点v2に、Ｃさんを点v3に、Ｄさんを点v4に対応させます。すると、先ほどの打ち合わせのペアは、

（Ａ，Ｂ）⇔ e1
（Ａ，Ｃ）⇔ e2
（Ｂ，Ｃ）⇔ e3
（Ｂ，Ｄ）⇔ e4
（Ｃ，Ｄ）⇔ e5

というように、グラフの各辺に対応させることができるのです。

では、グラフ上でスケジュールはどのように立てればよいのでしょうか？そこで登場するのが、辺彩色という問題です。

様々な彩色問題

点彩色

図6 点彩色の例

グラフの点に色を割当てます。ただし、辺で結ばれている２点は異なる色になるように割当てます。例えば、下のグラフで点v2と辺で結ばれている点v1，v3，v4は、赤と異なる色で塗られています。その一方で、辺で結ばれていない点v1とv4は同じ色（緑）で塗られています。もちろん、v1とv4は異なる色で塗られていても構いません。

全彩色

図7 全彩色の例

これは上記の点彩色と辺彩色を組合わせたような彩色です。辺で結ばれている点同士、同じ点に繋がっている辺同士、さらに繋がっている点と辺が異なる色になるように色を割当てます。例えば、下のグラフで点v2に注目すると、v2と辺で結ばれている点v1，v3，v4は紫と異なる色で塗られていますし、点v2に繋がっている辺e1，e3，e4はそれぞれ異なる色で塗られており、さらにそれらの辺はv2の赤とも異なる色で塗られてます。

この他にも様々な彩色問題が研究されています。私たちは、その中のいくつかに注目し研究しています。