四色問題の動的彩色 足掛け３年。 かなり長丁場の思索となりました。 そして、何度も組み立て直しました。 数学とは思えないほどシンプルな四色問題。 「あらゆる地図は４色のインクを用意すれば、そこに描かれた国を塗り分けられる」という中世の印刷業者の経験則。 その証明が150年以上も多くの数学者を悩ませる難問になるとは！ 結局、地図構成を1,936のパターンに分類し、計算機を使って塗分けを示すという方法で、1976年に証明が完結しました。 その後、1996年にパターンは633まで削減されましたが、パターンマッチングによる塗分け手法であることには違いはありません。 しかしなんというか、この証明って美しくないと感じるのは私だけでしょうか？ スーパーコンピューターでも、全ての着色パターンを証明し切るのに２カ月近くも掛かるんです。 同じ感想を持つある数学者の名言を知りました。 「この証明は、エレガントではない。エレファントだ。」 という訳で、素人ながらエレガントな証明に挑んだ訳です。 初稿となる論文は、2024年に完成しました。
|
・ 地図をグラフ化し、そこに補助線を加えることで三角ネットのみの還元可能な構成を与える。 ・ ノード接続とライン接続という単純な手続きを積み上げて、全体を着色するプロセスを確立する。 ・ ２色のスワップ特性を考察し、分断ルートという概念を用いて同色ライン接続を解消する。 ・ ルート変更の輻輳状態から、分断ルートの解が必ず得られることを示し、四色問題を証明する。 |
というアプローチです。 論文はここからダウンロードできます。 2024年版の論文 YouTubeにもアップしてあります。 四色問題の証明（不完全版）
しかし、書き上げて１ヶ月もしない内に、この方法では破綻してしまう地図のパターンを自ら発見してしまいました。 そこで、第２段となる構想を練りました。 次の論文は2025年に完成しました。
|
・ 地図をグラフ化し、そこに補助線を加えた三角ネットのみの還元可能な構成 ・ 海岸線を３色で維持しながら、ノードを逐次追加していくという手続きを積上げて全体を着色するプロセス ・ スワップ処理における排他的連鎖ルートの特性を利用し、接岸ラインから追加ノード色を除去する手法 |
というアプローチです。 論文はここからダウンロードできます。 2025年版の論文 性懲りもなく、こちらもYouTubeにもアップしました。 四色問題の証明（続・不完全版） 前回のYoutubeには、ほとんどコメントが付かなかったのですが、第２段はいくつかコメントを頂きました。 その中で、以下のようなやりとがありました。
|
@neinei601さん ざっと読みましたけど、網羅的検証になってるのかが分からなかったですね。 例えばrandomな問題を1万問等生成して、Appendixの手順で全て着色できるかなど試されてますか？ @muse_kato(私) そうですね。網羅性は自分でもちょっと弱そうだと思っています。 証明にはなっていないかも。 でも、このアプローチが今後の四色問題の解決に少しでも役に立ってくれると嬉しいです。 とてもシンプルなアルゴリズムなので、いつかプログラムを作ってみようと思っています。 この処理シーケンスなら、パソコンでも1000時間もかからず一瞬で処理が終わると予想しています。 一番の課題は、ハーケンとアッペルが作成した1,834種類の地図データを入手することです。 入手方法など、もしご存じでしたらご教示いただけると幸いです。 @neinei601さん まとめに書かれている、2色が2組必要だから計4色なのだとい考え方は説得力があったので、 アプローチ自体は面白そうだと思いました。 後は、網羅性について、9章で議論しているような例外的パターンが他にないかが気になるところです。 図形については申し訳ないですが私は知らないです。 最初は三角メッシュのグラフをランダム生成して着色してみるところからでいいのではないでしょうか @muse_kato(私) >9章で議論しているような例外的パターン そうなんですよ。ここが数学的にはヘタレ状態だと感じてます(苦笑)。 >最初は三角メッシュのグラフをランダム生成 そうですね。それだけでも、意義がありますね。 １万問やってデッドロックしなければ、多少脈ありという感じでしょうか。 でも、これって結局、コンピュータを使った証明アプローチ？(苦笑) @neinei601さん まぁいくらやっても状況証拠&必要条件でしかないですが、 やはり実験結果があるのとないのとでは初見の印象が違いますよね。 あなたのアプローチは単なる理論の証明でなく、 具体的な着色手順があることにも踏み込んでいるわけで（これは証明よりも強い主張）、 せっかくなら実用できることを示せると面白いと思いました。 多分数値実験すると例外パターンが見つかる気もしますが、 それを一つずつ潰していけば、「例外の規則」が見えてきて理論の修正につながるかもしれませんしね @muse_kato(私) 建設的で有意義なコメントを大変ありがとうございます！ >多分数値実験すると例外パターンが見つかる気もしますが、それを一つずつ潰していけば、 >「例外の規則」が見えてきて理論の修正につながるかもしれませんしね 無論、本稿を書き上げるにあたって手作業ではありますが、 いくつものパターンを（ケンプの手法が破綻するパターンも含めて）確認しました。 その過程で、9章の事例を思い付いたのも事実です。（デッドロックが発症した訳ではありません） ですので、neinei601さんのアドバイスは、まさしく的を射ていると思いました。 >具体的な着色手順があることにも踏み込んでいるわけで（これは証明よりも強い主張） プログラミングによる実験のモチベーションが上がってきました！ 実は、初稿ではXスワップで新しい連鎖ルートが発生する可能性があると考え、 それが無くなるまで（手順２）を繰り返す。というシーケンスを主張していました。 ところがその後、どのパターンで追試しても新しい連鎖ルートが生成されないのです。 追試したすべてのパターンで、（手順２）は一発で成功しました。 1つのパターンの中で、いくつものXスワップが起こりますが、そのすべてが一発でした。 そこで、何故うまくいくのかを考察して９章が生まれました。 ２つのアプローチで思索を続けます。 ・乱数による地図の生成を行い、提示した手順を自動実行するプログラムを作成する。 ・提示した手順に基づいた着色パターンの特性を考察し、 それをベースにしたXスワップでは新しい連鎖ルートが生成されないことを論理的に導く。 |
このやりとりに意欲を得て、今回の実証プログラムの作成に挑んだ訳です。 そして、コメントでご指摘いただいた通り、あっという間に無限ループの破綻パターンに突き当たりました(笑)。 四色問題の証明って、本当に一筋縄ではいきません。
それから半年間の試行錯誤を経て、2026年にやっと４色で塗り切れるアルゴリズムが完成しました。
|
・後方逆流を禁止した動的マスキングによるケンプレ鎖制御 ・２系統のカラーペアを重畳させ連鎖を遮断する「排他スワップ」 ・ガード構造による影響範囲の孤立化を図る「結界ルート」の動的変更 ・減色ノードを起点とした３色循環遷移による「三つ巴スワップ」 |
といった内容です。 第３段。三度目の正直といったところでしょうか。 論文はここからダウンロードできます。 2026年版の論文 開発した「彩色ソフト」もダウンロードできます。着色アルゴリズム検証プログラム
結局、数学的な証明ではなく、動的な彩色アルゴリズムの提案という形になってしまったのですが、 しかし、誇れるポイントがいくつかあります。 １つ目は、633パターンといった分類を一切導入する必要が無いこと。 ２つ目は、深さ優先探索でないため、計算速度が極めて高速O(N1.6)であること。 ３つ目は、一種の貪欲法ではあるが、５色ではなく、４色での彩色を保証していること。 ４つ目は、最終的に海岸線を(内陸と同一アルゴリズムで)３色に塗り分け可能なこと。 1,000ノード規模の乱数地図を百万枚流して、すべて着色を完遂しました。 更に、10,000ノード規模の乱数地図を一万枚流す確認も行い、こちらもすべて着色に成功しました。 着色速度も良好です。私のポンコツＰＣでも、10,000ノードの地図の着色に１秒も掛かりません。 開発したソフトは、提案するアルゴリズムの着色ステップを視覚的に確認できる楽しいソフトになってます。 ぜひ、試してみてください。そして、着色に失敗した地図を見つけたら、ぜひお知らせください(苦笑)。