五色定理

五色定理とは

五色定理は、与えられた平面図形を5色以下で彩色できることを示す数学的な定理です。具体的には、隣接する領域が同じ色を持たないように領域を塗り分けることができるというものです。この理論は、地図のような平面上の領域に適用され、特に政治地図などで、州や郡の区分を表現するのに用いられます。

定理の背景

この定理は、より強力な四色定理の一部とされています。五色定理自体の証明は比較的簡単であり、1879年に数学者アルフレッド・ケンプが四色定理の証明に失敗した際のアプローチに基づいています。その後、数学者パーシー・ジョン・ヒーウッドが約11年後にケンプの誤りを発見し、その結果として五色定理を証明しました。

証明の概要

五色定理の証明は、与えられた地図から単純平面グラフを構築することから始まります。このグラフの頂点は地図の各領域を表し、隣接する領域間には辺が引かれます。こうして、問題は「各頂点に色を塗って、辺で結ばれた二つの頂点が異なる色になるようにできるか」という彩色問題に変換されます。

このグラフが単純平面グラフであるため、オイラー標数を利用して、グラフの頂点には最大で5本の辺しか接続されていないことを示すことができます。この特長を利用して、ある頂点を選び、それをグラフから取り除くことで、新たなグラフに対しても五色で彩色できることを示します。

ここで、取り除いた頂点をvとし、このvと隣接する他の5つの頂点、すなわちv1, v2, v3, v4, v5を設定します。もしこれらの頂点が異なる5色で彩色されていなければ、vを塗る色は未使用のものになります。

もしv1とv3など、色が同じ場合、これらの連結成分を通じてvが塗れる別の色を見つけることができる可能性が起きます。このように、グラフの各部分から得られる情報を使いながら色を塗り分ける方法が示されます。

計算アルゴリズム

1996年には、Robertson、Sanders、Seymour、Thomasの研究により、単純平面グラフを線形時間で五色に彩色するアルゴリズムが提案されました。具体的には、次数が4以下の頂点を削除し、その色に応じて再帰的にグラフの彩色を行う手法です。これにより、頂点の次数が5または6である場合も、適切な色を選ぶことで彩色が可能になります。

まとめ

五色定理は、平面の地図に対する重要な理論であり、隣接する領域が異なる色で塗られることを示しています。この定理の証明は、数学の重層的なアプローチと証明技法の面白さを示す一例です。数学の世界での色彩に関する問題は、単なる遊びではなく、深い理論的背景を持つことが分かります。

もう一度検索