第291回 シーズン30 エピソード1

グラフ理論：僕らは隣接探偵団（前編） ただいま無料

僕の部屋

ユーリ「ねー、なんかおもしろいこと、ないの？」

僕「これまたいきなり」

ユーリ「いきなりじゃないもん！　ユーリが来てから、お兄ちゃん、ずっと本読んでるじゃん。遊ぼーよ！」

僕「遊ぼうといってもね……」

ユーリ「クイズとか、ゲームとか、パズルとか、クイズとかないの？」

僕「クイズ二回出て来たぞ」

ユーリ「そーゆーの、いーから。お兄ちゃんの《灰色の脳細胞》から何か出したまえよ、ワトソンくん」

僕「混ざってる混ざってる。そうだなあ……」

ユーリ「その本なーに？」

僕「この本？　うん、そうだ。 じゃあ、こんな連結ゲームをしようか」

ユーリ「おっ、来た来た。そー来なくっちゃ。第一戦はじまりはじまり〜……で、連結ゲームって何？」

連結ゲーム第一戦

僕「まず、紙を用意して、適当に点を打つ。打った点のことを頂点（ちょうてん）と呼ぶことにしよう。たとえば、こんなふうにたくさんの頂点を描く」

ユーリ「ふむふむ。ここから星座を作る？」

僕「おっ、するどいな。違うけど」

ユーリ「違うんかい」

僕「僕とユーリで、交互に二頂点を結んでいく。たとえば、僕がこんな風に結んだとしよう。この結んだ線のことを辺（へん）と呼ぶことにする」

ユーリ「ふーん、次はユーリの番ってこと？　どの二頂点を結んでもいいの？」

僕「うん、どの二頂点を結んでもいい」

ユーリ「じゃあ、こんな風に結んでもいい？」

僕「いいよ。いまユーリが描いた辺はまっすぐだったけど、 辺は曲がっていてもいい。 ぐるっと回りこんでもかまわない。たとえば、僕はこんな風に結ぼう」

ユーリ「よくわかんないけど、ユーリはここに決めた。真実はいつもひとつ！」

僕「コナンじゃないんだから」

ユーリ「犯人は君に決めた！」

僕「犯人を決めるなよ。じゃあ、僕はここを結ぼう」

ユーリ「あっ、そーゆーふーにつないでもオッケーなんだ」

僕「いいよ」

ユーリ「ふーん……でもさ、これ、何がおもしろいの？　どの二頂点を結んでもいいならゲームでも何でもないじゃん」

僕「そうだね。実は、ちょっとしたルールがある。ルールがなかったらゲームにならないからね」

ユーリ「ルール？」

連結ゲームのルール

僕「辺を描くときに、すでに辺で結ばれている二頂点を結んではダメ。つまり、こういう多重になった辺を描いてはダメ。もうすでに二頂点を結んだ辺が描いてあるから」

ユーリ「ほほー。ちょいゲームっぽくなってきた。他にもルールあんの？」

僕「あるよ。同じ頂点に戻ってくる辺はダメ。つまり、こんなふうにループを作っちゃダメ」

ユーリ「このリフジンさがたまらんなー」

僕「理不尽さって……。ゲームのルールはたいてい《○○しちゃダメ》だよね。たとえばサッカーではボールを手で持っちゃダメ」

ユーリ「ゴールキーパーは手で持ってもいーじゃん。てか、話を先に進めてくれたまえ、エラリイくん」

僕「それから最後のルールとして、サイクルを作っちゃダメ」

ユーリ「サイクルって何？」

僕「こういうもの」

ユーリ「これがサイクル？」

僕「ひとつの頂点から辺をたどって最初の頂点まで戻って来ることができる。そんなふうに選んだ辺の集まりがサイクル。サイクルができるような辺を描いてはダメ」

ユーリ「ぐるっと回れちゃダメってことね。さらなる理不尽さが加わった！」

僕「いま言った三つのルールを守りながら、交互に辺を描いていく。そして描けなくなったら負け。それが連結ゲームなんだ」

• ルール１：辺は多重にしない
• ルール２：ループを作らない
• ルール３：サイクルを作らない

ユーリ「りょーかい！　辺は多重にしない。ループを作らない。サイクルを作らない。真夜中を過ぎたら森に入らない」

僕「ルールを勝手に作らない」

ユーリ「んじゃ、第一戦再開！」

僕「僕はもう描いたから、次はユーリだよ」

連結ゲーム第一戦（再開）

ユーリ「うーん……どこを結ぼーかなー。じゃ、ここ」

僕「ずいぶん回り込んだなあ！」

ユーリ「ルールは守ってるっしょ？」

僕「そうだね。じゃあ、僕はここ」

ユーリ「そっか、間に入り込む手もあるんだ……じゃ、ユーリはここ」

僕「いやいや、それはダメだよ」

ユーリ「なんで？　どこ結んでもいいんでしょ？」

僕「だって、ルール３に違反している。サイクルができてるからね。全体をよく見ないとサイクルを見落とすよ」

ユーリ「あっ、ほんとだ。紛らわしーにゃあ」

僕「回り込んで描いたのはユーリだからね、言っておくけど」

ユーリ「へいへい、そーですねっと。……んじゃ、ここ」

僕「なるほど。じゃあ、僕はここ」

ユーリ「んー、じゃユーリは……」

僕「どこを結ぶ？」

ユーリ「ユーリはね……ありゃ？　ちょっと待って。 あーっ！　やっぱりダメかーっ！」

僕「うん、これで第一戦は僕の勝ちだね」

ユーリ「むー、ぐるっと回ったのが敗因かにゃあ……」

僕「こんなゲームだよ。わかった？」

ユーリ「もっかいやる！　今度は勝つ！　ユーリ先攻でもいい？」

連結ゲーム第二戦

僕「うん、ユーリ先攻でいいよ。じゃあ、第二戦は新しい紙でやり直そう」

ユーリ「今度はすなおに行くぞよ」

ユーリ「……」

僕「どうした？　次はユーリの番だよ」

ユーリ「……また負けそう」

僕「そうかな？」

ユーリ「うん……絶対負ける。だってね、次ユーリが描いて、その次お兄ちゃんが描いたら、もう描けなくなるもん。絶対！」

僕「絶対？」

ユーリ「絶対。だって……む？　むむ？」

僕「……」

ユーリの推理

ユーリ「お兄ちゃん、第一戦の紙見せて」

僕「ん？　これのこと？」

ユーリ「第一戦のときは頂点が $10$ 個だった。第一戦って、何気にお兄ちゃんが先攻だったよね」

僕「そうだね。ルール説明もあったし」

ユーリ「第二戦のこれは頂点が $11$ 個ある。第二戦って、お兄ちゃんは後攻だった……」

僕「うん。ユーリが先攻をやりたいと言ってたから」

ユーリ「もひとつ質問いいかにゃ。 第二戦では、ユーリが先攻になることが決まってから、 お兄ちゃんが頂点を描いたよね。先攻・後攻が決まった後で頂点の個数が決まった……？」

僕「ユーリのような勘の良い……」

ユーリ「テンプレいいから。もーわかった！　この連結ゲーム、最初の頂点の数で勝敗決まるんでしょ！」

僕「その通り。よく見抜いたなあ」

ユーリ「ちっちっち。簡単な推理だよワトソンくん。 それに、お兄ちゃんがずるっこするのはこれが初めてじゃないからね」

僕「そうだっけ」

ユーリ「そーだよー！　よくあるパターンじゃん！」

僕「それはさておき、頂点の数で最初から勝敗が決まるというけど……もうちょっと詳しく指摘してほしいなあ」

ユーリ「んー……ユーリの勘では、頂点が偶数個のときは先手必勝で、 頂点が奇数個のときは後手必勝なんじゃね？」

僕「なるほど。それがユーリ名探偵の推理なんだね」

ユーリ「そーだよん。だから、お兄ちゃんは点を $10$ 個描いたときは先攻を選んだんでしょ。偶数だから。 そして、ユーリが先攻になったときは、点を $11$ 個描いた。それは自分が勝つため！」

僕「名推理だ！」

ユーリ「真実はいつもひとつ！　整数はいつも偶数か奇数！」

僕「でも、頂点が $10$ 個のときと、 $11$ 個のときの二戦しかやってないよね。その他の数でも《必ず》勝敗が決まると言える？」

ユーリ「言えると思うよん」

僕「それから、ポイントは頂点の数じゃなくて、頂点の配置の可能性はないかな。頂点が偶数か奇数かだけで《必ず》勝敗が決まる？」

ユーリ「うー、決まると思うけど……」

僕「それから、辺の描き方で勝ったり負けたりするかもしれないよね。 ほんとうに数だけで《必ず》勝敗が決まる？」

ユーリ「ぐぬぬ……ちょっと待って。なぜにユーリが責められるのじゃ。わらわに何を求めておるのじゃ」

僕「キャラ壊れてるぞ。うん、つまりね。《必ず》というためには、証明したくなるよね、ってこと」

ユーリ「証明？　証明って数学の証明？」

僕「そうだよ。数学の証明。頂点が何個でも、配置がどうであっても、辺の描き方によらず……頂点が偶数個ならば先手必勝で、 頂点が奇数個なら後手必勝であることを証明してしまえばいい」

ユーリ「頂点に辺を描くのが、数学なの？」

僕「そうだよ。数学で扱うことができる。グラフ理論だね！」

ユーリ「ぐらふりろん。……でも、ぐにゃぐにゃだよ？」

僕「ぐにゃぐにゃ？」

ユーリ「辺はいくら曲がってもいいし、回り込んでもいい。 そんなぐにゃぐにゃなのに、数学なの？」

僕「ああ、そういうこと？　うん、そうだね。 辺はどんなに曲がっていてもいい。 数学で図形を扱うときは三角形や円や長方形のように、何ていうか『きちんとした図形』がよく出てくるけれど、 それだけが数学じゃないよ」

ユーリ「あっ、あっ、あっ、えーと……ケーニッ？なんとかの橋だ！」

僕「もしかして、ケーニヒスベルクの橋のこと？　一筆書きの問題だね」

ユーリ「それそれ！　一筆書きでも、道を曲げてもよかったよね。この連結ゲームとおんなじだ！」

僕「その通りだね。まさにそれだよ」

ユーリ「宣伝テトラさん……」

僕「一筆書きの問題は、グラフ理論でよく出てくる話題のひとつ。 グラフ理論では、頂点同士がどんなふうにつながっているかが大事なんだ。 どの頂点とどの頂点が隣接しているかが大事であって、 辺がまっすぐか曲がっているかは気にしない」

ユーリ「りんせつ？」

僕「隣り合っているってこと。頂点Aと頂点Bが辺で結ばれているようすを考えると、 頂点Aと頂点Bが隣り合っているといえるよね。そういう状況を《隣接している》と呼んだんだ」

ユーリ「ところで、どーやって証明するの？　辺を描いていく連結ゲームで、頂点が偶数個だったら先手必勝、奇数個だったら後手必勝……それを証明するって、 いったいどーすんだろ。頂点は何個描いても関係ないわけでしょ。 $5000$ 兆個描いてもいいわけだし」

僕「$5000$ 兆個の頂点だったら、先手必勝になるよ。偶数だからね」

ユーリ「どう証明すんの？」

僕「うん。証明する前にやるべきことがあるね。 それは《小さい数で試してみる》ってことだよ」

ユーリ「さっきやった。 $10$ 個」

僕「もっとずっと少ない数で試してみよう。たとえば、頂点が $1$ 個の場合」

頂点が $1$ 個の場合

ユーリ「頂点が $1$ 個！　うわっ、しょーもない連結ゲーム！」

僕「後手必勝になるかな？」

ユーリ「えっと……あー！　そーゆーことか！　うん、後手必勝だよ。 だって、ループを作っちゃいけないんでしょ？　《ルール１》だ。 頂点が $1$ 個しかないから、もう辺は描けない。だから、先手になったら負け。何ということでしょう」

僕「うん、頂点が $1$ 個の場合は後手必勝。では、頂点が $2$ 個の場合はどうかな？」

頂点が $2$ 個の場合

ユーリ「うん、頂点が $2$ 個だったら、先手必勝になるね。だって、先手が辺を描いたら、後手はもう描けないもん」

僕「そうだね。もしも、ループはダメだし、無理に辺を描いたら、辺が多重になってしまう。《ルール１》に反するわけだね」

ユーリ「ははーん……」

僕「何か気がついた？」

ユーリ「頂点が $1$ 個の場合、頂点が $2$ 個の場合と来たら……」