第294回 グラフ理論:偶奇の伝搬(後編)

二つ目の封筒を開けた「僕」とテトラちゃん。そこに入っていた問題は……

登場人物紹介

:数学が好きな高校生。

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

$ \newcommand{\HIRANO}{\unicode[sans-serif,STIXGeneral]{x306E}} \newcommand{\SQRT}[1]{\sqrt{\mathstrut #1}} \newcommand{\EMPTYSET}{\{\,\}} $

図書室にて

いまは放課後。ここは高校の図書室。

と後輩のテトラちゃんは、村木先生から渡された問題を解いていた。

一つ目の封筒に入っていた問題をようやく解いたところ。(第293回参照)

ようやく解いた……といっても、問題を作ったのは僕たちなんだけどね。

テトラ「できましたね……それにしても、《小さな数で試してみる》ってどうしてこんなに効果的なんでしょう」

「どうしてだろうね。小さな数で試しているうちに、その問題のことをよく理解するからかなあ……」

テトラ「あたし、一気に一般の$n$に挑戦する癖を何とかやめたいです。一度にすべてを解く!とか、いっぺんに全部を理解する!のに憧れちゃうんでしょうか……」

「一歩ずつ、だよね」

テトラ「一歩ずつ……あっ、そういえば! 封筒はもう一個あるんでした。いっぺんに開けないでと村木先生はおっしゃっていましたけど、もういいですよね」

「ああ、そうだね。こっちにはどんな問題が入っているんだろう」

テトラちゃんは残っていたもう一つの封筒を開けた。

中には……

テトラ「何でしょう。これは、ビニール?」

「ビニールというか、クリアファイルかな。いやファイルじゃない。二つ折りになったシート? 透明なシートっぽいね」

テトラ「図が描いてあります……ボードゲームみたいですね」

二つ目の封筒に入っていた透明シート

「僕には何かの《配線図》みたいに見えるなあ。こっちも図形問題なのかな。一つ目の封筒には古い紙を使った《地図》が入っていて、 二つ目の封筒には透明シートを使った《配線図》が入ってる……と」

テトラ「古い紙と透明シート……もしかして、過去と未来の演出ということでしょうか。時を越える演出とか?」

「演出はさておき、肝心の《カード》は入っているかな」

テトラ「《カード》もありますね。あ、あちゃちゃ?!」

テトラちゃんが《カード》を取り出そうと封筒を逆さにして振ると、 《カード》といっしょに小さくて薄いプラスチック片がパラパラと落ちてきた。

「これはオセロの石みたいだね。ずいぶん小さいけれど……」

テトラ「封筒の中でシャカシャカ音がしてたのは、これだったんですね」

「とにかく《カード》の方を読もうよ」

二つ目の封筒に入っていた《カード》

この図は、未来都市の施設内に作られた通信網である。

小さな丸印はセンサーを配置するための場所を表し、 二つの丸印をつなぐ線はセンサー間で通信が可能であることを表している。

センサーを表している小さな丸印を《頂点》と呼び、二頂点を結ぶ線を《辺》と呼ぶことにする。

センサーには「白」と「黒」の二種類が存在し、すべての頂点にどちらか一種類のセンサーを配置しなければならない。

ただし、一つの辺の両端には白と黒の両方を配置しなければならない。

テトラ「《頂点》は、このシートの丸印で、《辺》は頂点を結んでいる線のことですね」

「そうだね……そして頂点に、白と黒のセンサーを置く。さっき落ちてきたオセロの石のどちらかを上にして、頂点に置くってことか……なるほど」

テトラ「どういうゲームなんでしょう」

「いや、ゲームなのかな……この《カード》の説明だと、単に白と黒を置いてぜんぶを埋めればいいんだと思うよ。ああ、でも、ルールが一つあったね」

テトラ「はい。これですね。『ただし……』」

ただし、一つの辺の両端には白と黒の両方を配置しなければならない。

「そうだね。だから、たとえば白と黒は、こんなふうに置かなきゃいけないんだ」

一つの辺の両端には白と黒の両方を配置しなければならないというルールを守った例

テトラ「はい、わかります。それから、たとえばこんなふうに黒を二つ、隣り合うように並べてはいけないんですね。 でも、これは難しいことじゃありませんよ。 だって、同じ色が並ぶかどうかは見ればすぐにわかりますから」

一つの辺の両端には白と黒の両方を配置しなければならないというルールを破った例(黒が並んでいる)

「まあね。でも、頂点はけっこう多いよ」

テトラ「大丈夫です! 二人で分担すれば、すぐですっ! 何ならあたし一人でもっ!」

「ともかく置いてみようか」

テトラちゃんは白と黒をシートの《頂点》に置いていく。

もちろん、《辺》の両端は違う色になるように注意しながら……

テトラ「あっ、先輩。だめです。そこは白を置く頂点ですよ」

「え、でも、ここは黒になる頂点なんだけど……僕の側から見ると」

テトラ「え、ええっと……あたしの側から見ると白なんです」

白も黒も置けない場所がある?!

テトラちゃんは右上から、は左下から置いていった)

「……僕たちは、かなり間抜けなことをやっちゃったみたいだね」

テトラ「もしかして、このゲーム、二手に分かれてはまずかった……?」

「そういうことになりそうだね。僕とテトラちゃんが別の場所から置き始めたから、ぶつかってしまったんだ」

テトラ「あっ、でも、たいした手間じゃありませんから、あたしのを全部やり直せばいいですよ。ぜんぶいったん片付けて……」

「ああああああっ、ストップストップ!」

テトラ「せせせ先輩っ!」

「ごめん! つい……痛くなかった?」

は、オセロの石を片付けようとしたテトラちゃんの手を思わずつかんでしまった。

テトラ「だだだ大丈夫です。びっくりしただけです」

「ごめんね。あのね、片付けるんじゃなくて、色を反転させればいいんじゃないかと思ったんだよ」

テトラ「え? ああ……そうですね」

テトラちゃんはいったん置いた石をすべて反転した。

テトラちゃんが置いた石をすべて反転させた

「そうそう。《辺の両端を違う色にする》というのがルールだから、ルールを守っている範囲を反転しても、やっぱりルールは守っていることになる」

テトラ「これで、さっき《ごっつんこ》したところは、黒に決まります」

「あれ……?」

ルールを守り、頂点をすべて埋めた

テトラ「はい、残りもぜんぶ埋めちゃいましたよ! これで完成です。簡単な問題でしたね」

「……」

テトラ「先輩?」

「ねえ、テトラちゃん。これって同じ問題だよね」

テトラ「何がですか?」

「村木先生からの二つの封筒。その中身は同じ問題に見えるんだけど!」

テトラ「……確かに、二つの色で塗り分けるという点では同じですが?」

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

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

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

人気の連載

おすすめ記事

ケイクス

この連載について

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

結城浩

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

この連載の人気記事

関連記事

関連キーワード

コメント

chibio6 「二部グラフは奇数長サイクルを持たない」という命題の逆の証明、サイクルがない場合から考え… https://t.co/4UZgadaX85 4ヶ月前 replyretweetfavorite

aramisakihime 双対! 2種類の点をそれぞれ集めた図なども含めて、視座の移動が感じられてとても面白いです。 4ヶ月前 replyretweetfavorite

Lsdu2DalePerry 「あっ、はい。そうでした。対偶と逆を勘違いしていました。命題Pの逆は・・・」 4ヶ月前 replyretweetfavorite

inaba_darkfox ばらばらに散らばってた白と黒の点が、つながりを保ったまま2部グラフっていう形できれいに分離されるのが凄いって思った 4ヶ月前 replyretweetfavorite