じぶん更新日記・隠居の日々
1997年5月6日開設
Copyright(C)長谷川芳典



08月のインデックスへ戻る
最新版へ戻る



※クリックで全体表示。

　半田山植物園で見かけたオスのシオカラトンボ。近縁種にオオシオカラトンボがあるが、眼が青いことからシオカラトンボの可能性が高い。

2023年8月7日（月）




【連載】笑わない数学(6)四色問題(6)最小反例

　少し空いてしまったが、8月3日に続いて、笑わない数学の#3『四色問題』についての感想・考察。

　さて7月28日の日記でも述べたように、NHKの放送内容は、四色問題解決の経緯が簡略化されており、放送だけを視聴して理解することは難しい。その点では、YouTubeの解説動画：

●【ゆっくり解説】こんなに単純な問題がなぜ100年以上数学者たちを悩ませたのか−四色問題

のほうが遙かに分かりやすい【参考文献はこちら】。解説形式として、パンサーの尾形貴弘さんが喋りまくる放送よりも、『ノワール（聞き手）』と『ブラン（解説者）』という2人のキャラの掛け合いの解説動画のほうが分かりやすいという面もある。

　この動画のほうでは、放送では扱われなかった、
  • 最小反例
  • ケンプ鎖
  • 不可避集合と可約配置
という概念が解説されていた。放送のほうで取り上げなかったのは、おそらくあまりたくさんの新しい概念を登場させてしまうと未消化になってしまうという配慮が働いたためと思われるが、逆に概念をしっかり示したほうがスッキリして分かりやすくなるという場合もある。

　上掲のうちの『最小反例』については、こちらのレポートに分かりやすく解説されていた。なおこのレポートはPDF形式のため単体では出典が不明だが、URLから元を辿ると岐阜県の高校の理数科の研究発表であると推測された。このレポートでは、
最小反例とは、四色定理が間違っていて、4 色では塗り分けられない地図が存在するとした時の、5色以上が必要な国の数の最小値のことである。最小反例は 4 色で塗り分けられないが、それより少ない国からなる地図はどれも 4 色で塗り分けられるということが分かる。つまり、最小反例が存在しなければどんな地図も 4 色で塗り分けることができるといえる。
と解説されている。
　次に、最小反例のロジックにより、二辺国、三辺国、四辺国、五辺国について、「もし、○辺国を含む地図で最小反例があったとすれば、どういう矛盾が起きるのかを順に指摘していく。例えば、
  • Ａ国、Ｂ国と国境を接する二辺国（Ｃ国）を含む最小反例があると仮定する。
  • その二辺国からＡ国との国境を1本消す（Ｃ国は隣のＡ国に吸収される）。
  • Ａ国とＢ国は2色で塗り分けられる。
  • Ａ国とＢ国の間にＣ国を復活させる。
  • 復活したＣ国は、3色目で塗り分けられるが、これは元の地図が最小反例であるという仮定に矛盾する。
  • よって、最小反例は二辺国を含まないことが証明された。
同様にして、最小反例が三辺国を含まないことも簡単に証明できるが、四辺国となると、色の塗り替えが必要なケースが出てくる。そこで登場してくるのが『ケンプ鎖』であった。

　しかし、ケンプ鎖を適用しても4色への塗り替えが適用できない例が見つかった【ヒーウッド（ヘイウッド）、1889年】。このほかにもいくつか『反例』と称される例がこちらに紹介されている。

　次回に続く。