gm learning

頂点の色分け

　ここでは，頂点の色分けを考えます．その色分けの条件は次のとおりです．

条件：　辺で結ばれている頂点は異なる色で塗る．

この条件を満たすように，頂点に色を割り当てることを，グラフの頂点彩色と言います．

　下のアプレットでは，その頂点彩色の実験ができます．まず，適当にグラフを描いてから，[自動]ボタンをクリックしてください．すると，頂点彩色の条件を満たすように，頂点が自動的に色分けされます．

　色の違いがわかりにくければ， 色番号のチェックボックスをチェックしてください．すると，色を区別する番号が表示されます．

　頂点が色分けされたとことで，同じ色の頂点を辺で結んでみましょう．その状態では，頂点彩色の条件を満たしていませんね．

　そこで，[判定]ボタンをクリックしてみましょう．すると，条件を満たしていない頂点が白抜きになってマークされます．そのマークされた頂点に，条件を満たすように，違う色を塗りましょう．

　頂点に色を塗るときには， 頂点彩色のチェックボックスをチェックします．すると，グラフを作成する機能が停止されて，色選択ができるパレットが現れます．好きな色をクリックしてから，頂点をクリックすると，頂点がその色になります．

　ただし，黒は色のうちではありません．頂点を黒くすると，色が塗られていないものとして，彩色条件を判定します．

＊　パレットがブラウザの裏に行ってしまって，隠れていることもあるので，注意してください．

　さて，頂点彩色を考える上で問題になるのは，彩色に使われた色の個数です．

　頂点をすべて違う色で塗ってしまえば，彩色の条件を満たすのは明らかです．そういうふうに無駄に色を使わないように工夫して色分けをするとしたら，最低，何色で色分けできるでしょうか？

　その必要な最低の色数をグラフの染色数と言います．