|
Copyright(C)長谷川芳典 |
07月のインデックスへ戻る
最新版へ戻る
※クリックで全体表示。 |
昨日の日記で、東京23区を4色で塗り分けたあと、24区目を以下のように追加すると、4色では塗り分けられない「第25区」を追加することができると述べた。 板橋区、北区、足立区に隣接（但し、板橋区と足立区は一部のみ隣接）するような24番目の区を追加すると、この色は黄色でなければならないことは明白である。でもって、こうして完成した「東京都24区」の外側をドーナツ状に囲むように25番目の区を追加した場合、隣接する区では青、赤、黄緑、黄の4色がすべて使われているため、どうしても5色めが必要となるように思われる【左図】。となると、ついに4色では塗れない地図が発見されたのか？ じっさい、この図に示される白色のドーナツ状の「第25区」は4色すべての色と接しているため、このままでは5色めが必要となる。しかし、この図で。
|
【連載】笑わない数学(3)四色問題(3)ケンプ、オイラーの多面体定理 昨日に続いて、笑わない数学の#3『四色問題』についての感想・考察。 昨日述べたように、放送ではアルフレッド・ケンプに続いて、 ありとあらゆる地図を国の数で分類することから始める。まず1カ国の地図は1色で塗れる。同様に2カ国は2色、3カ国は3色以内、4カ国は4色以内で塗り分けられることは自明である。もしnカ国の地図が4色で塗り分けられたと仮定して、そこにもう1カ国を追加しても4色以内で塗り分けられることができたとすれば、数学的帰納法によってnがどのように大きくなっても4色以内で塗り分け可能ということが証明できる。という数学的帰納法による証明方針が紹介された（放送ではこれを『OKリレー作戦』と呼んだ）。 しかしこの数学的帰納法による証明には大きな困難がある。上掲の左図に示した東京23区（n=23）のように、nを1つ増やしたn=24のところまでは簡単に4色での塗り分けが可能であるが、その次に25番目の区を追加しようとすると色が足りなくなってしまう。つまり、塗り分け方によっては5色以上が必要になる場合があるということだ。とはいえ、これは四色問題の反例にはならない。ウィキペディアによれば、四色定理というのは日常的な直観で説明すると、 ●「平面上のいかなる地図も、隣接する領域が異なる色になるように塗り分けるには4色あれば十分だ。 ということであるが、これは、どうやら、 ●塗り分けに5色以上が必要となるような地図は存在しない。 という意味ではなく、正確には、 ●どんな地図も、【工夫をすれば】4色で塗り分けできる塗り方が1つ以上存在する。 という意味であるようだ。ということで、n個の国で4色塗り分けができたと仮定してn+1でも4色で塗り分けができることを示す場合、上掲の画像のように、すでに4色で塗り分けられている国の一部を別の色に「塗り替える」必要を示す必要がある。塗り替えの方法が確実に示せれば四色定理は証明されたことになるが、いろいろなケースで個別に塗り替えの手順を示すだけでは場合を尽くすことができず、証明したことにはならない。 ではケンプはどうしたか？ ケンプは、 ●どんな地図でも、二辺国、三辺国、四辺国、五辺国と呼ばれる国が必ず1つ含まれる。【どんな地図にも、二辺国、三辺国、四辺国、五辺国のどれか1つは存在している。 ということを発見した。もっとも放送では、なぜそうなるのかは紹介されず。Bingに尋ねてもよく分からなかった。 ネットでさらに検索したところ、スタッフブログに、 ちなみに…実は、番組ではまったく紹介できませんでしたが、この「どんな地図でもゼロ辺国、…、五辺国のいずれかが必ず１つはある」ことの厳密な証明は、「オイラーの多面体定理」という有名な定理を使います。証明の決め手は、ざっくり言うと、地図が２次元の平面であることです。という補足説明があった。なおスタッフブログではケンプの1879年の論文へのリンクもあった。こちら参照。 オイラーの多面体定理を使えば「いかなる地図も５辺国以下の国が含まれるのはなぜか？｣や「数学的帰納法を使う際になぜ６辺国以上の国のことを考えなくていいのか？｣を解決することができる。これについてはこちらに分かりやすい解説があった。 詳細は関連コンテンツに委ねるが、私が理解した範囲で簡単にまとめると、まず、前提として、 ●地図は平面グラフに置き換えることができる。 を理解する必要がある。これによれば、それぞれの国は色の属性を持った点、隣接を示す辺（国境）は点どうしを結ぶ線に置き換えられる。でもって、平面上にどのように点や線を配置しても（但し、線は交差してはいけない）、1本から5本のいずれかで結ばれた点が1つは存在している、というように問題を置き換えて考えることができる。 なぜ6辺国以上のことを考えなくてもよいのかについては、こちらに解説があり、私が理解した範囲で要約させていただくと、
次回に続く。 |