第291回　グラフ理論：僕らは隣接探偵団（前編）

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

僕の部屋

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

僕「これまたいきなり」

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

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

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

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

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

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

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

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

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

連結ゲーム第一戦

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

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

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

ユーリ「違うんかい」

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

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

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

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

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

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

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

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

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

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

僕「いいよ」

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

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

ユーリ「ルール？」

連結ゲームのルール

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

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

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

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

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

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

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

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

僕「こういうもの」

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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