うさぎでもわかる離散数学（グラフ理論） 第19羽 彩色問題（地図を塗り分けてみよう！）

０．はじめに 彩色問題は点彩色（頂点を塗り分けていく）と辺彩色（辺を塗り分けていく）の2つにわかれます。 今回は点彩色、辺彩色の両方についてまとめていきます。 後ほど説明しますが、下のような地図を塗り分ける問題は点彩色を用いることで解くことができます。 考えてみよう！ 何色あれば上の地図（近畿地方）を府県ごとに色分けすることができるでしょうか？ スポンサードリンク １．点彩色 (1) 点彩色とは 隣り合うどの2点も異なる色になるようにグラフの頂点を色わけすることを点彩色といいます。（頂点彩色、もしくは単に彩色とも呼ばれることもあります。 ） 例えば左側のグラフは隣り合うどの2点も異なる色に色分けしているので点彩色となっていますが、右側のグラフは隣同士を同じ色に色分けしてしまっているので点彩色ではありません。 (2) n-頂点彩色 あるグラフを \( n \) 色で彩色することを、n-頂点彩