« ディズニーの芸術 ― The Art of Walt Disney | メイン | 組織能力・知識・人材 リーディングス日本の企業システム第2期 »
2006年07月18日
四色問題
■ 書籍情報
ロビン・ウィルソン
価格： ￥2100 （税込）
新潮社(2004/11/25)
本書は、一世紀半もの長きに渡って、数学の難問の中で、「最も有名なものの一つ」であり続けた、地図の塗り分けに関する四色問題の歴史とその会をめぐる愉快な歴史を紹介しているものです。本書の登場人物は、「ルイス･キャロル、ロンドン主教、フランス文学の教授、エイプリル･フールに多くの人々をかついだいたずら者、ヒースを愛した植物学者、ゴルフ狂の数学者、一年に一度しか時計の時刻を合わせない男、新婚旅行の間じゅう地図を塗っていた新郎、そして、カリフォルニアの交通巡査」等となっていて、この難問が有名になった理由、単に問題そのものの難しさだけでないことを教えてくれます。
「四色問題」とは、
「四色あれば、どんな地図でも隣り合う国々が違う色になるように塗り分けることができるのか？」
という問題です。この問題は、地図製作者が印刷代を節約するために起こった問題でもなく、単なる物好きのための暇つぶしのようにも見えますが、道路や鉄道のネットワークや通信網に関する実践的なネットワーク問題は、もとをたどれば地図の塗り分け問題に帰着し、グラフ理論の研究や計算理論におけるアルゴリズム研究も色塗り問題につながっているとされ、「長年にわたる各種の試みがエキサイティングな数学の発達を促し、現実世界の重大問題の解決に応用されてきた」ことが述べられています。
この問題は、1852年に数学者ド･モルガンが友人の物理学者であるハミルトン卿に宛てて書いた一通の手紙によって提起されました。ド・モルガンは、学生から、「一つの図形を任意の方法で分割して各部分を色に塗るとき、境界線を共有する部分どうしが違う色になるようにすると、四色が必要になることはあっても、それ以上必要になることはない」という「事実」の理由を聞かれ、それに答えられないことに悩み、「わたしは自分の間抜けさに絶望して、スフィンクスに倣うしかなくなるかもしれません･･････」と記しています（スフィンクスは、オイディプスにかけた謎かけを解かれたために、崖から身を投じて自殺したと伝えられている）。
そして、この問題を質問した学生とは、後にロンドン物理学会の設立者となった物理学者であるフレデリック・ガスリーでした。しかし、この問題は彼の兄であり、後に南アフリカ大学の数学教授となったフランシス・ガスリーが提唱したものであることが明らかになっています。
この問題は、後の数多くの数学者たちを悩ましましたが、1879年に、ロンドンの法廷弁護士にしてアマチュア数学者であったケンプによって、その証明が発表され、たちまち数学神話の一部として広く受け入れられるようになります。この証明は、非常に良いものではありましたが、11年後に、ダーレム・カレッジの数学講師ヘイウッドによって間違いを指摘されます。
20世紀に入ると、アメリカ人数学者によって、
・不可避集合：その中の少なくとも一つがすべての地図に現れるような配置の集合。
・可約配置：最小反例には含まれないような国々の配置。
という2つのアイディアが登場することで進展を遂げます。
1960年代には、地図の塗り分け問題だけを扱った最初の主だった本として『四色問題』が出版されるなど、多くの進歩があったエキサイティングな時代になります。1971年には、当時最高のコンピュータが合った原子力委員会ブルックヘブン研究所のコンピュータ・センター長であった日経二世のヨシオ・シマモトによって、「シマモトの馬蹄」として知られる配置が発見されます。そしてついてに1976年、アッペルとハーケンによって四色問題の証明がなされます。ただし、この証明には、1000時間に及ぶコンピュータの使用時間が費やされ、その出力紙は約1.2メートルに達しました。
問題提起以来124年後にしてついに解決された証明は、熱狂を持って迎えられた一方、コンピュータを用いたことに対しては、
「わたしに言わせれば、あんな解は数学ではない」
「この定理があんなひどい方法で証明されることを神がお許しになるはずがない！」
等の深い失望の声もありました。また、コンピュータを用いた長い証明に対しては、検証可能性という疑問を投げかけること自体にも困難が生じてきます。
本書は、1世紀半近く多くの数学者を熱中させた有名な問題をめぐる読み物としてはもちろん、グラフ理論やネットワークの理論に関心がある人にとっても興味深く読める一冊ではないかと思います。
■ 個人的な視点から
本書の原題である「Four Colours Suffice」とは、四色問題を証明したアッペルとハーケンが、すべての配置の可約性を確認した時に、数学科の黒板の上に発表した、
「Modulo careful checking, it appears that four colours suffice」
という言葉に由来し、後に数学科が料金別納郵便物に押す証明印の標語には、この「四色あれば足りる(four colours suffice)」という言葉が使われるようになったそうです。
■ どんな人にオススメ？
・複雑ネットワークやパーコレーションに関心がある人。
■ 関連しそうな本
小田垣 孝 『つながりの科学―パーコレーション』 2006年07月14日
ダンカン ワッツ (著), 辻 竜平, 友知 政樹 (翻訳) 『スモールワールド・ネットワーク―世界を知るための新科学的思考法』 『スモールワールド―ネットワークの構造とダイナミクス』 2006年03月22日
増田 直紀, 今野 紀雄 『複雑ネットワークの科学』 2005年11月18日
ポール ホフマン (著), 平石 律子 (翻訳) 『放浪の天才数学者エルデシュ』 2005年11月06日
安田 雪 『実践ネットワーク分析―関係を解く理論と技法』 2005年10月04日
■ 百夜百マンガ
【シェイプアップ乱 】当時のジャンプの中では少数派になってしまった汚い絵の作品。最近の作品では、絵自体はうまくなりましたが、（いい意味で）暑苦しさは相変わらずです。
投稿者 tozaki : 2006年07月18日 07:00
トラックバック
このエントリーのトラックバックURL:
http://www.pm-forum.org/MT3/mt-tb.cgi/1056