第416回 シーズン42 エピソード6

《距離》を使って形を探る（後編）

図書室にて

テトラ「先輩！　ちょうどいいところに！」

僕「ちょうどいいところ？」

リサ「……」

テトラ「先日《格子点の世界》のお話をうかがいましたよね」

僕「うん、そうだった。 《格子点の世界》で何歩歩くかという《距離》を使って《円》や《楕円》や《双曲線》を描いたよね（第415回参照）。 また何か、新しい形を探り出したの？」

テトラ「いえ、《新しい形を探り出した》んじゃなくて——《形の新しい探り出し方》を考えていたんです。 いわば、探り出し方を探ってたんですねっ！」

僕「ええと……形の新しい探り出し方？」

リサ「……」

《単位円》

テトラ「あたしが最初に考えていたのは《単位円》のことです」

僕「単位円。原点が中心で半径が $1$ の円」

テトラ「はい、そうです。 そして、その概念を《格子点の世界》に持っていきます。 原点から $1$ 歩だけ進んだところにある点全体の集合——つまり、それが、いわば《単位円》です……よね？」

僕「そうだね。原点から $1$ 歩だけ進んでたどり着ける点を、 原点からの《距離》が $1$ の点と見なすわけだから。 だから、 $$ \SET{(1,0),(0,1),(-1,0),(0,-1)} $$ という $4$ 個の点からなる集合は、《格子点の世界》の《単位円》と考えることができる。確かにその通り」

テトラ「単位円は大切だなあ……とあたしはいつも思っています。 たとえば、三角関数を定義するときも単位円が出てきますし。 なのであたしは、この $4$ 個の点をじっと見ていました……」

僕「なるほど」

テトラ「……そして、あたしはグラフを思い浮かべたんです」

僕「グラフ？」

グラフ

テトラ「はい。グラフといっても関数のグラフではなく、頂点と頂点を辺で結んだグラフです」

僕「うん、わかるよ。グラフ理論の簡単な話は以前やったことがあるから（第291回参照）。 たとえばこういうものだよね」

テトラ「はい。 それでですね、あたしが単位円を考えたときにグラフを思い浮かべたのは、 スタートとなる頂点をこんなふうに決めれば、 そこから $1$ 歩進んだところにある頂点さんたちがイメージできたからです。 それもまた単位円みたいなものだなあ……と思いました」

僕「ははあ……グラフで $1$ 本の辺を通ったところにある頂点だね。 確かに単位円み（・）があるなあ」

テトラ「一つのグラフには、たくさんの頂点があります。 そして頂点と頂点を結んでいる辺があります。 でも、すべての頂点が互いに結ばれているとは限りません」

僕「そうだね」

テトラ「《格子点の世界》では、位置関係ですぐに $1$ 歩がわかりました。 上下左右で隣にある点たちです。 つまり、《格子点の世界》をグラフとして考えるなら、 それぞれの頂点は、上下左右の $4$ 頂点との間に辺があると考えることができます」

僕「確かに」

テトラ「でも、一般のグラフでは、位置関係で隣の頂点が決まるわけではありません。 そもそもグラフでは空間的な位置関係というのはない（・・）からです。あ、いえ……ないわけじゃないですね。 何というんでしょうか。どの頂点とどの頂点が隣り合っているかという隣接関係は、 辺によって決められているといいたいんですが……伝わってます？」

僕「うん、テトラちゃんの言いたいことはわかるよ。 《二つの頂点 $u,v$ のあいだに辺が存在する》ことによって《頂点 $u$ と頂点 $v$ が隣り合っている》ことを意味している——っていいたいんだよね」

テトラ「そうです、そうです」

僕「グラフといえば、村木先生からもらった《カード》を使って、 いろんな問題をいっしょに考えたよね」

テトラ「《直線国境諸国巡遊偶数回横断問題》のことですねっ！あれは驚きました（第293回参照）」

僕「よく覚えてるなあ。《機材の予約問題》というのもあったね（第295回参照）」

テトラ「はいはい」

僕「《五色定理》もあったなあ（第299回参照）！ ミルカさんからも、 それからリサちゃんからも、グラフのことをいろいろ教えてもらった」

リサ「《ちゃん》は不要」

テトラ「ですです。 ——そんなふうに考えを進めてきて、 あたしは、グラフが《格子点の世界》を一般化していると思いました。 いわばスタートとなる頂点から $1$ 歩進んだところにある頂点全体の集合も このグラフにおける《単位円》といえそうだと気付いたとき、とっても興奮したんです。 また、新しい世界とつながった！と感じたからです。《座標平面の世界》《格子点の世界》そして《グラフの世界》……」

僕「うん、その気持ち、わかるわかる！」

テトラ「そして——そこからあたしは《グラフの探索》について考え始めました」

グラフの探索

僕「グラフの探索……？」

テトラ「はい。スタートとなる頂点から始めて、グラフの頂点から頂点へ、 辺をたどって（・・・・）渡り歩いて、ゴールとなる頂点を探していく探索です」

僕「……」

テトラ「たとえば、こんなグラフがあったとします。一つの頂点をスタートとして、 別の頂点をゴールとします」

僕「ああ、わかったわかった」

テトラ「はい。スタートから $1$ 歩進んだ頂点、さらにそこから $1$ 歩進んだ頂点……というのを、 ゴールが見つかるまで繰り返していくんです。このグラフの例ですとスタートから $3$ 歩でゴールまで行けます」

僕「それはおもしろいね！　……ところで、いま思ったんだけど」

テトラ「？」

僕「これって先日テトラちゃんが言ってた《ホイヘンスの原理》と同じ話になってるよね（第415回参照）」

テトラ「そうですっ！ いま、その話をしようと思ってたところです。 さすが先輩、すぐ気付きますね」

僕「ぴったり同じだよね」

テトラ「はい。 波面のすべての点が波源になって、 そこから素元波が出て行くことで、次の瞬間の波面ができるという《ホイヘンスの原理》は、 波面上のすべての点が波源になるわけですが、 それは、グラフの探索でいうと、 そこまでにたどり着いた頂点を新たなスタートだと考えて、 そこから新たなグラフの探索を始めたのと基本的には同じなんですっ！」

僕「なるほどなあ……ということは、グラフの探索でも《波面》があるわけだよね。 つまりね。ゴールを探索して進んでいく途中の最前線にある頂点の集合のこと」

テトラ「そういうことになります。 グラフの探索でゴールを探し求めていく過程は、 その《波面》を少しずつ進めていく過程なんですっ！」

リサ「最短経路問題」