四色定理 地図塗り分けツール
どんなに複雑な地図でも、境界を共有する国どうしが同じ色にならないように塗るには、4色あれば必ず足ります。子どもがクレヨンで試せるほど単純な命題ですが、証明には1世紀以上の年月とコンピューターが必要でした。ランダムな地図を自分で塗り、どの境界が衝突するかを確かめてから、3つの方法が塗る様子を見てみましょう。ときに5色目を必要とする手早い貪欲法のルールから、必ず4色で塗り終えるバックトラック探索まであります。 色を選び、国をクリックして塗ります。隣り合う2つの国が同じ色になると、その境界が赤くなります。角で接しているだけの国どうしは同じ色でもかまいません。コンピューターに任せることもできます。方法を選んで「解く」を押すと全体の様子を、「1ステップ」を押すと一手ずつ追って見られます。「最少色数」は、この地図が3色、あるいは2色で足りるかどうかを調べます。「新しい地図」は別の地図を描き、「隣接関係を表示」は境界を共有する国どうしのネットワークを描きます。
使い方
- 国の数を選んで「新しい地図」を押すか、表示されている地図から始めます。
- 色を選んで国をクリックして塗り、隣国どうしが衝突している赤い境界に注意します。
- 方法を選んで「解く」または「1ステップ」を押し、地図が塗られていく様子を見ます。「最少色数」を押すと、この地図に必要な色の数がわかります。
地図からグラフへ
各国に点を1つ置き、2つの国が境界を共有していれば、その2点を線で結びます。こうして地図はグラフになり、地図を塗り分けることは、結ばれた点どうしが異なる色になるように点を塗ることと同じになります。地図は平らな紙の上に描かれるので、これらのグラフは平面的、つまり線を交差させずに描くことができます。1点でだけ接する国、たとえば角で出会う4つの正方形は、隣国とはみなしません。四色定理は、すべての平面グラフが4色で塗り分けられることを述べています。「隣接関係を表示」をオンにすると、今の地図のグラフが見られます。
3つの塗り方
貪欲法による彩色は、隣国の多い国から順に1つずつ取り上げ、それぞれに隣国がまだ使っていない最初の色を割り当てます。速いものの先を見通さないため、地図によっては5色目、さらには6色目まで使ってしまいます。1979年にダニエル・ブレラーズが考案した DSATUR は、隣国にすでに最も多くの異なる色が現れている国を常に次に選ぶので、たいていはこの落とし穴を避けられます。バックトラックは色を順に試し、ある国に使える色がなくなると、直近の選択を取り消してやり直します。何度も後戻りすることはあっても、必ず4色の塗り分けを見つけます。
よくある質問
なぜ4色で必ず足りるのですか?
短い理由を見つけた人はいません。1976年のケネス・アッペルとヴォルフガング・ハーケンによる証明は、どの地図にも1936個の小さな配置のどれかが必ず含まれること、そしてそれぞれの配置は取り除いてから後で塗り分けを復元できることを示しました。そのすべてを調べるのに、コンピューターで1000時間以上かかりました。1996年にニール・ロバートソン、ダニエル・サンダース、ポール・シーモア、ロビン・トーマスが示した、よりシンプルなコンピューター証明では633個の配置で済み、2005年にはジョルジュ・ゴンティエが証明支援系 Coq で証明を完全に検証しました。
4色すべてが必要な地図はありますか?
はい。互いにほかの3つすべてと接する4つの国、たとえば1つの国を3つの国が輪のように取り囲む場合は、4色が必要です。それでも多くの地図は3色で済み、「最少色数」で画面上の地図について確かめられます。4色で必ず足りるにもかかわらず、一般にある地図が3色で塗り分けられるかどうかを判定するのは難しい問題で、NP完全です。
貪欲法がときどき5色を使うのはなぜですか?
貪欲法は各国を一度だけ塗り、決して考え直しません。早い段階の選択のせいで、後の国が4色すべてに囲まれてしまうことがあり、そうなると5色目を使うしかありません。バックトラックなら、後戻りして前の選択を変更します。
ほかの曲面でも定理は成り立ちますか?
球面では成り立ちます。球面は平面と同じだからです。トーラス、つまりドーナツの表面では、7色が必要な地図があり、7色あれば必ず足りることをパーシー・ヒーウッドが示しました。植民地を持つ国家のように、国がいくつかの離れた部分からなってもよいとすると、4色ではもう足りません。
サーバーに何か送信されますか?
いいえ。地図、塗り分けの方法、チェックはすべてブラウザ内で動きます。設定はこのブラウザのローカルストレージに保存されます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エディターへ