点と線の旅: 一筆書き、地図、迷路、近道

正十二面体をひと回りする遊び、4色で塗り分ける地図、迷路の抜け方、いちばん近い道、そして回る順番。点と線で考えると、ばらばらに見える問題がつながります。

駅と線路、島と橋、町と道。丸い点を線でつなぐと、いろいろな問題が同じ形になります。点を「頂点」、線を「辺」、点と線の図を「グラフ」と呼びます。ここの5つの作品は、このグラフの上で遊びます。

正十二面体をひと回り（このサイトの「イコシアン・ツアー」）

正十二面体（五角形12枚でできた立体）の辺だけを通って、20個の頂点をぜんぶ1回ずつ通り、元の頂点に戻ります。これが「ハミルトン閉路」です。アイルランドの数学者ハミルトンは、このゲームを1857年にダブリンでの学会で示し、のちにロンドンの玩具会社に権利を渡した、とされています。発売は1859年ごろだそうです。同じころ、イギリスのカークマンも同じような道を調べていました。ハミルトンが最初に研究した、とは言えませんが、道の名前には彼の名前が残っています。

プログラムで、図形が20頂点・30辺で、どの頂点にも辺が3本あること、20辺の1周の道が見つかることを確かめました（icosian-tour/engine.test.ts）。また、作品に入っている「少し変えた図形」には、道がまったくないことも、総当たりで確かめました。道がない、と言い切るには、全部を調べるか、理由を見つける必要があります。

4色で塗り分ける地図（このサイトの「4色の地図」）

となりあう国に別の色を塗るとき、何色あれば足りるでしょうか。1852年、イギリスのフランシス・ガスリーが、郡の地図を塗っていて「4色で足りそうだ」と気づいた、とされています。 1879年に証明が発表されましたが、1890年に誤りが見つかりました。結局、証明が出たのは1976年で、アペルとハーケンが、コンピューターで何千もの場合を調べる形でした。2005年には、証明ソフトを使って、その検証が機械でも確かめられました。人間が全部は読み切れない証明をどう受け入れるか、という議論も生まれました。

作品の中央に島がある地図は、プログラムで「4色が必要で、3色では不可能」と確かめました。「6つの国の地図を2色で塗る」例もあります（four-color-map/engine.test.ts）。作品の地図は、このサイトのために作った架空の地図です。となりあう国は、辺が長さのある線でふれあっているものだけで、角で接するだけの国は、となりに数えません。

迷路を抜ける（このサイトの「迷路探検」）

迷路を解く古典的な方法に、片方の手を壁につけたまま歩く「右手法」があります。ただし、これがうまくいくのは、壁がすべて外周とつながっていて、輪がない迷路だけです。ゴールが島の周りにあると、島の周りをぐるぐる回るだけになります。もう一つ、通った道に印をつけて探索する方法があります。19世紀のフランスの人トレモーの名で呼ばれ、現在の深さ優先探索と同じ考えです。これは通路がはっきりした迷路ならどれでも解けますが、最短とは限りません。

この作品の迷路は、プログラムで200通りの種を試し、すべてが「つながっていて、輪がない」迷路になることを確かめました。輪がないので、右手法は必ず出口に着きます。そのうえで、乗り換えを幅優先で探す道は、右手法で歩く道より長くなることはありません。この迷路では出口までの道がただ1つなので、最短の道も1つだけです（maze-explorer/engine.test.ts）。

いちばん近い道（このサイトの「最短経路」）

道ごとに時間（費用）が違うとき、最小の合計になる道を探すのが、ダイクストラ法です。出発点から近い順に、道を確定していきます。ダイクストラは1956年にアムステルダムでこの問題を考え、1959年に発表しました。本人は後年、買い物の途中のカフェで、約20分で思いついたと語っています（本人の回想です）。

プログラムで、ダイクストラ法の答えが、すべての出発点から全部の道を数え上げた結果と一致することを確かめました。作品の2つの道路網では、最短の費用が6と5です。また、乗り換えの回数がいちばん少ない道（幅優先）は、最初の道路網では費用11になり、最短より高くなります。「少ない手数」と「少ない費用」は別のものです（shortest-path/engine.test.ts）。

回る順番（このサイトの「巡回ルート」）

いくつかの町を1回ずつ回って戻るとき、どの順番がいちばん短いでしょうか。「巡回セールスマン問題」です。 19世紀のハミルトンらにさかのぼる問題で、語としては、1949年のジュリア・ロビンソンの報告が最初の使用とされています。1954年に49都市の最短が、1970年代以降はもっと多くの都市で、そして2006年には85,900都市の例が解かれました。 1972年、カープが関連する問題がNP完全だと示し、この問題は「NP困難」だとわかりました。これは「全然解けない」という意味ではなく、都市が増えたとき、全部を調べる方法は現実的でなくなる、ということです。

作品の8地点では、順番は 7! ＝ 5040 通りです。プログラムで全部を調べた最短が、別に書いた総当たりと一致することを確かめました。いちばん近い町へ進む方法（最近隣法）は、最初の地図では最短より1以上長くなります。そこから、交差する2本を入れ替えて短くする方法（2-opt）で、順番にいい道に近づけます（tsp-route/engine.test.ts）。

共通すること

点と線に直す：問題の飾りを取ると、同じ形が見えてきます。
「ある」と「ない」：道がある、4色で足りる、は見つければ示せます。ない、は全部を調べるか、理由が要ります。
近道は一つではない：最短の時間、少ない乗り換え、見つけやすさは、別々のものさしです。

作品の地図、迷路、道路網は、どれもこのサイトのために作ったものです。