ケーキ同好会でも、プログラミングは必須スキルです！

グラフアルゴリズム グラフ1

初夏。

『夏至の候、梅雨明けを心待ちにする今日このごろでございます。皆様いかがお過ごしでしょうか。』

こんな感じでいいのかな。

教室の大きな窓から外に目をやると、相変わらず雨はしとしとと降り続けていた。

運動場はそこらじゅうに水たまりができていて、今日の帰りも通り抜けるのに苦労しそう。

『このごろ降り続ける雨に、なんとなく憂うつな気持ちになりました。』

こんなこと手紙に書くとさすがにおかしいかな。

とは言っても代案は思いつかないので、手持ち無沙汰に配布されたプリントに書かれている時候の挨拶の一覧を眺める。

ふと私の数席前に座っている望結ちゃんが目に入った。

望結ちゃんは机に向かって何かを読んでいるみたいだった。

チャイムが鳴った。

●

望結ちゃんと私はケーキ同好会っていう部活に入っているので、部室まで一緒に向かう。

ケーキ同好会という名前なのに、半分くらいプログラミングしてる気がするけど。

昨日ひまり先輩と哀先輩が競技プログラミングのコンテストで優勝したりしてるけど！

この実績が認められて廃部の話はなくなったらしい。それでいいの？

ところで、望結ちゃんがずっと手に持っている本が気になった。

「その本は？」

「うん。最近読み始めた」

望結ちゃんが持っていた黄色い本の表紙を私に見せた。

表紙には「グラフ理論」と本の名前がでかでかと書かれていて、なかなか主張が強い本だなあ。

というかすごく分厚い。

「......棒グラフみたいなもののもっと偉いやつ？」

部室の前まで来たので、私は鍵を差し込んで、部室の扉を開けた。

グラフはよく聞くけど、後ろに理論がくっついてて変な感じ。

「勉強し始めたばっかりだから詳しくはないけど。たとえば」

望結ちゃんは部室にある近くの椅子に座って、手に持っていた紙に川と橋を描いた。

「すべての橋をちょうど一度ずつ渡ることができる？」

【挿絵表示】

「......急にパズル？」

「グラフ理論と関係がある」

望結ちゃんが、はい、といって私にペンを渡す。

私は望結ちゃんの横に座って、とりあえず左の陸地から始まる方法がないか調べてみることにした。

あ。左か右の陸地から始める方法はどちらかだけ調べたらいいんじゃない？

橋の配置は左右対称だから。

......ちょっと自分天才かもしれない。

一筆書きできなかった。ありゃ。

「どうしても橋がひとつ余っちゃうなあ」

真ん中の陸地から始めるのかな、と思っていたら、

「すべての橋を渡るのはどう頑張ってもできない」

隣から無慈悲な宣告が聞こえたような気がした。

むむむ。

「証明できる？」

「......渡り方を全通り試す？」

始めてから2か月くらいだけど、考え方がだいぶ競プロに染まってるかも。

「実は、グラフを考えるともっと簡単に判定できる」

「おー！」

「陸地を〇で書いて、橋がある陸地同士を-で結んでみる」

【挿絵表示】

【挿絵表示】

「橋をちょうど一度ずつ渡ることができるか、という問題は

このグラフを一筆書きする方法があるか、という問題に変わった」

ほうほうなるほど。

なじみのあるものからなんだか知らないものに変わったから、さっぱりわかりません。

あれ、やっぱりこれ見たことがあるような......

「フィボナッチ数列を再帰関数で計算したときのやつだ！」

【挿絵表示】

「これについて研究するのがグラフ理論」

●

「グラフには頂点があって、〇で書かれてる。

頂点どうしの間を結ぶ線は辺と呼ばれる」

【挿絵表示】

「グラフ理論に詳しかったら、考えたいものを今みたいにグラフにして、

グラフ理論の定理を使って問題を簡単にしたりできるみたい」

「でも私たちはグラフ理論の定理を知らないから、今から自分たちで作る」

「定理を作る......！」

「グラフが一筆書きできる条件についての定理」

教科書に載ってる定理の使い方を学ぶ、みたいなことしかしたことないから新鮮かも！

「まずはグラフの特徴を表す量を見つけてみよう」

「数字的なものでいったら、グラフに頂点とか辺が何個あるとかかな？」

「そうだね」

このグラフは頂点が4つあって、辺がいち、にー、......5つあるね。

「あとは、この頂点から辺が何本出てるかなー、とか？」

「いいね。それを頂点の次数という」

望結ちゃんがグラフのそれぞれの頂点に次数を書き込んだ。

【挿絵表示】

「じゃあ、一筆書きと今見つけた量との関係を考えてみよう」

頂点の個数と辺の個数はあんまり関係なさそうかなあ。

一直線に頂点が並んでるグラフを考えると頂点と辺の個数を好きな数にできそう。

頂点の次数はどうだろう？

「ある頂点を通り抜けるときに辺が何本使われるかを考えてみよう」

「入ってくる一本と出ていくときにもう一本使われるね」

合計で二本使われるね。

望結ちゃんが頂点を通り抜けることを矢印を描いて表した。

「ある頂点から始めるときと、終わるときは？」

「ある頂点から始めるときは、

通り抜けるときと比べて入ってくるときがないから一本だけ使われるね」

「うん。

同じく、ある頂点で終わるときは出ていくことがないから一本だけ」

【挿絵表示】

「このことを考えると、頂点の次数を数えることで、

どの頂点から一筆書きを始めればよいかが分かるようになる」

「そっか、頂点の次数が奇数なら、その頂点から始めるか終わるかしないといけないもんね」

「次数が奇数である頂点がグラフに3つ以上ある場合、そのグラフは絶対に一筆書きできないことになる」

「1つでもだめだね、終わるところがないもん」

「じゃあ最初の問題に戻ろう」

【挿絵表示】

「次数が奇数の頂点が4つあるから、このグラフは一筆書きできない」

「じゃあ、すべての橋を一度だけ渡ることはできないんだね。」

かいけつかいけつ。

私が、うんうん、と首を上下に振るのをみて、望結ちゃんは疑問の顔を浮かべた。

「まだ仕事が残ってる。

次数が奇数である頂点が0個か2個のとき、一筆書きできるかはまだ分かってない」