ハミルトン閉路問題とは？わかりやすく解説

ハミルトン閉路問題（Hamiltonian Cycle Problem）とは、与えられたグラフにおいて、すべての頂点を一度だけ通って出発点に戻る路（ハミルトン閉路）が存在するかどうかを判定する問題である ^[1] ^[2]。

名称は、1857年にこの問題を正十二面体上のパズル「ハミルトンの世界一周ゲーム(Icosian Game)」として考案した数学者ウィリアム・ローワン・ハミルトンに由来する^[2]。

概要

与えられたグラフが有向グラフの場合は有向ハミルトン閉路問題、無向グラフの場合は無向ハミルトン閉路問題と呼ばれる

ハミルトン閉路の「出発点に戻る（閉路である）」という条件を緩和し、全頂点を一度ずつ通る「路」の有無を問う問題は、ハミルトン路問題と呼ばれる。

また、無向ハミルトン閉路問題は、各辺に重み（距離）が付けられたグラフにおいて最小重量のハミルトン閉路を求める巡回セールスマン問題（TSP）の特殊ケース（すべての辺の重みが等しい場合）と見なすことができる。

計算複雑性

ハミルトン路・閉路問題は、有向グラフおよび無向グラフのいずれにおいてもNP完全問題であることが、1972年にリチャード・カープによって証明された ^[3]。

また、以下の特殊なグラフにおいても、NP完全性は維持される：

二部グラフ^[4]
最大次数が3の無向平面グラフ^[5]
入次数・出次数が共に2以下の有向平面グラフ^[6]
橋（グラフ理論）（英語版）のない無向平面3-正則二部グラフ
3-連結3-正則二部グラフ^[7]
格子グラフ（英語版）の部分グラフ^[8]
格子グラフの立方体部分グラフ^[9]

一方で、4-連結平面グラフや2-連結平面グラフなどについては、常にハミルトン閉路が存在することが証明されており、線形時間で解を求めるアルゴリズムが存在する^[10] 。

アルゴリズム

この問題に対する効率的な多項式時間アルゴリズムは見つかっていないが、いくつかの計算手法が提案されている。

力まかせ探索: すべての可能性を総当りで検証する方法。頂点数nの時、O(n!)であり、非常に低速である。
動的計画法: 頂点の集合 S と終点 v を状態として保持することで、 O(n² 2ⁿ) の時間計算量で解くことができる^[11]^[12]。
バックトラッキング: 探索木を構築し、ハミルトン路を形成できないことが判明した時点で枝刈りを行う。最大次数3のグラフに対しては O(1.251ⁿ) で解くことができる^[13]。

モンテカルロ法: Anders Björklund（英語版）によって提案された包除原理を利用したアプローチ。特定の行列式を計算することで、任意のn頂点グラフに対して O(1.657ⁿ) で、二部グラフに対してはO (1.415 ⁿ )で判定が可能である^[14]。
SATへの変換: NP完全性の性質を利用し、問題を3-SATなどの充足可能性問題に変換して、既存のSATソルバーで解くことができる。

応用例

Network-on-Chip(NoC)

コンピュータの主要な機能を単一のマイクロチップに統合したシステム・オン・チップ(SoC)内のデータ転送において、ハミルトン路に基づいたルーティングアルゴリズムが用いられる ^[15]。これにより、通信のデッドロックやライブロックを回避し、効率的マルチキャスト(多地点配送)が可能になる。

コンピュータグラフィックス

3Dレンダリングにおいて、三角形メッシュを効率的に処理するために利用される。連続する三角形が面を共有するように順序付ける「ストリップ化」は、メッシュの双対グラフにおいてハミルトン路を見つけることに相当する ^[16] 。

脚注

^ Sipser, Michael 田中圭介, 藤岡淳訳 (2023). 計算理論の基礎. 共立出版. ISBN 978-4-320-12561-2
^ ^a ^b 茨木俊秀『アルゴリズムの設計と解析』昭晃堂、1989年。 ISBN 4-7856-0119-1。
^ Karp, Richard (2009). “Reducibility among combinatorial problems” (英語). 50 Years of Integer Programming 1958-2008: from the Early Years to the State-of-the-Art.: 219-241.
^ “Proof that the existence of a Hamilton Path in a bipartite graph is NP-complete”. Computer Science Stack Exchange. 2019年3月18日閲覧。
^ Garey, M. R.; Johnson, D. S.; Stockmeyer, L. (1974), “Some simplified NP-complete problems”, Proc. 6th ACM Symposium on Theory of Computing (STOC '74), pp. 47–63, doi:10.1145/800119.803884 .
^ Plesńik, J. (1979), “The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two”, Information Processing Letters 8 (4): 199–201, doi:10.1016/0020-0190(79)90023-1 .
^ Akiyama, Takanori; Nishizeki, Takao; Saito, Nobuji (1980–1981), “NP-completeness of the Hamiltonian cycle problem for bipartite graphs”, Journal of Information Processing 3 (2): 73–76, MR 596313 .
^ Itai, Alon; Papadimitriou, Christos; Szwarcfiter, Jayme (1982), “Hamilton Paths in Grid Graphs”, SIAM Journal on Computing 4 (11): 676–686, doi:10.1137/0211056 .
^ Buro, Michael (2001), “Simple Amazons endgames and their connection to Hamilton circuits in cubic subgrid graphs”, Computers and Games, Lecture Notes in Computer Science, 2063, pp. 250–261, doi:10.1007/3-540-45579-5_17, ISBN 978-3-540-43080-3
^ Chiba, Norishige; Nishizeki, Takao (1989), “The Hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs”, Journal of Algorithms 10 (2): 187–211, doi:10.1016/0196-6774(89)90012-6
^ Bellman, Richard (January 1962). “Dynamic Programming Treatment of the Travelling Salesman Problem” (英語). Journal of the ACM 9 (1): 61–63. doi:10.1145/321105.321111. ISSN 0004-5411.
^ Held, Michael; Karp, Richard M. (March 1962). “A Dynamic Programming Approach to Sequencing Problems” (英語). Journal of the Society for Industrial and Applied Mathematics 10 (1): 196–210. doi:10.1137/0110015. ISSN 0368-4245.
^ Iwama, Kazuo; Nakashima, Takuya (2007), Lin, Guohui, ed., “An Improved Exact Algorithm for Cubic Graph TSP” (英語), Computing and Combinatorics, Lecture Notes in Computer Science (Berlin, Heidelberg: Springer Berlin Heidelberg) 4598: pp. 108–117, doi:10.1007/978-3-540-73545-8_13, ISBN 978-3-540-73544-1 2023年10月7日閲覧。
^ Bjorklund, Andreas (October 2010). “Determinant Sums for Undirected Hamiltonicity”. 2010 IEEE 51st Annual Symposium on Foundations of Computer Science. IEEE. pp. 173–182. arXiv:1008.0541. doi:10.1109/focs.2010.24. ISBN 978-1-4244-8525-3
^ Bahrebar, P.; Stroobandt, D. (2014). “Improving hamiltonian-based routing methods for on-chip networks: A turn model approach”. 2014 Design, Automation & Test in Europe Conference & Exhibition: 1–4.
^ Arkin, Esther M.; Mitchell, Joseph S. B.; Held, Martin; Skiena, Steven S.. “Hamiltonian Triangulations for Fast Rendering” ("PDF"). Department of Computer Science Stony Brook University.

表話編歴グラフ理論
要素・定義・表現	頂点辺（英語版）グラフ無向有向ラベル付き（英語版）重み付き（英語版）ハイパーグラフ接続行列隣接行列隣接リストラプラシアン行列
指標	位数（英語版）サイズ（英語版）次数次数行列距離（英語版）半径直径内周 (頂点)彩色数辺彩色数（英語版）点連結度辺連結度交叉数（英語版）
部分構造	ループ（英語版）多重辺（英語版）部分グラフ（英語版）誘導部分グラフ道閉道連結成分（英語版）強連結成分（英語版）橋（英語版）カットクリーク独立集合支配集合マッチングオイラー路シュタイナー木全域木ハミルトン路
全体構造	連結グラフ正則グラフ立方体グラフケージ強正則グラフ木平面グラフ 2部グラフ有向非巡回グラフ弦グラフムーアグラフパーフェクトグラフ対称グラフ半対称グラフ頂点推移グラフ辺推移グラフ距離推移グラフ補グラフ双対グラフグラフ同型
固有名を持つグラフ	パスグラフ（英語版） $P n$ 閉路グラフ $C n$ 完全グラフ $K n$ 完全2部グラフ $K m, n$ スター $S n = K 1, n$ 車輪グラフ $W n$ 空グラフピーターセングラフヒーウッドグラフマギーグラフホフマンシングルトングラフフォークマングラフ
トピック・定理	一筆書きオイラーの多面体定理クラトフスキの定理四色定理五色定理ケイリーの公式プリューファー列最短経路問題巡回セールスマン問題中国人郵便配達問題ダイクストラ法ベルマン-フォード法ワーシャル-フロイド法ハミルトン閉路問題最大クリーク問題頂点被覆問題最小頂点被覆問題最大独立集合問題最大流最小カット定理最大カット問題支配集合問題次数直径問題安定結婚問題
カテゴリ / コモンズ

ハミルトン閉路問題とは？わかりやすく解説