再読み込みするとランダムに頂点を作り直して彩色します。ソースは VertexColoringApplet.java。
頂点に色をぬります。ただし枝で結ばれている、隣り合った頂点とは 違う色でぬらなければならないとき、できるだけ少ない色でぬりたいのだが、 色は最低何色必要でしょうか? という問題です。最適解を求めるのは頂点の数が 多くなると難しいことが知られています。
講義で例に挙げられていた現実的な問題としては、携帯電話のアンテナの 周波数割り当て問題。携帯電話のアンテナには固有の周波数が割り当てられ、 そのおかげで同時に複数の携帯電話が使われてもそれぞれ異なる周波数を 使用していれば混信しないようになっているのですが、使える周波数には 限りがあるので全てのアンテナに違う周波数を割り当てるわけにもいきません。 考えてみると、十分遠くにあるアンテナ同士は混信することもないので、全ての アンテナに違う周波数を割り当てるのは無駄とも言えます。なので、距離が近い アンテナ同士は必ず違う周波数を割り当てておきさえすればよい、ということに なります。これはアンテナを頂点、周波数を色とすれば、上の頂点彩色問題に 置き換わることがわかるでしょうか? このように、頂点彩色問題を解くことに 変換(帰着)できる多くの問題があるので、頂点彩色問題は重要な問題の1つです。
ちなみに上のプログラムのアルゴリズムは結構簡単です。頂点にぬる色を 0、1、2……と番号でつけていくことにして、必要な番号が少なければよいと 考えましょう。左から頂点を順にスキャンしていきます。頂点を見つけたら、 それより左にある頂点と枝で結ばれているか調べ、そことは番号がかぶらない ように、かつできるだけ小さい色番号をつけていきます。これを右端まで 続けるだけです。このアルゴリズムは最適解を見つけられるとは限りませんが、 最適解の3倍以下の色数でぬれることがわかっています(3近似という)。