象が転んだ

たかがブロク、されどブロク

”四色問題”から眺めたウクライナ危機

2022年03月31日 05時26分38秒 | 数学のお話

 NHKBS「笑わない数学」(第3回)では、四色問題がテーマだ。
 「四色定理」とも呼ばれ、平面上のいかなる地図(領域)も”4色あれば同じ色が隣り合わずに塗り分けられる”という定理である。
 但し、(境界線ではなく)点のみを共有する領域は隣り合ってるとはみなされず、同色でもよい。

 この地図の”塗り分けの定理”を今回のウクライナ危機に例えてみる。
 そもそも、ウクライナをアメリカ(NATO)とロシアのニ色で塗り分けようとした時点で、大きな悲劇が待ち構えていた。
 中立を必死に訴えるウクライナだが、それだけでは三色になり、”塗り分けの定理”は成り立たず、長らく続いてきたウクライナ危機も一向に解決しない。
 つまり、ウクライナの悲劇を繰り返さない為には、ウクライナを囲む隣国の領域を(アメリカとロシアとEUの3つの色とは)異なった色で塗り直さなければならない。
 これを数学的に定義すればだが、”四色あれば十分”(=四色の定理)となる。
 故にウクライナの周りには、四色目となるアメリカ・ロシア・EUと、新たな中立圏が必要となり、これは私が「結合則で見るウクライナ」で提案した東欧圏である。


四色問題

 証明される前は四色問題と呼ばれ、1976年に一応は証明されたが、未証明の期間が長かった為、現在でも「四色問題」と呼ばれる事がある。
 (ウクライナと米と露の関係みたいに)3つの境界線が1点に集まる場所がある為、最低でも3色が必要である事は明らかですね。
 更に、ある領域の周囲に幾つかの領域がある場合、その領域が偶数(長野県は8個)であれば3色で塗り分けできるが、奇数個の領域で囲まれてる場合(ウクライナの場合は7個)は3色での塗り分けは(不可能で)4色が必要となる。
 そして、”4色あればどんな場合でも塗り分け可能なのか?”という事がこの「四色問題」の本質である。

 ここでは証明は(難解すぎて)省くが、この四食問題の歴史は偶然にも(ウクライナ危機の起源とされる)クリミア戦争の前の1852年に、フレデリック・ガスリー(英)により定式化され提案された。
 1890年になり、パーシー・ヒーウッド(英)により”地図を塗り分けるには5色で十分である”事が証明される(五色定理)。
 しかし、”4色で十分か?”という四食問題は、”平面グラフは4彩色可能である”という(離散数学の)グラフ理論における、最も有名な未解決問題として残った。
 1976年、ケネス・アッペル(米)とヴォルフガング・ハーケン(独)は、コンピュータを利用し約2000個(後に1405個)の”可約”な配置からなる”不可避集合”を見出し、何とか(力業で)四色定理を証明する?に至る。
 その後、アルゴリズムやプログラムの改良が行われ、不可避集合の数を1405個から633個に抑え、再証明が行われた。
 2004年、ジョルジュ・ゴンティエ(加)はよりシンプルな証明を行い、コンピュータ手法の洗練により、確かな手続きで証明が行われ、現在では四色問題は解決したとされる。


塗り分け可能なウクライナ問題

 四色定理の証明の手法は、以下の大きく2段階に分けられる。
 まずどんな平面グラフでも、その集合に属するグラフのどれか1つが部分グラフとして含まれる集合を考えた時、この様な性質を持つグラフの集合を”不可避集合”と呼ぶ。
 これは、かつてウクライナやベラルシが旧ソ連に含まれてた事を(不可避の現実として)イメージすれば判り易いですかね。
 因みに、ここで言う”グラフ理論”のグラフとは(関数のグラフではなく)、点(ノード)の集合に線や辺(エッジ)を書き加えたダイヤグラム(図式、構造)で表現される。
 例えば、路線図(ダイヤ)は(実際の地理の形状ではなく)駅と路線との”繋がり方”に注目する。この”点と繋がりを結ぶ線”の概念こそがグラフ(理論)である。

 次に、この不可避集合をうまく選ぶと、それに属するどのグラフも”可約”になる。
 つまり、その部分グラフを含むグラフがある時、その部分グラフを除いたものが4色で塗り分けが可能ならば、グラフ全体も4色で塗り分けができる。
 因みに、”可約”とは整数論や関数論でよく使われ、ある数やある多項式で割り切れる数や多項式を言います。一般的に言えば、ある単純なものに分解出来る。ここでは、ある領域(グラフ)が色分け出来る事を指します。
 これは、ウクライナが旧ソ連の(不可避な)領土だったとしても、上手く選べば”可約”になる。つまり、ウクライナがある独立した色に塗り分けられる事をイメージすれば、少しは理解しやすいですね。

 もっと冒険的に言えば(ですが)、例え戦争が不可避でも戦争そのものを4色で塗り分ける事は出来る。更に、4色に塗り分ける事で戦争を分散させる事は不可能じゃないとも言える。
 結局、どんな複雑な民族間の紛争も、たかが4色で塗り分けられると(少し強引すぎますが・・・)。


最後に〜四色問題が描くウクライナ

 前述のアッペルとハーケンはコンピュータによる実験を繰り返し、プログラムを何度も書き換え、可約なグラフから成る約2000個のグラフからなる不可避集合を求めた。当時のスパコンであるIBMSystem/370を、1200時間以上使用した、まさに力業とも言える証明でした。
 数学の世界では、複雑な問題に対し、簡潔にまとまった短い証明を”エレガントな解答”と言う事がある。四色定理に対する”力業による証明”は、これとは対極にあり、”エレファント(象)な証明”とも言われます。
 一方で、五色問題の証明は簡潔なもので、四色問題とは対照的でもあった。
 以上、ウィキを参考に主観を加え、簡単にまとめました。

 この様に、ウクライナ危機を数学的に記述する事で、ユニークな見方が出来ますね。
 ウクライナが中立ではなく四番目の色に染まる時、本当の意味での春が来るんでしょうか。
 いや、戦争や介入ではなく、四色問題の解法により平和が訪れてくれれば、数学フェチにとってはこれほど嬉しい事もない。



14 コメント

コメント日が  古い順  |   新しい順
tokoさん (象が転んだ)
2022-04-05 11:37:47
確かに
戦争は浮気程には単純じゃないんですよね。
今回のウクライナ危機を見てもつくづくそう思います。
四色で塗り分けた所で、賠償責任問題は片付きそうにもない。
いや、責任をロシアとアメリカとEUとその他の四色に塗る分けるか・・・
返信する
四股問題 (toko)
2022-04-04 18:21:17
要するに数学的には
四人の女までしか浮気できないんですよね。
それを証明する為に
まずは浮気のパターンを全て書き出し、その1つ1つが四股以内で成し遂げられる事を証明する。
ウ~ン?

浮気もこうやって数学で記述すれば
浮気される側も納得できるのかな
いやいやそんな単純でもないか 
返信する
腹打てサン (象が転んだ)
2022-04-02 03:01:07
いえいえ私の方も理解が浅くて、迷惑をおかけしてます。
いくら証明の見通しが良くなっても、実際に証明するとなると(エレガントな解法とは言え)、ややこしく抽象的にはなりますよね。

でもお陰で、色々と勉強になりました。
これからもよろしくです。
返信する
訂正 (腹打て)
2022-04-01 20:23:07
‹たかが4色グラフGの全ての頂点を塗り分ける事が可能›と書いたけど
‹たかだか4色でグラフGの隣り合う頂点を塗り分ける事が可能›とした方が正解だったね。

今さら面倒だろうけど、訂正です。
返信する
#114さん (象が転んだ)
2022-04-01 13:25:07
いえいえ大歓迎ですよ。
何だか最近はいつも以上に冴えてますね。
この提案は、四色問題というより”四股問題”でしょうか^^;

(何時も一緒にいる)女房を”不可避”とすれば、その不可避な女を上手く選べば、女房を除く4人の女と浮気ができる。そこで(女房を含めた)全体としてみても、たかだか4人の女との浮気が可能となる??

ここでは、不可避を女房に可約を浮気に例えて定理にすれば四色問題とピタリ合うんですが、現実にはあり得なさそうで、意外にもある得る展開かもですね。
返信する
地図を浮気相手に (#114)
2022-04-01 08:43:55
置き換えれば
男が同時に付き合える女は
女房を含め
たかだか4人しかいない
という事でいいのだろうか

迷惑だったら
消してもいいよ^^;
返信する
腹打てサン (象が転んだ)
2022-04-01 04:24:18
とてもわかりやすい説明で、感謝です。
最初からこう説明すればよかったですね(反省)。
グラフ理論なんて、てっきり関数の事かと思ってましたから・・・
地図の塗り分けを平面グラフに置き換える事で、色を次数(グラフで隣接する頂点の数)に置き換えると、証明の見通しは明るくなりますよね。
つまり、平面グラフの次数が4以下である事を証明すればいいんですが、五色問題なら(次数が5以下である事を)オイラーの多面体定理と背理法を使って、きれいに証明できるんでしょうが。四色問題となると、そう上手くはいかないんですかね。

paulさんのコメにある様に、難題を近道して解こうとすると必ず墓穴を掘るので、四色定理はこの辺で打ち止めにしたいです(悲)。
返信する
paulさん (象が転んだ)
2022-04-01 04:21:41
私も知らずに”機能法”になってました。
どうやら設定で自動入力フォームをリセットすると学習機能もリセットされてるみたいで・・・
よく解らんですね。
わざわざ指摘していただいてどうもです。
返信する
Hooさん (象が転んだ)
2022-04-01 04:20:01
エレガントなブログと行きたいんですが
(性格と同じで)どうしても、重たく硬く暗くなるんですよね。
その上、プーチンのウクライナ戦争ですから・・・
エレファント(象)がプーチンを押し潰すって訳にいかんのかな
返信する
グラフ理論 (腹打て)
2022-03-31 20:48:03
複雑な形態をアレコレ日本語で議論するより、グラフ(図式)を描いて頂点と辺(線)で議論した方が圧倒的に分かりやすい。
グラフ理論の本質はここにあるんだけど、グラフGとは、点の集合Vとそれら2点間を結ぶ辺の集合Eのペアで表され、G=(V,E)などで記述する。
少し見慣れない記述だが、転んだ君も言ってるように、このグラフ理論を知ってれば問題を簡潔に記述でき、見通しがよくなる。

で、どのように地図をグラフ理論に応用するかというと、地図の面をノード(頂点)に対応させ、隣接する面同士にエッジ(線)を引く。
そこで、四色定理は‹たかが4色グラフGの全ての頂点を塗り分ける事が可能›と言い換える事が出来る。

これは、平面グラフが平面に交差なしで書ける事に注意すれば、転んだ君の言う”平面グラフは4彩色可能”と同じ事だよね。
勿論、これを証明するのが非常に厄介で、コンピュータの力を借りた訳だが、5色定理なら、コンピュータを使わずに背理法を使って華麗に証明出来る。

数学の世界には気の遠くなるような様々な分野や領域があり、難題をふり分けて考える事で見通しを良くし、解決に導く。
ウクライナ危機もそうやって解決して欲しいもんよ。
返信する
数学的帰納法 (paulkuroneko)
2022-03-31 15:28:05
機能法ではなく、帰納法でした。
訂正します。
返信する
象が空を飛ぶ (HooRoo)
2022-03-31 15:20:32
アメリカでは分厚い壁のことを巨象と呼んだりするけど
転んだサンのブログはエレガントじゃなく
エレファント(象)が空を飛ぶようなものだわね^^;
返信する
paulさん (象が転んだ)
2022-03-31 14:03:08
機能法に加え、背理法もそうですが
下手に使い過ぎると、自らが矛盾の海に彷徨う事になる。
難題を示そうとしてるのに、難題で得られる結果を用いてしまう。まるで、矛盾に自ら溺れる数学者たちの苦悩が見て取れるようです。

日本人は、”なぜ戦争がなくならないのか?”って簡単に考えますよね。
勿論、そんな事ができればとっくの昔に戦争はなくなり、今は軍隊も警察も存在しないでしょうが。
小競り合いが戦争に結び付く過程はとても複雑で、問題は多岐に渡る。ウクライナ危機もそういう意味では、難題の1つですよね。
しかし、そんな難題も数学的に記述すれば、解決できなくとも見通しは明るくなります。

そういうつもりで、四色定理をテーマにしたんですが、paulさんの手にハマると、深いペテンの闇に誘い込まれるようで、理解するのに必死でした。
色々と勉強になります。
返信する
華麗なる証明の落し穴 (paulkuroneko)
2022-03-31 13:04:01
転んだサンが言った2段階の証明ですが、グラフを地図に置き換えるとわかりやすいです。

①平面上の地図が必ず1つは含む、不可避なパターンを列挙する。
②地図からそのパターンを取り除いてできる地図が可約、つまり4色で塗れるならば、元の地図も4色で塗れる事を示す。

この2つの証明には、パターンを全て列挙し、その1つ1つを証明するにもスパコンが必要でした。
もっとシンプルな証明はないのか?
多くの数学者は考えます。
そこである数学者は、とてもエレガントな解法?を思い付きます。

①5つの国だけからなる地図は4色で塗りわける事が出来る。
②地図の外周にある国(海に面する国)は3色で塗りわける事が出来る。
③n国の地図が4色で塗れると仮定し、n+1国も4色で塗れる事を証明する。
以上、①〜③の手順を繰り返せば、あらゆる地図は4色で塗り分ける事ができる(証明終)。

②は”外周が3色で塗り分けられる”事を意味しますが、勘の鋭い人はこれが怪しいと気付いた筈です。
四色問題の証明に必要なのは、”n国全体を4色でかつ、外周は3色で塗り分ける方法がある”事ですよね。
つまり、②は四色定理を使った条件となっています。言い換えれば、四色定理を使って四色定理を証明した何ともエレガントな落し穴だったんです。

この様に、数学的機能法は多くのケースで使用されますが、明白とされる命題の証明に使うべきで、四色問題の様な難題ではこうしたトラブルはよく起きます。
難題を華麗に解き明かすのは数学者の永遠の夢です。
でも、こうしたペテンな華麗なる証明が数多く存在するのも数学的ではありますよね。
返信する

コメントを投稿