gooブログはじめました!

写真付きで日記や趣味を書くならgooブログ

再び迷路問題に挑戦する

2011-12-13 16:02:14 | ブログ

 再び新聞のパズル欄に載っていた別タイプの迷路問題に挑戦することにした。そのパズルをより単純化したもので示すのが下図のモデルである。

<shapetype id="_x0000_t75" stroked="f" filled="f" path="m@4@5l@4@11@9@11@9@5xe" o:preferrelative="t" o:spt="75" coordsize="21600,21600"><stroke joinstyle="miter"></stroke><formulas><f eqn="if lineDrawn pixelLineWidth 0"></f><f eqn="sum @0 1 0"></f><f eqn="sum 0 0 @1"></f><f eqn="prod @2 1 2"></f><f eqn="prod @3 21600 pixelWidth"></f><f eqn="prod @3 21600 pixelHeight"></f><f eqn="sum @0 0 1"></f><f eqn="prod @6 1 2"></f><f eqn="prod @7 21600 pixelWidth"></f><f eqn="sum @8 21600 0"></f><f eqn="prod @7 21600 pixelHeight"></f><f eqn="sum @10 21600 0"></f></formulas><path o:connecttype="rect" gradientshapeok="t" o:extrusionok="f"></path><lock aspectratio="t" v:ext="edit"></lock></shapetype><shape id="図_x0020_0" alt="image1.jpg" type="#_x0000_t75" o:spid="_x0000_i1025" style="VISIBILITY: visible; WIDTH: 252pt; HEIGHT: 311.25pt; mso-wrap-style: square"><imagedata o:title="image1" src="file:///C:UsersTakakiAppDataLocalTempmsohtmlclip11clip_image001.jpg"></imagedata></shape> 

 問題は、Aからスタートし、Pまで迷路を通って行くものである。16個のアルファベットは、全部通らなければならないが、アルファベット順に進む必要はない。同じところを2回以上通るのは禁止である。

 迷路は、アルファベットまたは分岐点で位置づけられる頂点と、頂点間をむすぶ辺とから構成される。スタートAとゴールPを除く各々の頂点は、2~4本の辺と接続するが、1回だけの通過点であるから、そのうちの2本の辺だけがルートとして有効であり、残りの辺は棄却されるべきものである。例えば、-A-B-C-のルートにAとCとを結ぶ辺が加わっていれば、A-C間の辺は捨てるべきであることは自明である。もしこの辺をルートにとるならば、頂点Bを通るルートは切断されてしまう。

上記の迷路パズルを解くに当たり、特に、頂点Hを通過するルートと、頂点GおよびJを通過するルートとに注目しよう。

 D-H-Lと通るルートは、頂点Iが切り離されるから、あり得ない。また、D-H-IまたはI-H-GH中間点を通るルートは、LまたはNが切り離されるから、あり得ない。さらに、D-H-GH中間点またはL-H-GH中間点を通るルートは、頂点Iが切り離されるから、あり得ない。そうすると、I-H-Lを通るルートだけが可能であることが分かる。このルートをHと呼ぶことにしよう。

 GおよびJを通過するルートは、F-J-Gを通るルートと、K-J-Gを通るルートとが可能である。前者をG、後者をGと呼ぶことにしよう。

 HとGの組合せは、Hを含むH-I-O-N-M-K-L-HのループとルートHとが分離してしまうため、全体として一筆書きのルートが構成できない。従って、残るは、HとGの組合せのみが可能であることが分かる。このようにして、HとGをつなげることにより、正解となるA-F-M-N-O-I-H-L-K-J-G-B-D-E-C-Pのルートが見えてくる。

 ところで、正解のルートは、複数の線分と点から構成され、点と点の間を線分で連結した鎖であることが知られる。そして、このような鎖は、トポロジーの世界では、単一の線分と同じものと考えられる。また、スタートの点とゴールの点とを重ねると、この鎖は単純な閉曲線となる。この単純閉曲線は、三角形と同じものと考えられる。

 トポロジーは、上記のような幾何的な図形を代数的な表現形式に変換する手段を提供する。この代数表現はホモロジー群と呼ばれる。このホモロジー群が難解である。トポロジーは、柔らかい幾何学と言われるが、構成要素がどのように連結して1つの物質を構成しているか不明のとき、このホモロジー群を用いて物質の構造を絞り込めるのだろうか。