4色定理: 古典的な色付け問題に対する新時代のアルゴリズム

四色定理について聞いたことがあるはずです。もともと地図上の国々を色分けすることから生まれたこの興味深い問題は、現代世界の 3 大数学問題の一つとして知られています。数学者が真の証明を導き出すまでには 100 年以上かかり、使用されたコンピューターによる証明も数学の段階に入りました。今日でも、グラフ理論の分野では、四色定理から派生した興味深い問題が数多く存在します。たとえば、ラジオ放送局から生まれた問題では、無限に大きい方眼紙に数字を記入しますが、同じ数字間の「距離」は、その数字自体よりも大きくなければなりません。では、平面全体をカバーするには、少なくともいくつの数字が必要ですか?

著者 |ハン・イン

子どもの頃、書斎の壁に貼られた世界地図をじっと見つめたことがありますか?色とりどりの模様を眺めながら、いつか世界中を旅できる日を想像しました。 19世紀のイギリスでは、そんな視線から、古くて古典的な数学の問題である「彩色問題」が生まれました。

図 1: 世界地図 |出典：天然資源省標準地図サービスシステム

4色問題の起源

物語は1852年、イギリスの地図製作者フランシス・ガスリーが地図を観察しながら「地図に色を付ける」という疑問を提起したことから始まります。彼は、隣接する国々が異なる色になるように地図を着色するには 4 色だけが必要であることを発見しました。しかし、彼を困惑させたのは、「4」という数字が最良であるかどうかでした。彼は兄のフレデリック・ガスリーと友人たちに助けを求めた。コミュニケーションをとるうちに、彼らはこの問題が数学と深い関係があることに徐々に気づきました。フレデリックは、ロンドン大学ユニバーシティ・カレッジの教師である数学者オーガスタス・ド・モルガンに助けを求めた。ド・モルガン教授は問題を解決しようとしたができなかったため、手紙を書いて、親友であるアイルランドの数学者ウィリアム・ハミルトン教授に問題を伝えた。残念ながら、賢明なハミルトンはこの問題にあまり興味を持っていませんでした。

モーガンさんは手紙の中でこう書いている。「今日、ある学生が私に事実を説明するように頼んできました。それが事実とみなせるかどうかはわかりません。平面上の図形は任意に有限個の部分に分割でき、各部分を隣接する部分が異なる色になるように色分けできるが、使用できる色は4色だけだと彼は言いました。どう思いますか？この問題が事実なら、人々の注目を集めることができるでしょうか？」

当初、この「単純に聞こえる」問題は数学者からあまり注目されませんでした。 1878 年になって初めて、イギリスの数学者アーサー・ケイリーがロンドン数学会でこの問題を公式に発表し、「四色問題」と名付け、誰もがこの問題を解きたいという欲求を抱くようになりました。当時、数学者たちは一般的に、4色問題はそれほど難しくなく、すぐに解けるはずだと信じていました。しかし、事態は予想に反して進みました。 「四色予想」から「四色定理」までには120年以上かかりました。かつては「フェルマーの最終定理」や「ゴールドバッハの予想」とともに世界で最も有名な3つの数学問題の一つとさえ考えられていました。

図2: 数学者ケイリー 出典: スミソニアン協会図書館

四色定理の百年記念証明

4 色問題の一般的な説明には、各国の形状、面積、経度、緯度など、無効な情報が多数含まれています。唯一の重要な情報は、隣接性 (つまり、2 つの地域が同じ境界を共有している) です。この無効な情報を無視して、グラフ理論の抽象言語を使用してこの問題を厳密に定義する方法を見てみましょう。

グラフ G = (V, E) が与えられます。ここで、空でない集合 V は頂点集合であり、E は辺集合です。ここでは実際に双対グラフの概念が使用されています。つまり、頂点 ν∈V は地図上の国を表すために使用されます。辺e12=(ν1, ν2)∈Eは、2つの頂点（国）ν1とν2が隣接していることを示すために使用されます。以下では、単純な無向グラフのみを検討します。グラフのエッジは無向、つまり e12=e21 です。重複する辺は存在しない。つまり、頂点ν1とν2を結ぶ辺は最大で1つ存在する。自己ループはありません。つまり、1 つの頂点のみを接続するエッジはありません。

4 色問題は、次のような推測に抽象化されます。単純な無向グラフ G=(V, E) の頂点を、隣接する点が異なる色になるように色付けするには、少なくとも 4 色が必要です。ここで必要な最小色の数を彩度数と呼びます。

当初は手作業で計算することしかできず、4色予想は96か国を含む地図に対して有効であると結論付けました。物語の転機は 1879 年に起こりました。イギリスの弁護士アルフレッド・ケンプが四色予想の証明に重要なアイデアを提供したのです。ケンプは、任意の単純な無向グラフ G=(V, E) には、2、3、4、または 5 つの隣接する頂点を持つ頂点が少なくとも 1 つある (国には少なくとも 2、3、4、または 5 つの隣国がある) と提案しました。この命題は実際にはオイラーの公式の応用です。グラフ G=(V, E) に ν 個の頂点、e 個の辺、f 個の面があるとします。まず、どの面にも少なくとも 3 つの辺があり、隣接する 2 つの面は 1 つの辺を共有し、各辺には 2 つの頂点があるため、2e=3f となります。すべての頂点に少なくとも 6 つの辺がある場合、2e ≥ 6ν となります。しかし、オイラーの公式によれば、ν-e+f=2 となります。これは矛盾を生じます。

Kempe は、最大 5 つの隣接頂点とそれに対応する辺を持つ上記の頂点を「必然的な構成」と名付けました。次に、彼は帰納法を使用してこの頂点とその隣接する辺を削除し、サブグラフ G' を取得しました。このサブグラフ G' が 4 色予想を満たす場合、元のグラフ G' は縮小可能と呼ばれ、削除された頂点とその辺は「縮小可能な構成」と呼ばれます。ケンプは、すべての必然的な構成が縮小可能な構成である（つまり、対応する頂点とその辺を削除した後で 4 色にできる）ことが証明できる限り、4 色予想は必然的に成り立つと信じていました。数学的に言えば、n 個の頂点を持つグラフが 4 色予想を満たす場合、n+1 個の頂点を持つグラフでは、必然的な構成となる頂点とその辺が存在する必要があります。隣接する点が 3 色の場合、削除された点を 4 番目の色で塗りつぶすと、結論は自然に成り立ちます。それ以外の場合は、元の画像を再描画してこの頂点を解放し、隣接する点を 3 色にする必要があります。この目的のために、ケンプは「ケンプチェーン」法を設計しました。

しかし、ケンペの結果が発表されてから 11 年後、そこに致命的で修正不可能な誤りがあることが発覚しました。しかし、ケンプの考えは後の世代にとって重要な進歩をもたらしました。人々は彼の方法を継続し、22 か国、39 か国、52 か国以下の地図を 4 色で表せることを証明しました。アメリカの数学者ケネス・アペルとヴォルフガング・ハーケンが、イリノイ大学の2台のコンピューターで1,200時間を費やしてようやく4色定理の証明を完了したのは1976年のことでした。彼らはケンペの方法を継続して改良し、1936 個の必然的な構成をすべて完全にリストアップし、それらの簡約性を 1 つ 1 つ検証しました。この研究は、難しい数学の問題を証明しただけでなく、コンピューターが数学の論理的証明にも使用できることを人々に知らせたという点で世界に衝撃を与えました。二人の数学者が研究成果を発表した日、地元の郵便局は祝賀のためすべての郵便物に「4色で十分」という特別な消印を押した。

図 3 4 色定理の証明が発表されてから何年もの間、イリノイ大学アーバナ・シャンペーン校の数学科は、発送する郵便物に「4 色で十分」という消印を押していました。丨画像ソース: las.illinois.edu

図4: 数学者ヴォルフガング・ハーケン（1928-2022）とケネス・アペル（1938-2013）丨 出典:
Legacy.com/mathyear2013.blogspot.com

実際、アペルとハーケンは、4色予想を解くためにコンピューターを使用する必要があることを認識した最初の人々ではありませんでした。 1950 年初頭、ドイツの数学者ハインリッヒ・ヘーシュは、4 色予想の限られた膨大な数の異なる構成をテストするには、膨大な量のデータを処理できる強力なコンピューティング デバイスの助けが必要であると予測しました。コンピュータ技術がまだ発達していなかった時代に、西旭の考えは非常に先進的でした。彼は、4色問題の解決にコンピューターの使用を提唱し、試みた最初の数学者でした。彼はまた、自分のアイデアの多くをハケンと惜しみなく共有しました。彼は四色予想の証明を推進する上で大きな役割を果たしたと言える。

アペルとハケンの研究結果はセンセーションを巻き起こしたが、当時は広く認知されていなかった。人々の疑念は主に、数学の問題を証明するためにコンピュータを使用することを認識していないことに起因しています。懐疑論者は、アペルとハーケンの方法は本質的に徹底的なテストであると信じています。彼らは単に機械を使って何千万もの状況をテストしただけです。証明の詳細はコンピュータ内に隠されており、人間の力では検証できません。数学界は純粋で明確な数学的証明を求めた。 30年後、イギリスのケンブリッジ大学の若き数学者ジョルジュ・ゴンティエが、完全にコンピューター化された四色定理の証明を発表しました。アペルやハーケンとは異なり、彼の論理的証明の各ステップはコンピュータによって独立して完了しました。コンピュータ革命の何年にもわたって、人々は数学の仕事におけるコンピュータの助けを徐々に認識するようになり、ついに四色定理が有効であると認めるようになりました。

放送彩色数問題: 4色問題の一般化

数学者たちは、四色予想を研究しながら、関連する他の色付け問題についても考えました。たとえば、最も有名なハドヴィガー・ネルソン問題は、無限大の平面上の点を、隣接する点が異なる色になるように色付けするというものです。本日ご紹介するのは、4 色問題の別のバリエーションである、パッキング カラーリング問題 (ブロードキャスト カラーリング問題とも呼ばれます) です。この疑問は、クレムソン大学のウェイン・ゴダード教授らによって最初に提起されました。それは実際には、ラジオ局の周波数割り当てという非常に実際的な問題から始まりました。

図 5: ラジオ |出典: インターネット

各ラジオ局が発信する信号のカバーエリアは限られています。信号が強くなるほど、カバー範囲が広くなります。ラジオの周波数変調（FM）帯域は非常に狭いです。私の国の民間ラジオの FM 範囲は FM87.5-108MHz です。わが国の各省や各都市のラジオ局が異なる周波数の信号を発信するというのは明らかに非現実的でしょう。同じ周波数を持つ 2 つのラジオ局の信号は、十分に離れている場合にのみ相互に干渉しません。たとえば、天津クロストークラジオ、瀋陽都市ラジオ、台州交通音楽ラジオの FM 周波数はすべて 92.1 MHz です。天津に隣接する北京では、同一信号による干渉の重複を避けるため、ラジオ局周波数表に92.1MHzの信号帯域を割り当てていない。

では、干渉を避けながら最短の信号帯域範囲で全国放送システムをカバーできるように、さまざまな地域のラジオ局の周波数をどのように割り当てればよいのでしょうか?数学者は数学の言語を使ってこれをどのように定義するのでしょうか?

4色定理と同様に、単純な無向グラフ G=(V, E) が与えられた場合、整数セット K={1,…,k} を使用して色セットを表し、d(u, ν) を使用して 2 つの頂点 u、ν 間の距離を定義します。任意の2つの頂点u、ν∈V、および任意の整数c∈Kに対して、f(u)=f(ν)=c（つまり、頂点uとνが同じ色である）であれば、uとν間の距離d(u,ν)>c（つまり、同じ色を持つ2つの頂点は十分に離れている。上記の実際的な背景を考慮すると、これは同じ信号周波数を持つラジオ局が十分に離れていることを意味する）を満たすマッピングf:V→{1,…,k}を考えます。このような写像fはパッキングk-彩色スキームを構成し、パッキング彩色スキームを満たすことができる最小の整数はグラフχρ(G)のパッキング彩色数と呼ばれます。

パッキングカラーリング問題は、実際にはマップカラーリング問題にさらに強い制約を課します。 K={1} の場合、パッキング 1 色付け問題は、隣接する 2 つの頂点の色が異なることを必要とする最も基本的なマップ色付け問題です。まずは簡単な例を見てみましょう。下の図の 1 次元整数軸を考えてみましょう。グラフ G=Z={0, ±1, ±2,...} を整数集合としてとります。各整数は頂点を表します。隣接する 2 つの整数は、隣接する 2 つの頂点として記録されます。 2 つの整数間の距離は、それらの差の絶対値として定義されます。構築マッピングは次のとおりです。

図 9: プラス記号領域 |出典：参考文献[8]

同僚がコメントしているように、Suvecaseus 氏と Heller 氏は単に問題を解決しているのではなく、組み合わせ論における研究アイデアを最適化しています。 4か月間の不断の努力の末、ついに平詰め染色の問題を解決しました。

終わり

四色定理は1世紀以上にわたって数学界を悩ませてきましたが、今日に至るまで、真に純粋な数学的証明は見つかっていません。しかし、4 色問題の重要性は、問題そのものをはるかに超えています。さらに重要なのは、数学者の世代が考える過程で、グラフ理論、位相幾何学、コンピューターサイエンスなど、他の分野の学問について考えるようになったことです。人々が 4 色問題を研究するのは、実際に地図を 4 色で塗りつぶすためではなく、数字「4」の位相特性と数学的意味合いを探求するためです。

最初の数学定理がコンピューターの助けを借りて証明されたため、四色定理は当初疑問視されていたものが広く認識されるようになり、数学の歴史において特別な位置を占めることになった。今日の人工知能の急速な発展により、AI 支援による数学的証明がほとんどの学者の焦点となっています。 AI による正式な証明は数学本来の美しさを損なうと信じている人もいますが、高度な技術的手段によって数学者の仕事が大幅に簡素化されたことは否定できません。おそらく私たちが問うべきなのは、コンピュータそのものではなく、コンピュータを使用する学者の姿勢と方法である。

ユークリッドは紀元前 300 年に『原論』でほぼ完璧な言語で数学を定義し、一連の直感的で厳密な体系を後世に提示しました。 21 世紀になると、人々は正確な記号と機械的な規則を使用して、数学をコンピューター コードに変換しました。これも数学文化の継承と反復ではないでしょうか？

参考文献

[1] 徐俊明.グラフ理論とその応用。第3版[M]。合肥：中国科学技術大学出版局。 2010年。

[2]Fritsch R. 4色定理[J].アメリカ数学月報、1997年、106(8):785。

[3]Gonthier G. 形式的証明—4色定理[J].アメリカ数学会通知、2009(1)。

[4] 王先芬、胡作軒。四色定理の証明の3世代。自然の弁証法ジャーナル。 2010年4号、pp.42-48、127、計7ページ

[5]Goddard, W., Hedetniemi, S., Hedetniemi, S., Harris, J., Rall, D.:グラフのブロードキャスト彩色数。アルスコーム。 86 (2008年1月)

[6]Bre sar, B., Ferme, J., Klav zar, S., Rall, DF:包装用着色料に関する調査。ディスカッション Mathematicae グラフ理論 40(4)、923 (2020)

[7]Subercaseaux, B.、Heule, MJH: 無限正方格子のパッキング彩色数は少なくとも14である。Meel, KS、Strichman, O. (編) 第25回国際満足度テストの理論と応用会議 (SAT 2022)。ライプニッツ国際情報学会議報 (LIPIcs)、vol. 236、21:1–21:16頁。ダグシュトゥール城 – ライプニッツ ツェントルム毛皮情報 - マティック、ダグシュトゥール、ドイツ (2022)

[8]Subercaseaux, B., Heule, MJH 無限正方格子のパッキング彩色数は15である。arXiv:2301.09757

この記事は科学普及中国星空プロジェクトの支援を受けています

制作：中国科学技術協会科学普及部

制作：中国科学技術出版有限公司、北京中科星河文化メディア有限公司

特別なヒント

1. 「Fanpu」WeChatパブリックアカウントのメニューの下部にある「特集コラム」に移動して、さまざまなトピックに関する人気の科学記事シリーズを読んでください。

2. 「Fanpu」では月別に記事を検索する機能を提供しています。公式アカウントをフォローし、「1903」などの4桁の年+月を返信すると、2019年3月の記事インデックスなどが表示されます。

著作権に関する声明: 個人がこの記事を転送することは歓迎しますが、いかなる形式のメディアや組織も許可なくこの記事を転載または抜粋することは許可されていません。転載許可については、「Fanpu」WeChatパブリックアカウントの舞台裏までお問い合わせください。