読者です 読者をやめる 読者になる 読者になる

まっどさいえんちすと

日本語が苦手なのでブログで練習します。パエリアが大好き

4色問題-離散数学のすすめ-グラフマイナー(1)

4色問題というのに興味ありませんか?笑

これは、どんな地図も隣接して領域が異なる色になるように塗るためには4色で十分である。

というものです。

この問題はイギリスの法科学生フランシス・ガスリーにより定式化されました。アプローチとして、離散数学の、グラフマイナー理論というものが非常に面白いです。

ただこのグラフマイナー理論は、知る限り相当難しい内容や手法です。

なので、小学生に教えるように一個ずつ生きます。

 

まず4色定理をグラフ理論に置き換えてみましょう。

東京都なら、大田区、荒川区、新宿区、渋谷区を点で現したときに、線で結びます。

平面グラフとそれを呼びます。

 

平面グラフの特徴は

1:頂点を取り除く

2:辺を取り除く

3:辺を縮約する

 

という作業を行っても、どんな平面グラフでもグラフの性質は変わらない。というものです。

(辺を縮約するとは、その辺の両端を同一化すること)

 

このような操作をしても平面グラフが性質を保つことを

「マイナー操作に閉じている」といいます。

 

さてここで4色問題は以下のように言い換えられます。

「隣接している頂点同士が異なる色になるように平面グラフを彩色するには、4色で十分である」

 

ここで新しい定理を代入します。クラトスキーの定理です。

「与えられたグラフGが平面グラフである必要十分条件は、GがK33とK5をマイナーとして含まないことである。」

 

さて何のことやら・・・

それは次の回で