迷路パズルでもグラフ理論が大活躍さ！

3-1．「枝分かれ」と言えばこのグラフ

　……考察と言っても、まぁ、割と知られている方法が１つありますよね😓
　「袋小路を続々と塗りつぶしていけば正解ルートが露わになる」という方法。
　これをグラフ理論で考察してみたいと思います。

　さて。
　いきなりですが、迷路にある物と言えば何でしょう？
　袋小路？　正解！
　他にはＴ字路や十字路、入口や出口もありますね。
　つまり、迷路には「枝分かれ」と「終端」があちこちに存在するわけです。

　じゃぁ、それをグラフで表現するとどうなるか？
　Ｔ字路・十字路・袋小路を頂点とし、通路を辺だと考える。
　すると、こ〜んなグラフができあがる！

　おぉ〜、これはまさに木グラフじゃぁないですか！
　迷路は木グラフで表現できるんですね。
　まぁ、木というよりは基板の回路にしか見えないけどね😅
　でも、これも立派な木グラフです。

　さて、迷路の目的は「スタート地点からゴールへ行く」ということですよね。
　これは木グラフで言うと何に相当するんでしょう？
　それは「頂点Ｓから頂点Ｇへ辺をたどる」ということです。
　では、そのルートはどうやって見つけるんでしょう……？

　当然ですが、迷路を攻略する上で、袋小路は邪魔なわけですよね。
　となれば「袋小路を塗りつぶせばいい」というアイデアが生まれるのは必然と言えます。
　このアイデア、木グラフではどういう行為に相当するんでしょう？

それは、末端の枝を刈ることと同じである。

　木グラフにおいて、端点は袋小路と同じです。
　だから、端点を辺ごと取っちゃえばいいんです。
　まさにガーデニングで言う「庭木の剪定」と同じですね！
　あっ、迷路の世界では、テレショップで大人気の高枝切りバサミは必要ありません😅

　迷路の世界における庭木の剪定は、とことんまで行います。
　袋小路を塗りつぶすと、枝分かれを失って袋小路に変化する箇所が現れます。それも塗りつぶします。
　そうやって、枝という枝をことごとく切り落とす。
　そうすれば、一本の幹だけになる。
　頂点ＳからＧまでの一本道、つまり正解ルートが露わになるというわけなんです。

　迷路の正解ルート、木グラフの一本道。
　両者が同じなのは一目瞭然ですね😊

3-2．グラフが方向を装備する！

　さ、割と知られた手法の話はここまで。
　ここからは、別の視点で考察してみましょう。
　題材にする迷路とグラフはセクション3-1を流用します。
　そして、この木グラフをちょっとばかり改造します！

　考察の方法は至極単純。
　基本に忠実、王道を行く手法をとります。

スタートからゴールまで、迷路を地道に探索してみようか！

　探索というと、右手法や左手法を思い浮かべた方々はたくさんいることでしょう。
　ここでは、それすら使わない基本のキに立ち返ります。
　迷路をあちこち歩きましょう！
　ま、せっかく木グラフがあるのだから、迷路ではなく木グラフの方を探索してみます。

　まず、頂点Ｓから辺をたどると、頂点Ａに着きました。
　そこで、「ＳからＡに来たよ〜♪」ということを表すために、辺に「方向」を付けましょう。
　ＳからＡへ、上向きの辺になりました。

　頂点Ａからは３方向に分かれていますが、まずは左折してみます。
　すると、頂点Ｂに着きました。
　ここでも「ＡからＢへ来た」ことを示すために辺を方向付けします。
　以下、同様にして、頂点に着くたびに「来た方向に沿って辺を方向付け」していくんです。
　そうすると、下図のように、すべての辺に方向が付きました。

　実は、グラフ理論には、こういう「方向付けをしたグラフ」という物もあるんです。
　これを 有向グラフ と呼びます。
　また、辺に方向が付くと、名前は 有向辺 または 弧 に変わります。

　迷路を隅々まで探索して得られた、この有向グラフ。
　このグラフからは、あることが成り立つようになりました！

• 頂点Ｇから矢印に逆らって有向辺をたどれば、まったく迷わずに頂点Ｓにたどり着く。
  その道筋をＳから逆にたどれば、それが正解ルートになる。

　ＳからＧへ向かう方向だと分岐ばっかりで、正解ルートを見つけるのに苦労する。
　ところが、ＧからＳへ向かう方向だと一発で正解ルートがわかってしまう。
　驚きの結果ですね！

　こうなる理由は簡単です。
　どの有向辺も「Ｓから来た方向」を示しているからです。
　ということは、有向辺の方向を逆にすれば、すべて「Ｓへ行く方向」になるんです。

「迷路」なのに迷わずに行けるなんて、なんて画期的な方法なんだ！

　……と言いたいところですが、残念ながら、この方法は実戦では役に立ちません。
　だって、迷路をくまなく歩き回ってるんですもの😅
　辺に方向付けしている最中にゴールにたどり着いちゃうのさ😅

　でも、有向グラフ化することで別の見方が生じます。
　パソコンや Web関連のとある物になぞらえてその話をしましょう。

3-3．迷路はアレと構造が同じだった

　グラフにおいて、頂点や辺の視覚的な性質（形状や位置関係など）は意味を持ちません。
　だから、頂点同士の繫がりを勝手に変えない限り、頂点や辺を自由に変形・移動できます。
　迷路の有向グラフを実際に変形してみると、枝分かれの構造になりました。

　これ、何かに似てるなぁ……と考えていたら、ある物に気がついた。
　パソコンや Webサイトのディレクトリ構造と同じだった！

　頂点Ｓはルートディレクトリ。頂点１はＳの子ディレクトリ。
　そこから分岐して、頂点２, 10, 31は孫ディレクトリ。
　以下、延々と子孫をたどって、Ｇは末端のファイルや Webページ。
　こういった捉え方もできるんですね。
　Ｇの URL は…… https://www.S.com/1/10/12/14/15/19/20/G.html といった感じかな？
　この URL からは「トップページは https://www.S.com/ だろうなぁ」と簡単に推測できますが、これはさっき述べた「ＧからＳへ向かう方向だと一発で正解ルートがわかる」ということと似てますね。
　ＧからＳへの道筋は１本しかないですもんね。上へ上へと親ディレクトリをたどれば良いだけだから。

　迷路と枝分かれ構造は本質的に同じだった。
　ということは、前者で成り立つ事柄は後者でもそのまま成り立ちます。
　例えば、迷路では有名な 右手法/左手法。
　迷路の左手法は枝分かれ構造でも左手法で表現できるんです。

　ちなみに、プログラミングを嗜んでいる方々はご存じのことですが、この左手法は「根付き木における深さ優先探索」と同じです。
　左手法と深さ優先探索、見た目は違うように見えても根っこは同じだったわけです。
　こういうことがわかるのも、グラフ理論のおかげと言えますね。

　「まったく別物のように見えるのに実は構造が同じだった」ということは時にあります。
　同じ構造だと知るだけでも理解がグッと深まります。
　個別に覚えていた２つの物が急速に繫がりを持って、一気に知識や思考の幅が広くなりますもんね。
　別々の世界にポツンポツンとあった知識たちが繋がる。
　まさに「点と点が線で結ばれる」という、勉強していて嬉しい瞬間ですよね。

　点と点が線で結ばれる。
　あら、ここにもグラフ理論が絡んでるやん！
　すげぇな、グラフ理論って。

4-1．壁伸ばし法とは何ぞや？

　まぁ、とりあえず「壁伸ばし法って何だ？」という話ですよね。
　まずはそれを説明しましょう。

図 4-1

　マスがタテヨコに並んだまっさらな盤面を用意します。
　盤面には既に外壁が描かれています。
　マスは点線で区切られ、点線同士の交点には小さい●がありますね。
　すべての●から点線に沿って線を引いていき、迷路の壁を作っていきます。

図 4-2

　まぁ、実際にやってみましょう！
　任意に●を１個選び、上下左右に点線を次々たどって線を引いていきます。
　もし線が既存の壁にぶつかったら、そこで終わり。

　あ、図4-2 の緑色のように、引いてる線に自らぶつかってはいけません！
　そうならないように線を引きましょう。

図 4-3

　孤立している●がまだ存在するなら、同様に線を引いていきます。
　既存の壁にぶつかったら終わり。
　すべての●が壁と繋がるまでこれを繰り返します。

　あ、「既存の壁」は外壁でなくてもＯＫです。
　「既存」でありさえすればＯＫ！
　「外壁に繋がっている壁」と解釈するとわかりやすいかも。

図 4-4

　すべての●が壁と繋がりました。

　あとはスタートとゴールを適当につけて、これで迷路のできあがり！
　これが 壁伸ばし法 です。

　この方法で作ると、ループも分断もないオーソドックスな迷路ができあがります。
　当セクションでは、木グラフの視点でこの迷路を解説してみようと思います。

4-2．迷路の壁に秘密あり

　木グラフの視点で考察するために、壁伸ばし法をもう一度おさらいしましょう。

図 4-5

　まず、まっさらな盤面を用意しましょう。
　この時点で、スタート＆ゴール地点の周りには外壁が２つありますね。
　赤色＆青色と色分けしておきましょう。
　そして、頂点も適宜付けておきます。
　すると、こういうことが言えますね。

• 赤色も青色も木グラフである。
• 赤色と青色は接していない。

　まぁ、木というかコの字ですね😅
　でも、これも立派な木グラフです。

図 4-6

　先ほどの壁伸ばし法と同じ手順で作ってみます。
　ある点から壁が伸びて外壁にぶつかった。
　既存の壁にぶつかったら、その壁と同じ色に塗りましょう。
　２色とも壁が増えましたが、それでもこういうことが言えますね。

• やはり赤色も青色も木グラフである。
• やはり赤色と青色は接していない。

図 4-7

　さらに続けていって、迷路が完成！
　赤色＆青色ともに複雑な形になりました。
　この時、こういうことが成り立っています。

• 赤色・青色ともに木グラフである。
• ２色の木グラフは接していない。
• この２色以外の木グラフは存在しない。

　実は、この作り方をした時、できあがった迷路はこういう性質を持っているんです。

• この迷路にループは存在しない。
• この迷路は壁で分断されていない。

　こうなる理由はこのページで説明しましょう。

　赤色と青色の木グラフを壁とし、ループも分断もない迷路ができましたね。
　あとは、この迷路をちょいと解いてみたい！
　さて、どうやって解こうかな……？

　……と思った矢先に、実は悲しいお知らせがある。
　この迷路、解くまでもないんです。
　なぜなら、もう正解ルートが見えてしまっているから。

• 赤色と青色の壁に挟まれたルートを歩けば良い。
  たったそれだけで自然とゴールにたどり着く！

　すごい😅
　ホントにたどり着いた😅

　理由は簡単です。
　木グラフは一繋がりなので、同色の壁は一繋がりになっています。
　つまり、両サイドが同色である通路を歩いている時、そこから奥へ進んでも必ず袋小路に着いちゃうんです。
　だから、両サイドが異なる色の道を歩くしか術がありません。

　ちなみに。
　セクション3-1で行った「袋小路塗りつぶし」をやると、この理屈はすごく明快になります！
　袋小路を赤色＆青色で塗りつぶしてみると……

　おおっ！
　こりゃぁ「赤と青の間を歩け〜！」の真意がハッキリわかる😃

　ただ、残念なことが１つ。
　上記の理論は「スタートもゴールも迷路の外側になければならない」という条件が必要です。
　迷路によってはゴールが内部にあったりしますが、そういう迷路には使えません。
　壁が全部一繋がりになっちゃいますもんね。

4-3．秘技・回転ドアの術！

　まず、以降の解説に先駆けて、皆さんに忍術を伝授します。

図 4-8

　頂点を２個用意し、それらを辺で結びます。
　今は辺を点線で表していますが、これに次の操作を施してみましょう。

辺だけを 90°回転させる！

　まるで回転ドアのように、辺の中心で辺を回転させる。
　回転後の点線は太線で表すことにしましょう。
　これを、当セクションでは 回転ドアの術 と呼ぶことにします。
　「ダサい名前ｗ」とか言わないで😅

　まぁ、いきなり「回転ドアの術〜ッ！」なんて言われても何のことやらですよね😅
　でも、この術も迷路に関係があるので、術の話を続けたい。

図 4-9

　小さいサイズを例に、術を説明していきましょう。
　25個の頂点を格子状に繋げたグラフを用意します。
　これは グリッドグラフ と呼ばれる物です。
　ついでに、外壁も描いておきましょう。

　まぁ、頂点をマスに見立てて、マスが５×５に並んだ盤面だとでも思ってください😊

図 4-10

　今、25個の頂点を辺で一繋がりにした木グラフを１つ作ります。
　例えば、図4-10 のように。
　このようにして作った木グラフを、元のグラフの 全域木 と呼びます。
　以降、「全域木」はグリッドグラフの全域木を指すものとします。

　あっ、「必ずすべての頂点を一繋がりにする」ことに注意してください。
　孤立した頂点があってはＮＧ。グラフが分離していてもＮＧです。

　さて、全域木を作ると、いくつかの辺は使われずに残りましたね。
　そこで、その未使用の辺に回転ドアの術をかけてみましょう。

愚羅腐（グラフ）忍法！　回転ドアの術ッ！

図 4-11

　回転後は太線で表すことにして、盤面はどう変わったでしょうか？
　図4-11 の通りになりました。

あれ？
迷路になってるじゃぁないですか！

　そうなんです。
　グリッドグラフから全域木を抽出して、残りの辺に回転ドアの術をかけてやる。
　そうしたら、なんと、迷路ができあがるんです。

　この理由は、壁と未使用の辺の間に１対１対応があるからですね。
　壁があれば点線はない。
　壁がなければ点線はある。
　図4-11 の壁に「逆回転ドアの術」をかけてやると、図4-9 に戻ります。

　回転ドアの術だけで迷路ができた。
　ということは、グリッドグラフ, 全域木, 壁の３つには何やら関係がありそうですね！
　図4-9 のグリッドグラフには 40本 の辺がある。
　図4-10 の全域木に使われている辺は全部で 24本。
　残り 16本 に回転ドアの術をかけて壁にしたら、迷路ができた。

あぁ〜、真っ先に 16＋24＝40 が見えるねぇ……。

　もちろんそれは正しい。
　が、もう少し詳しく掘り下げましょう。
　木グラフに関して１つの定理があります。これを使います。

• \(k\) 個の頂点を持つ木グラフは、必ず \((k-1)\) 本の辺を持つ。

　これは、実際に木グラフを描いて確かめると良いでしょう。
　１本の辺でしか繋がっていない頂点が必ずあるので、その頂点を辺ごと取り除いていくとわかります。
　セクション3-1で行った「庭木の剪定」と同じ要領ですね。
　辺がなくなるまで続けると頂点が１個だけ残るので、上記の定理が成り立つんです。

　木グラフの辺の本数は、頂点の個数にしか依存しません。
　だから、次のことが言えます。

• ５×５に頂点を並べたグリッドグラフは、必ず 40本の辺を持つ。
• そのグリッドグラフから抽出した全域木は、必ず 24本の辺を持つ。
• 回転ドアの術をかける対象は、決まって 16本の辺である。

　必ず。必ず。決まって。
　つまり、グリッドグラフのサイズが決まった瞬間、この３要素も自動的に決まっちゃうんです。
　５×５のグリッドグラフの場合、常に 40本, 24本, 16本 なんですね。
　そして、これは任意のサイズに一般化できます。

• \(m \times n\) の矩形状に頂点を並べたグリッドグラフは、必ず \((2mn-m-n)\) 本の辺を持つ。
• そのグリッドグラフから抽出した全域木は、必ず \((mn-1)\) 本の辺を持つ。
• 回転ドアの術をかける対象は、決まって \((m-1)(n-1)\) 本の辺である。

　なぜその本数になるのかを軽く証明すると、こんな感じ。

　下図の \(m \times n\) サイズのグリッドグラフには、水平の辺が \(m(n-1)\) 本、垂直の辺が \((m-1)n\) 本あります。
　だから、辺の総数は

\[ \text{(辺の総数)} = m(n-1) + (m-1)n = 2mn - m - n \]

　また、グリッドグラフから抽出した全域木には頂点が \(mn\) 個あります。
　だから、全域木の辺の本数は

\[ \text{(全域木の辺数)} = mn-1 \]

　よって、回転ドアの術の対象となる辺の本数は

\begin{align} \text{(辺の本数)} &= (2mn - m - n) - (mn - 1) \\ &= mn - m - n + 1 \\ &= (m-1)(n-1) \end{align}

　「必ず、必ず、決まって」と３要素が固定値だったということは、さまざまな要素も固定値になりそうですね。
　一例を挙げるとこんな感じ。

• ｍ×ｎサイズの迷路を入口から入り、右手法/左手法 を使って「１マス＝１歩」で迷路内部を全探索するとする。
  全探索を終えて入口に戻った時、\(2(mn-1)\) 歩いたことになる。

　こういうことも成り立ったりする。
　この理由は、迷路の全探索は全域木のすべての辺を往復１回ずつたどることと同じだからです。
　これも固定値 \(2(mn-1)\) でしたね。

　３要素をうまいこと応用すれば、もっと奥深い結論が得られそうですね。
　例えば、ループが１カ所ある迷路に対しては、全域木に辺を１本増やして考えれば良い。
　迷路が２つに分断されていれば、逆に辺を１本減らして考えれば良い。
　他にも、さまざまな要素を研究できそうに思います。

　迷路は入口から出口へたどるだけの遊びではなかったですね。
　グラフ理論だけでもこれだけの考察ができるし、他の方法でもいろいろ法則が見つかるでしょう。
　こういった研究も、迷路の楽しみ方のひとつかもしれませんね。

　ここからは余談です。
　そういえば、壁の枚数は \((m-1)(n-1)\) でしたね。
　綺麗に因数分解できています。
　それについて軽く語った後、最後に回転ドアの術で当ページを締めくくりましょう。

図 4-12

　セクション4-1の壁伸ばし法を利用して迷路を作りました。
　その迷路で壁の枚数を確かめてみましょう。
　盤面のサイズは タテ10×ヨコ14 です。

　実は、●から壁を伸ばした時、壁の枚数に関して法則があります。
　図4-12 でわかるかも。
　１個の●と１枚の壁がキッチリ対応しているんです。

　●と壁の間には１対１の対応がある。
　ということは、できあがった迷路には●と同じ枚数の壁がある。
　じゃぁ、●の個数を調べれば……。

　というわけで、壁の枚数は 9×13 枚。
　まさに \((m-1)(n-1)\) の通りですね😃

　最後は、回転ドアの術でセクション4-1の迷路を再び作ってみます。
　下図の通り、はい完成！
　……と、術が綺麗にキマったところで、これにてドロン！
　ニンニン！