[logo] Web連載「数学ガールの秘密ノート」
Share

第299回 シーズン30 エピソード9
グラフ理論:制約が生む世界(前編)

登場人物紹介

:数学が好きな高校生。

テトラちゃんの後輩。 好奇心旺盛で根気強い《元気少女》。言葉が大好き。

$ \newcommand{\SQRT}[1]{\sqrt{\mathstrut #1}} \newcommand{\TRUE}{\textbf{true}} \newcommand{\FALSE}{\textbf{false}} \newcommand{\FOCUS}[1]{\fbox{ $#1$ }} \newcommand{\LEQ}{\leqq} \newcommand{\NEQ}{\neq} \newcommand{\REMTEXT}[1]{\textbf{#1}} \newcommand{\SET}[1]{\{\,#1\,\}} \newcommand{\EMPTYSET}{\{\,\}} $

高校の図書室にて

テトラ「先輩、先輩! 《新作》来ましたよ!」

「ああ、テトラちゃん。《新作》?」

テトラ「村木先生からの《カード》ですよ! カードといっても《封筒》ですけれど」

テトラちゃんは、手にした大き目の封筒を両手で掲げてみせる。

「また、村木先生の過剰な演出があるのかな?」

テトラ「今回の封筒は一つだけです。それに、 オセロの石も入ってないみたいですね(第294回参照)」

そう言いながら、封筒を上下に激しくゆさぶるテトラちゃん

こういうとこ、けっこうバタバタしてるよなあ。

テトラ「先輩?」

「ん?」

テトラ「もしかして、いま『テトラは落ち着きが足りないぞ』とか思ってませんでした?」

「そんなこと、思ってないよ」

テトラ「そうですか……それで、 もしもお時間があったら、いっしょに考えませんか?」

「でもこれは《テトラちゃんへの問題》ということじゃないの?」

テトラ「村木先生によれば、みんなで楽しむように、だそうです」

「そうなんだ」

テトラ「あたし、先日の《オイラーの多面体定理》と《平面的グラフ》のお話(第298回参照)をレポートにして村木先生に持っていたんですよ。 そうしたら、この封筒をくださったんです」

「みんなで楽しむようにって?」

テトラ「はい。さっそく開けてみましょうっ! いえ……開けてみることにいたしましょう……」

テトラちゃんは、急にすました表情になり、おしとやかな手つきで封筒を机に置く。

封筒を静かに開いて、手をすうっ……と中に入れて《カード》を滑らせるように取り出した。

テトラ「はい、こちらが新作の《カード》でございます」

「これはこれはご丁寧に」

テトラ「(ふかぶか)」

「(ふかぶか)」

二人で、お辞儀をする。

いったい何をしてるんだ、僕たちは。

ミルカ「何をしてる?」

テトラ「きゃっ!」

「ミルカさん、いつ来たの?」

登場人物紹介(追加)

ミルカさん:数学が好きな高校生。 のクラスメート。長い黒髪の《饒舌才媛》。

ミルカ「そんなことより、村木先生の《カード》を見よう」

僕たち三人は、机の上に置かれた《カード》を眺める。

村木先生の《カード》

「『どんな地図でも、五色で塗り分けられるか。』」

ミルカ「答えはイエス。しかし、村木先生のお題としては、《五色定理》の証明をせよということなんだろうな」

テトラ「五色定理の証明っ!? そ、そんなことできるんですかっ?」

「テトラちゃん、どうしたの?」

テトラ「あたし……何かで読んだことがあります。 地図を塗り分ける問題のお話です。ものすごく難しい数学の問題で、 コンピュータを使って非常に多くの場合分けをしてようやく証明できた問題ですよね? 詳しくは知らないんですが、 コンピュータを使って数学の証明するなんてアリなんだって驚きました……」

「それは、五色定理じゃなくて《四色定理》だと思うよ、テトラちゃん」

テトラ「四色定理……五色じゃなくて四色?」

「うん、そうだよ。色を多く使える方が塗り分けするのは楽だよね。 だから、四色定理が超難問だとしても、 五色定理は、もしかしたら僕たちでも証明できるのかもしれない」

ミルカ「この《カード》は例によってアバウトな表現をしているから、私たちが考える問題を明確にしておこう」

「地図は有限個の国に分かれていて、 隣接している国は別の色で塗る必要がある。 点で接している国同士は隣接しているとは見なさない。 ああ、それから、一つの国が《飛び地》になっていることはないというのも?」

ミルカ「ふむ。それから、地図は平面上にある、というのも」

テトラ「それはそうですよね」

ミルカ「平面上に限るのは、たとえば、トーラス上の地図は除外して考えるという意味。 トーラス上の地図は、確か塗り分けに七色必要だったはずだ」

テトラ「トーラスというのはドーナッツの表面ですね」

ミルカ「そう」

テトラ「それにしても、四色定理ほどではないとしても、五色定理は証明できるんでしょうか」

ミルカ「ともかく、地図の双対グラフに対して頂点彩色をしていこう。 地図であるという制約は、双対グラフが平面グラフであるという制約になる」

テトラ「双対グラフ?」

「二色塗り分けのときに使ったグラフじゃないかな(第293回参照)。 国を頂点と見なし、国境を辺とみなしたグラフのことだよね?」

地図と、その双対グラフ

ミルカ「そう」

テトラ「あら? ちょっとお待ちください。だとしたらすでに二色で塗り分けできることは証明しませんでしたっけ?」

「それは、国境がすべて地図の端まで直線で伸びていた場合だよね。 直線で世界が二分されて、片側の色をすべて反転する技法が使えたんだから」

テトラ「ああ、そうでした、そうでした。いわば《色反転の技法》ですね(第293回参照)」

「《三国地図》を考えれば、二色では色が足りないのはすぐわかるね」

テトラ「国が三つ……二色で足りなくなるのは頂点が三個のグラフだからですね」

ミルカ「頂点が三個でも、二彩色可能なグラフはある」

テトラ「あ、ええと……」

「テトラちゃんが言いたかったのは、

 《頂点三個のグラフの中には、二彩色不可能なグラフが存在する》

ということだね。そしてミルカさんが言ったのは、

 《すべての頂点三個のグラフは、二彩色不可能である》は偽である

ということで、どちらも正しいんじゃないの?」

テトラ「……」

「だよね、テトラちゃん?」

テトラ「は、はい、そうです。あの……いまさらですけれど、 論理って大切なんですね。論理を意識しないと、言いたいことがうまく伝わりません」

ミルカ「特に、量化子(りょうかし)だな。 $\exists$ と $\forall$」

「$\exists x\, P(x)$ の方は、 $P(x)$ を満たす $x$ が存在するということだね。 $P(x)$ を満たす $x$ が、 たった一つでも存在するとき、 $\exists x\, P(x)$ は真になる」

テトラ「はい……」

「それから、 $\forall x\, P(x)$ の方は、 どんな $x$ を持ってきても $P(x)$ を満たすとき、 $\forall x\, P(x)$ は真になる」

テトラ「量化子……意識するように注意します」

ミルカ「結局、こんな問題として考えよう」

問題1(五色定理)

任意の平面グラフは五彩色可能である。これを証明せよ。

  • 頂点の数は有限とする。
  • 辺の数は有限とする。
  • グラフにはループがない。
  • グラフには多重辺がない。
  • 平面グラフは、平面上に描かれていて辺が交差しないグラフ。
  • 隣接する頂点(辺の両端となる頂点)は別の色で塗る。
  • 五彩色可能とは、頂点を塗る色の数が五色以下であることをいう。

「ミルカさんは、五色定理の証明を知っているの?」

ミルカ「いや知らない。だからspoilerの心配なく、安心して話せる」

テトラ「ネタバレなしですねっ! ……あっ、でも、テトラを置いてけぼりにしないでください。あたしもきちんと考えたいですから」

こんなふうにして、僕たちの「五色定理」への挑戦が始まった。

まずは、それぞれが黙って考える時間。

証明は、ちょっとネット検索すれば見つかるかもしれない。 でも、それではつまらない。

たとえ、自分にわからないとしても、 いったんはspoiler(ネタバレ)なしでチャレンジしたいから。

無料で「試し読み」できるのはここまでです。 この続きをお読みになるには「読み放題プラン」へのご参加が必要です。

ひと月500円で「読み放題プラン」へご参加いただきますと、 435本すべての記事が読み放題になりますので、 ぜひ、ご参加ください。


参加済みの方/すぐに参加したい方はこちら

結城浩のメンバーシップで参加 結城浩のpixivFANBOXで参加

(2020年7月31日)

[icon]

結城浩(ゆうき・ひろし) @hyuki


『数学ガール』作者。 結城メルマガWeb連載を毎週書いてます。 文章書きとプログラミングが好きなクリスチャン。2014年日本数学会出版賞受賞。

Twitter note 結城メルマガ Mastodon Bluesky Threads Home