第291回 グラフ理論:僕らは隣接探偵団(前編)

新シーズン「グラフ理論」開始! ユーリと「僕」がいつものように楽しくゲームを始めたんだけど……あれれ?

登場人物紹介

:数学が好きな高校生。

ユーリのいとこの中学生。 のことを《お兄ちゃん》と呼ぶ。 論理的な話は好きだが飽きっぽい。

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

僕の部屋

は高校生。ここはの家。中学生のいとこ、ユーリが遊びに来ている。

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

「これまたいきなり」

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

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

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

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

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

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

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

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

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

連結ゲーム第一戦

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

紙に頂点を描いた

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

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

ユーリ「違うんかい」

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

(1)僕が、二頂点を辺で結んだ

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

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

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

(2)ユーリが、二頂点を辺で結んだ

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

(3)僕が、二頂点を辺で結んだ

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

(4)ユーリが、二頂点を辺で結んだ

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

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

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

(5)僕が、二頂点を辺で結んだ

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

「いいよ」

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

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

ユーリ「ルール?」

連結ゲームのルール

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

ルール1:辺は多重にしない

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

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

ルール2:ループを作らない

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

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

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

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

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

「こういうもの」

ルール3:サイクルを作らない

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

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

サイクル

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

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

  • ルール1:辺は多重にしない
  • ルール2:ループを作らない
  • ルール3:サイクルを作らない

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

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

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

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

連結ゲーム第一戦(再開)

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

(6)ユーリが、二頂点を辺で結んだ

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

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

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

(7)僕が、二頂点を辺で結んだ

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

(8)ユーリが、二頂点を辺で結んだ

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

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

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

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

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

人気の連載

おすすめ記事

さあ、数学ガールの世界に飛び込もう!

ケイクス

この連載について

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

結城浩

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

この連載の人気記事

関連記事

関連キーワード

コメント

nanay_desu 数学ガールのグラフ理論とかめっちゃいい https://t.co/zUo8wcAwMS 26日前 replyretweetfavorite

ouvsv ユーリ「犯人は君に決めた!」 ってかわいいな。(数学と関係ない・・・)> 29日前 replyretweetfavorite

hyuki 「読み返せば」と言ってからなぜか二時間も書き続けていました…😅 でも無事に完成。明日の第292回の更新をお楽しみにね!いまのうちに第291回を読んでおいて! https://t.co/v8cghijh37 30日前 replyretweetfavorite

ryochansq お、数学ガールの秘密ノートがグラフ理論に入った。競プロerも興味持てそうな内容。 約1ヶ月前 replyretweetfavorite