用語集

左側のキーワードの1つを選択…

マップのカラーリング

読書の時間: ~10 min
このページは自動翻訳されているため、エラーが含まれている可能性があります。翻訳のレビューをご希望の場合はご連絡ください。

特定のマップですでにグラフ理論を使用しています。ズームアウトすると、個々の道路や橋が消え、代わりに国全体の概要が表示されます。

マップ、または個別の地域で構成されるその他の図面に色を付ける場合、隣接する国を同じ色にすることはできません。また、できるだけ少ない色を使用することもできます。

チェス盤のようないくつかの単純な「マップ」は2色(黒と白)しか必要としませんが、ほとんどの複雑なマップはそれ以上必要です。

米国の州の地図に色を付ける場合、50色で十分ですが、必要な色ははるかに少なくなります。以下のマップをできるだけ少ない色で着色してみてください。

United States

0 colours used

South America

0 colours used

Germany

0 colours used

England

0 colours used

これらのマップはすべて4つの異なる色で着色できますが、他の非常に複雑なマップではさらに多くの色が必要になる可能性があることは想像に難くありません。実際、一部のマップには、4つの国がすべて相互に接続されている場合、少なくとも 4つの色が必要です。

以前と同様に、国と国境を含むマップを平面グラフに変換できます。すべての国が 、およびがエッジで接続されている:

次に、グラフの頂点に色を付けます。2つの頂点がエッジで接続されている場合、それらの頂点は異なる色でなければなりません。

1852年、植物学の学生であるフランシスガスリーは、イングランドの郡の地図に色を付ける必要がありました。彼が試したどのマップでも4色で十分であるように見えましたが、 _すべての_マップで機能する証拠を見つけることができませんでした。これは非常に困難な問題であることが判明し、 4色の定理として知られるようになりました。

その後の100年の間に、多くの数学者は4色の定理に「証明」を発表しましたが、後で間違いが見つかるだけでした。これらの無効な証明の一部は説得力があり、エラーの発見に10年以上かかりました。

長い間、数学者たちは4色で十分であることを証明することも、4色以上を必要とするマップを見つけることもできませんでした。

ウォルフガングハーケンケネスアペルが最終的にそれを解決するためにコンピューターを使用した1976年まで、4色の問題はほとんど進歩しませんでした。彼らは無限に多くの可能な地図を1936の特別な場合に削減しました、それらはそれぞれ合計で1000時間以上かかるコンピュータによってチェックされました。

4色の定理は、コンピュータを使用して証明された最初のよく知られている数学的定理であり、それはずっと一般的になり、論争の余地が少なくなっています。より高速なコンピュータとより効率的なアルゴリズムは、今日、ラップトップで4色の定理をほんの数時間で証明できることを意味します。

Postmark for the Department of Mathematics at the University of
Illinois Urbana-Champaign, where Haken and Appel worked.

4色の定理は、平面または球体上のマップでのみ機能し、すべての国が単一のエリアで構成されています。

ただし、数学者は、国が複数の切り離されたコンポーネントで構成できる_帝国の_地図や、トーラス(ドーナツの形)などの異なる形状の惑星の地図も見てきました。これらの場合、4色以上が必要になる場合があり、プルーフはさらに難しくなります。

This map on a torus requires seven colours.

Archie