補遺
●参考文献
1.ロビン・ウィルソン 「四色問題」 2004 新潮社
訳者は茂木健一郎。ただ,あとがきでモギケン自身が述べているように,下訳は別の人が行なっている。数学者でもない彼が下訳をどのようにブラッシュアップしたのか(できたのか)は不明。とはいえ,この本自体は四色問題の歴史も証明のエッセンスもとてもわかりやすい。グラフ理論の知識が全くなくても問題なく読める良書。
2.一松信 「四色問題―その誕生から解決まで」 1978 講談社ブルーバックス
専門家である数学者が執筆。すでに絶版。後述の双対グラフを使って説明がされていて,グラフ理論になじみがないとすこしわかりにくい。とはいえ一般向け書籍なので,素人でも念入りに読めば分かるように書かれている。何度も反復して読解に努めれば得るものが多い良書。
3.Thomas, Robin (1995), The Four Color Theorem
アッペル・ハーケンの証明の改良。アッペルとハーケンがつくった可約配置の不可避集合の要素数は1936個(後に1476個)だったが,ロバートソンらがこれを633個に減らした。用いる放電法の種類も,400以上あったのを32に減らした。ただし,可約性のチェックだけでなく,不可避集合の構築にもコンピュータが必要となっている。
4.Thomas, Robin (1998), "An Update on the Four-Color Theorem", Notices of the American Mathematical Society 45 (7): 848-859
●英語の情報量
四色問題についていろいろと調べたが,日本語の情報がとても少ないと痛感。一般向けの日本語の書籍はほとんど上記の二つしかないが,英語の本ならAmazonで十何冊もヒットする。ネット上の情報も,Wikipediaをはじめ,英語の方が格段に豊富だ。
●年号の揺れ
四色問題解決の年は,1976年とする文献と1977年とする文献がある。何をもって証明がなされたかと考えるか,の違いによるのかな。1976年夏,世界中で華々しく報道されたことは事実。
●双対グラフ
四色問題を考える際には,ふつう双対グラフを使うが,本文では参考文献1に倣ってわかりやすさを優先し,地図のまま扱った。
双対グラフとは,地図の各国を点で表し,国と国の隣接関係を線で表した平面グラフ。地図をそのまま扱うより数学的に本質化されて都合がよい。両者の対応関係は次のようである。
地図 | 国 | 国と国の境界線 | n辺国 | (三枝地図) |
双対グラフ | 点 | 点と点を結ぶ線 | n枝点 | (極大平面グラフ) |
n枝点とは,線がn本出ている点。元の地図と双対グラフとでは,面と頂点が入れ替わっていて,辺の数は変わらないので,オイラーの公式 V+F−E=2はそのまま成り立つ。
極大平面グラフとは,グラフの線で囲まれた領域がすべて三角形になっている平面グラフ。そのようなグラフでは隣接していないどの二点を結んでも,平面グラフではなくなってしまう(逆も正しい)ので,「極大」と呼ぶ。極大平面グラフは,点同士が最大限隣接しているので,他のグラフよりも塗り分け難い。四色問題を考えるときは,極大平面グラフを考えれば十分。
三枝地図において三国が会する点は,極大平面グラフの三角形にあたる。ただし,三枝地図と極大平面グラフは似ているだけできちんとは対応していない。例えば眼鏡枠の形の国境線で隔てられた四国(左眼,右眼,額,顔)を考えると,これは三枝地図であるが,その双対は極大平面グラフにならない(左右の眼が隣接していない)。点が4個以上の極大平面グラフでは,n枝点のnは必ず3以上だから,2枝点を考える必要はない。この点で二辺国を考慮する参考文献1の論証は冗長だ。もっとも二辺国は自明な可約配置だからたいした違いではない。
●ヘーシュのグラフ記法
ヘーシュは,放電法とD,C可約性の導入で四色問題解決に多大な貢献をしたが,ほかに配置を表す便利な記法も提唱し,これも広く使われた。
彼は双対グラフにおいて,各点が何枝点であるかが一目で分かるように,n枝点をnの数値ごとに異なるマークで表した。五枝点なら黒丸,六枝点なら点,七枝点なら白丸…というように。
可約配置の不可避集合をつくるわけだが,ヘーシュの記法によって,検討しようとする配置がどんな配置か一目でわかるようになる。配置を表すグラフは,地図全体を表すグラフの一部(サブグラフ)であり,配置内部の点は,内部で相互につながっているだけでなく,周辺のグラフともつながっている。ヘーシュの記法を使えば,配置の内部の点と線だけ書けば,周囲とどうつながっているかも同時に表現できる。
●用語集
四色問題(四色定理) | Four Color Problem (Four Color Theorem) |
点/辺/面 | vertex / edge / face |
最小反例 | minimal counterexample |
可約配置 | reducible configuration |
D可約性(C可約性) | D-reducibility (C-reducibility) |
不可避集合 | unavoidable set |
ケンペ鎖 | Kempe chain |
放電法 | discharging method |
極大平面グラフ | triangulated planar graph |