ハミルトン路と閉路の解説

点を五つ輪に並べ、それぞれを両隣と結んでみてください。各点を一度ずつ通って一周し、元の場所へ帰れます。これがハミルトン閉路です。辺をいくつか足したり取り除いたりすると、問いは驚くほど難しくなります。グラフにそうした閉路があるかどうかは、どんなコンピューターもまだすべてのグラフについて速く答えられない、最もよく知られた問題の一つです。

平らに広げた正十二面体。20 個の角に子音字が記され、そのすべてを通るハミルトン閉路が明るい線で描かれ、探索が引き返した場所には赤い破線の辺がある
平らに広げた正十二面体。20 個の角に子音字が記され、そのすべてを通るハミルトン閉路が明るい線で描かれ、探索が引き返した場所には赤い破線の辺がある

すべての頂点を一度ずつ

グラフとは、頂点と呼ばれる点の集まりが、辺と呼ばれる線で結ばれたものです。ハミルトン路は辺をたどってすべての頂点をちょうど一度ずつ通り、ハミルトン閉路はさらに出発点へ戻るので、辺の数は頂点の数と同じになります。ハミルトン閉路を持つグラフはハミルトングラフと呼ばれます。示された経路を確かめるのは簡単で、頂点を数えて一歩ずつ見ればよいだけです。難しいのは一本見つけること、あるいは一本もないと示すことです。頂点をたどる順序の数は n! のように増え、20 頂点ですでに 2.4 × 10¹⁸ になるからです。

ハミルトンのイコシアンゲーム

四元数を発見したアイルランドの数学者ウィリアム・ローワン・ハミルトンは、1857 年にイコシアンゲームを考案しました。盤には平面に広げた正十二面体が描かれ、20 個の角には子音字が記されていて、主な課題は 1 から 20 までの番号のついたペグを、連続する数どうし、そして 20 と 1 が辺で結ばれるように角へ置くことでした。ハミルトンは権利を 25 ポンドでロンドンの玩具商 John Jaques and Son に売り、1859 年に発売されましたが、売れ行きは芳しくありませんでした。このパズルの解は、出発点と向きを問わず閉路を一度と数えて 30 通りです。問い自体は新しいものではなく、トマス・カークマンは 1855 年に王立協会へ送った論文で、どの多面体にすべての角を通る閉路があるかを問い、閉路を持たない例を一つ示していました。

ナイト巡回

ナイト巡回はチェスのナイトを動かして、すべてのマスにちょうど一度ずつ止まらせます。マスを頂点、ナイトの動きを辺とするグラフにおけるハミルトン路です。閉じた巡回は出発点からナイトの一手の距離で終わり、すなわちハミルトン閉路になります。チェスの指し手は千年以上前からこうした課題を出しており、オイラーは 1759 年の論文でこれを研究しました。1823 年に H・C・フォン・ワーンズドルフは、次の手が最も少ないマスへ常に進むことを提案しました。この単純な規則は、8 × 8 の盤の巡回をたいてい戻らずに完成させます。ナイトは常にマスの色を変えるので、閉じた巡回には明るいマスと暗いマスが同数必要であり、マスの数が奇数の盤は除かれます。アレン・シュウェンクは 1991 年に、どの長方形の盤に閉じた巡回があるかを正確に示しました。正方形の盤のうち、一辺が 6 以上の偶数のものにはすべてあります。ふつうのチェス盤には 13,267,364,410,532 通りの閉じた巡回があり、ブレンダン・マッケイが 1997 年に数え上げました。

ハミルトン閉路を持たないグラフ

閉路がないことの最も速い証明は数え上げの議論です。どの辺も異なる色を結ぶように頂点を二色で塗り分けられるなら、閉路は色を交互にたどるので各色の頂点が同数必要です。5 × 5 の格子は一方が 13 個、他方が 12 個なので、ハミルトン閉路はありません。取り除くとグラフが分かれてしまう切断点は二度通らねばならず、次数 1 の頂点はそもそも通り抜けられません。こうした議論をすべてすり抜けるグラフもあります。1898 年にユリウス・ピーターセンが発表したピーターセングラフは次数 3 の頂点を 10 個持ち、ハミルトン閉路はありませんが、どの頂点を一つ取り除いても残りにはハミルトン閉路があります。そうした性質を持つ最小のハイポハミルトングラフです。1862 年にイコシアンゲームについて書いたアレクサンダー・スチュアート・ハーシェルにちなむハーシェルグラフは、11 個の頂点と 18 本の辺を持ち、四角形の面が九つある多面体のグラフです。角の数がこれより少ない多面体で、ハミルトン閉路を欠くものはありません。1884 年にピーター・ガスリー・テイトは、各角に三本の辺が集まる多面体にはすべてハミルトン閉路があると予想しましたが、W・T・タットが 1946 年に 46 頂点の反例を見つけました。

存在を保証する条件

辺が多いグラフなら、ハミルトン閉路は確実にあります。ガブリエル・ディラックは 1952 年に、n ≥ 3 個の頂点を持ち、どの頂点の次数も n/2 以上のグラフにはハミルトン閉路があると証明し、エイスタイン・オーレは 1960 年に条件を弱めました。隣接しない二頂点の次数の和が常に n 以上であれば十分だというのです。どちらの条件も一方向にしか働きません。100 頂点の単純な輪はどこでも次数 2 で、50 にはるかに届きませんが、それ自体がハミルトン閉路です。全体の見取り図はこうです。十分条件があり、失敗する理由があり、その間には探索でなければ決着のつかないグラフの広い領域が横たわっています。

速い判定法が知られていない理由

グラフにハミルトン閉路があるかを決めるのは NP 完全で、リチャード・カープの 1972 年の 21 問の一つでした。すべてのグラフについてこれを速く解く方法があれば、他の何千もの問題も速く解け、P 対 NP の問いにも決着がつきます。すべての辺を一度ずつ使うオイラー路との対比は際立っています。オイラーは 1736 年に、奇数次数の頂点を数えればその問いは即座に決まると示しました。ハミルトン閉路に対する最良の厳密解法は、今も指数時間を要します。頂点のすべての部分集合にわたる動的計画法は、1962 年にリチャード・ベルマン、ならびにマイケル・ヘルドとリチャード・カープが見つけたもので、およそ n² × 2ⁿ 段階を要し、アンドレアス・ビョルクルンドの 2010 年の乱択法はおよそ 1.657ⁿ です。実際には、うまく枝刈りしたバックトラックが数十頂点のグラフを扱え、最短のハミルトン閉路を探す巡回セールスマン問題は、同じ問いに重みをつけた版です。

グレイコードと超立方体

0 から 7 までの数を 3 ビットの符号で書き、ちょうど 1 ビットだけ異なる符号どうしを結んでみてください。できあがるのは立方体のグラフです。その中のハミルトン閉路、たとえば 000, 001, 011, 010, 110, 111, 101, 100 は、八つの符号をどれも一つ前と 1 ビットだけ異なるように並べます。こうした並びがグレイコードで、ベル研究所のフランク・グレイにちなむ名です。彼は 1947 年に出願した特許でこれを記しました。どの超立方体にも一つあります。1 ビット短い符号を書き、続けて同じ並びを逆順に書き、前半に 0、後半に 1 を付ければよいのです。ロータリーエンコーダーがグレイコードを使うのは、二つの位置の中間で読み取っても誤差が 1 段階を超えないようにするためです。立方体のハミルトン閉路は 6 本、4 ビットの超立方体は 1,344 本です。

試してみる

ハミルトン路エクスプローラーを開いて、ハミルトンのパズルを自分で試してみてください。破線の輪が次に行ける先を示します。あるいは「探索」に切り替えてバックトラックの働きを眺めてください。路が伸び、赤い破線が引き返した場所を示し、棒グラフが路の長さごとのノード数を数えます。行き止まり検査、連結性検査、ワーンズドルフ順を切り替え、それぞれが必要とするノード数を比べ、小さなグラフの閉路をすべて数え、あるいは自分のグラフを描いて、どの簡易判定が当てはまるか見てみてください。

よくある質問

オイラー閉路を持つグラフはハミルトングラフでもありますか。逆はどうですか。

どちらも他方から導かれません。頂点を一つ共有する二つの三角形からなる蝶ネクタイは、すべての次数が偶数なのでオイラー閉路を持ちますが、共有する頂点を二度通らねばならないのでハミルトン閉路はありません。完全グラフ K₄ はハミルトン閉路を持ちますが、四つの頂点の次数がどれも 3 なので、オイラー閉路はありません。

コンピューターがすべての順序を試せばよいのでは。

小さなグラフに限ります。n 個の頂点の順序は n! 通りあり、20 個でおよそ 2.4 × 10¹⁸ です。バックトラックははるかに優れています。辺だけをたどり、行き詰まった時点で部分的な路を捨てるからです。20 頂点の正十二面体の 30 本の閉路をすべて、およそ 1,400 段階で見つけます。それでもグラフによっては部分的な路の数が指数的に増え、これをすべてのグラフで避ける方法は知られていません。

ハミルトン路の問題は閉路の問題より易しいのですか。

いいえ、どちらも NP 完全です。互いに変換できます。既存のすべての頂点と結んだ新しい頂点を一つ足すと、元のグラフにハミルトン路があることと、新しいグラフにハミルトン閉路があることはちょうど同値になります。逆向きには、ある頂点の複製(隣接点は同じ)を足し、元の頂点とその複製にそれぞれ新しい端の頂点をつければ、閉路の問題が路の問題になります。

5 × 5 の盤のナイト巡回が角の色から始まらなければならないのはなぜですか。

25 マスのうち 13 マスが角と同じ色、12 マスがもう一方の色で、ナイトは一手ごとに色を変えます。25 マスをたどる巡回は色が交互になるので、マスの多いほうの色で始まり終わります。アプリは 5 × 5 の盤の開いた巡回 1,728 通りをすべて見つけます。巡回とその逆順を一つと数えれば 864 通りで、どれも角の色のマスで始まり終わります。

試してみますか?

ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。

ハミルトン路エクスプローラーを開く