Euler's Eyes
2026-10-27
イコシアン・ゲームとハミルトン閉路
1856 年、まだ非可換な代数に取り組んでいたハミルトンは、イコシアン算法を発明した。三つの記号 $\iota$、$\kappa$、$\lambda$ が次の規則に従う。
$$\iota^2 = 1, \qquad \kappa^3 = 1, \qquad \lambda^5 = 1, \qquad \lambda = \iota\kappa.$$今日の言い方では、これらは二十の三角形の面をもつ正二十面体の回転群を生成する。ハミルトンは 1857 年にダブリンで開かれた英国科学振興協会の会合でこの算法を発表し、それが正十二面体、つまり十二の五角形の面と二十の頂点をもつ立体の辺に沿った道筋を表すことに気づいた。
パズル
このアイデアを広めるため、ハミルトンは十二面体を平たく押しつぶして盤の上に描き、二十の頂点に穴をあけて、それぞれに都市の名をつけ、番号のついた二十本のピンを添えた。課題は、ある都市から出発し、辺だけをたどって、ほかのすべての都市をちょうど一度ずつ訪れ、出発点に戻ることである。1859 年、彼はロンドンのゲーム製造業者ジョン・ジャックス社に権利を 25 ポンドで売った。ゲームは『イコシアン・ゲーム』として、また『旅人の十二面体』という携帯版として売られたが、商業的には失敗だった。少し根気があれば、基本の課題は数分で解けてしまうのだ。
やってみよう。文字は、ハミルトンが都市の名に使った子音である。
オイラーは解き、ハミルトンは解けない
すべての頂点をちょうど一度ずつ通って出発点に戻る道筋は、今日ハミルトン閉路と呼ばれる。この問いは、オイラーがすべての辺をちょうど一度ずつ渡ろうとしたケーニヒスベルクの橋のいとこのように見える。だが二つはまったく違う。辺については、オイラーが 1736 年に簡単な判定法を与えた。各頂点から何本の辺が出ているかを見ればよい。頂点については、簡単な判定法を誰も知らない。1972 年、リチャード・カープはハミルトン閉路問題を NP 完全問題のリストに入れた。これを速く解く方法を見つけた者は、何千もの難問を速く解く方法を手にし、クレイ研究所から百万ドルを得ることになる。
そのいちばん有名な親戚が巡回セールスマン問題である。ある地図のすべてのハミルトン閉路のうち、どれが最も短いか。配達経路、回路基板の穴あけ、DNA の配列決定などに現れる。
練習：辺を数える
正十二面体では、20 個の頂点のそれぞれが 3 本の辺に接している。辺は何本あるか。また、ハミルトン閉路はそのうち何本を使うか。
頂点ごとに数えると $20 \times 3 = 60$ 個の辺の端があり、一本の辺には端が二つあるので、$60 / 2 = 30$ 本である。ハミルトン閉路は 20 個の頂点を通って戻るので 20 本の辺を使い、残りの 10 本は使われない。
練習：立方体の閉路
立方体の頂点は、$000$ から $111$ までの三桁のビット列として書け、一桁だけ違うものどうしが辺で結ばれる。ハミルトン閉路を一つ見つけよ。
一つの解は $000 \to 001 \to 011 \to 010 \to 110 \to 111 \to 101 \to 100 \to 000$ である。各段階で一つのビットだけが変わる。この列は三桁のグレイ符号であり、各段階で一桁しか変わらないからこそ、位置センサーや誤り訂正で使われている。
出典： William Rowan Hamilton, “Memorandum respecting a new System of Roots of Unity”, Philosophical Magazine（1856）· Norman L. Biggs、E. Keith Lloyd、Robin J. Wilson, Graph Theory 1736–1936（1976）· Richard M. Karp, “Reducibility among combinatorial problems”（1972）· マテマテカ（サンパウロ大学）のイコシアン・ゲーム。
ウィリアム・ローワン・ハミルトンの全トピック · ← ケイリー＝ハミルトンの定理 · ウィリアム・ローワン・ハミルトンの遺産 →