第299回 グラフ理論:制約が生む世界(前編)

村木先生からとんでもないお題がやってきた。「僕」たちは総力を挙げて問題に挑む……「グラフ理論」シーズンのクライマックスへ!

登場人物紹介

:数学が好きな高校生。

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

$ \newcommand{\HIRANO}{\unicode[sans-serif,STIXGeneral]{x306E}} \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(ネタバレ)なしでチャレンジしたいから。

この続きは有料会員登録をすると
読むことができます。
cakes会員の方はここからログイン

1週間無料のお試し購読する

cakesは定額読み放題のコンテンツ配信サイトです。簡単なお手続きで、サイト内のすべての記事を読むことができます。cakesには他にも以下のような記事があります。

人気の連載

おすすめ記事

トポロジーの世界に飛び込んでみよう!

ケイクス

この連載について

初回を読む
数学ガールの秘密ノート

結城浩

数学青春物語「数学ガール」の中高生たちが数学トークをする楽しい読み物です。中学生や高校生の数学を題材に、 数学のおもしろさと学ぶよろこびを味わいましょう。本シリーズはすでに12巻も書籍化されている大人気連載です。 (毎週金曜日更新)

この連載の人気記事

関連記事

関連キーワード

コメント

chibio6 頂点③か⑤のどちらかは①と同色にできるので、①から⑥までは5色で塗り分けできる。さら… https://t.co/fFkMWLk1U8 約2ヶ月前 replyretweetfavorite

euler_KHUx 読んでいてワクワクしました!明日のシリーズ300回目が楽しみです\(^o^) 約2ヶ月前 replyretweetfavorite

hyuki Web連載「数学ガールの秘密ノート」は明日でいよいよ第300回となります。グラフ理論シーズンの最終回。すごくおもしろいので、第299回をいまのうちにお読みください! https://t.co/AXTkDYLk7H 約2ヶ月前 replyretweetfavorite

TkBohz > ミルカ「数学をしよう。 かっこいいな 約2ヶ月前 replyretweetfavorite