ハミルトン路チェッカー

ハミルトン路チェッカー

ハミルトン路チェッカーは、グラフがハミルトン路（すべての頂点をちょうど1回ずつ訪れるシーケンス）またはハミルトン閉路（ハミルトン路に加えて、開始頂点に戻るもの）を含んでいるかどうかを判定します。このツールは、高速な構造的事前チェック（連結性、次数の前提条件、ディラックの定理、オレの定理）と、ワーンスドルフのヒューリスティックによって調整されたバックトラッキング探索を組み合わせ、証拠パスをステップバイステップのアニメーションで可視化します。

ハミルトン路とは？

頂点数 n のグラフ G = (V, E) において、ハミルトン路とは、すべての頂点を含む順序付きシーケンス v₁, v₂, …, v_n であり、連続する各ペア (v_i, v_i+1) が G のエッジであり、すべての頂点がちょうど1回ずつ現れるものを指します。さらに (v_n, v₁) もエッジである場合、そのシーケンスはハミルトン閉路となります。

この問題は、1857年に正十二面体グラフのすべての頂点をちょうど1回ずつ訪れる閉路を見つけるパズル「イコシアン・ゲーム」を考案したウィリアム・ローワン・ハミルトンにちなんで名付けられました。

難しさの理由: NP完全性

ハミルトン路判定問題およびハミルトン閉路判定問題は、どちらもNP完全です (Karp, 1972)。P = NP でない限り、あらゆるインスタンスを多項式時間で解くアルゴリズムは存在しません。最悪の場合、バックトラッキングは閉路に対して最大 (n−1)! サイズの探索木を探索します。このため、この電卓は入力を20頂点までに制限しています。頂点数 n がわずかに増加するだけで、実行時間は爆発的に増加するためです。

実際には、ワーンスドルフのヒューリスティック（もともとは1823年にハインリヒ・ワーンスドルフが騎士の巡回問題のために考案したもの）を用いることで、構造化されたグラフ上での探索が劇的に高速化されます。各ステップで、アルゴリズムは未訪問の隣接頂点のうち、残りの未訪問隣接頂点数が最も少ない頂点へパスを延長します。この貪欲法的な規則により、探索が行き止まりに陥るのを防ぎ、素直なグラフではバックトラッキングなしでハミルトン巡回路を発見できることがよくあります。

必要条件 — 高速な棄却

コストの高い探索を実行する前に、電卓はハミルトン路を含む可能性がないグラフを棄却します：

• 連結性: ハミルトン路はすべての頂点を訪れる必要があるため、グラフはちょうど1つの連結成分を持つ必要があります。有向グラフの場合は、矢印の向きを無視した弱連結性が必要です。
• 次数（無向）: 次数が1の頂点は最大2つまでです（これらはパスの端点の候補となります）。ハミルトン閉路の場合、すべての頂点の次数は2以上でなければなりません。
• 次数（有向）: ハミルトン路の場合、入次数が0の頂点は最大1つ（始点）、出次数が0の頂点は最大1つ（終点）までです。ハミルトン閉路の場合、すべての頂点の入次数 ≥ 1 かつ 出次数 ≥ 1 である必要があります。

これらの規則により、絶望的な入力を線形時間で棄却し、無駄なバックトラッキングの労力を避けることができます。

十分条件 — 古典的定理

いくつかの古典的な定理は、単純無向グラフにハミルトン閉路が存在することを保証する十分（ただし必要ではない）条件を与えます。これらが適用される場合、電卓は探索を実行せずに（証拠となる閉路は提示しますが）結果を「保証あり」とマークします。

ディラックの定理 (1952年)

G が n ≥ 3 の単純無向グラフであり、すべての頂点の次数が n / 2 以上であれば、G はハミルトン閉路を持ちます。

オレの定理 (1960年)

隣接していないすべての頂点ペア u と v について deg(u) + deg(v) ≥ n が成り立つなら、G はハミルトン閉路を持ちます。オレの条件はディラックの条件よりも厳密に弱いため、オレの定理が成り立つときはディラックの定理も成り立ちます。

ディラックまたはオレの条件を満たさないからといって、グラフにハミルトン閉路がないわけではありません。どちらも満たさないが閉路を持つグラフは多く存在します（例：単純な n 角形の閉路は最小次数が2であり、大きな n に対して n/2 よりもはるかに小さくなります）。

内部の探索アルゴリズム

事前チェックで決着がつかない場合、電卓はグラフの隣接表現に対してバックトラッキング探索を実行します。主な手法：

1. ビットマスクによる訪問済みセット: 訪問した頂点をビットマスクとして保存します（最大20頂点まで、O(1) の高速な所属判定が可能）。
2. ワーンスドルフのヒューリスティック: 各延長において、残りの未訪問次数が少ない順に隣接頂点を試行し、「分岐の少ない」順序を模倣します。
3. ルート選択: ハミルトン閉路の場合、開始頂点は1つだけで十分です（閉路は回転不変であるため）。ハミルトン路の場合、出次数が少ない（希少な位置）順に開始頂点を試行します。
4. ステップ予算: ハードキャップにより、病的なインスタンスが無期限に実行されるのを防ぎます。予算を使い果たした場合、UI は「タイムアウト」と報告します。

ハミルトン vs オイラー

ハミルトン問題とオイラー問題は混同されやすいですが、根本的に異なります：

サポートされている入力形式

エッジリスト

1行に1つのエッジ、またはカンマ区切り。サポートされている区切り文字：A-B, A B, A,B, A--B, A->B, A<-B。有向グラフであることを強制するには -> を使用してください。

隣接行列

0/1値の正方行列。1行に1行分を入力し、スペースまたはカンマで区切ります。「行列ラベル」フィールドにオプションのラベルを入力できます。入力がない場合は、自動的に A, B, C… が使用されます。

このチェッカーの使い方

1. 入力形式を選択 — 手書きの小さなグラフには「エッジリスト」、コードや教科書からの貼り付けには「隣接行列」を選択します。
2. グラフを貼り付ける — テキストエリアにグラフを入力します。行列入力の場合は、任意で頂点ラベルを指定できます。
3. チェック対象を選択 — 路のみ、閉路のみ、または一度に両方をチェックするか選択します。
4. グラフの種類を選択 — 「自動検出」は、矢印のスタイル (->) や行列の対称性から有向性を推測します。
5. 「ハミルトン性をチェック」をクリック — 結果ページには、判定の見出し、必要条件の事前チェック、ディラック/オレの十分条件テスト、証拠パス（存在する場合）、およびインタラクティブな可視化が表示されます。
6. 証拠を再生 — 再生/ステップコントロールを使用して、グラフ上でエッジが1つずつ点灯する様子を確認します。

実行例 — ピーターセングラフ

有名なピーターセングラフ（10頂点、15エッジ、3-正則グラフ）は、ハミルトン路は持ちますがハミルトン閉路は持たないグラフの教科書的な例です。以下のエッジリストをフィールドに貼り付けてチェックをクリックしてください：

チェッカーは確認します：ハミルトン路は発見されます（例: 1 — 2 — 7 — 10 — 5 — 4 — 9 — 6 — 8 — 3）が、網羅的探索によりループを閉じる方法がないことが判明します。これは1890年代に最初に証明された結果です。

主な用途

• ルーティングと巡回セールスマン問題 (TSP) — すべての TSP 巡回路は、完全重み付きグラフにおけるハミルトン閉路です。
• ゲノムアセンブリ — 重複するリードから DNA シーケンスを再構築する作業は、オーバーラップグラフにおけるハミルトン路としてモデル化できます。
• 回路設計 — 配線長を最小限にするための PCB 上のピン配置。
• ゲーム AI とパズル解き — チェス盤上の騎士の巡回、イコシアン・ゲーム。
• スケジューリング — 各タスクが次のタスクへ実現可能な移行ができるように順序を決定する。
• 組合せ数学の教育 — 手作業で解ける小さな例を用いて NP完全性を説明する。

よくある質問

ハミルトン路とは何ですか？

ハミルトン路とは、グラフのすべての頂点をちょうど1回ずつ通る道のことです。1857年に正十二面体グラフ上の問題を研究したウィリアム・ローワン・ハミルトンにちなんで名付けられました。このような路が存在するかどうかの判定は NP完全問題であり、すべてのグラフに対して多項式時間で解く既知のアルゴリズムは存在しません。

ハミルトン閉路とハミルトン路の違いは何ですか？

ハミルトン閉路は、開始頂点に戻るハミルトン路のことで、すべての頂点をちょうど1回ずつ訪れる閉じたループを形成します。すべてのハミルトン閉路にはハミルトン路が含まれますが（終点のエッジを除去すればよいため）、その逆は真ではありません。多くのグラフはハミルトン路を持ちますが、ハミルトン閉路は持ちません。

ディラックの定理とは何ですか？

ディラックの定理（1952年）は、nが3以上の頂点を持つ単純無向グラフにおいて、すべての頂点の次数が n/2 以上であれば、そのグラフはハミルトン閉路を持つというものです。これは十分条件ですが必要条件ではありません。ディラックの閾値を満たさない多くのグラフも、ハミルトン閉路を持つことがあります。

オレの定理とは何ですか？

オレの定理（1960年）は、nが3以上の頂点を持つ単純グラフにおいて、隣接していないすべての頂点のペア u と v について、その次数の和が n 以上であれば、そのグラフはハミルトン閉路を持つというものです。オレの条件はディラックの条件よりも弱いため、オレの定理が適用される場合は常にオレの定理も適用されます。

なぜ探索は20頂点に制限されているのですか？

ハミルトン路および閉路の判定問題は NP完全です。最悪の場合の実行時間は頂点数に対して指数関数的に増加します。プルーニングとワーンスドルフのヒューリスティックにより、この電卓は20頂点までの多くの小規模グラフを迅速に処理できますが、より困難なケースではタイムアウトする可能性があります。20頂点を超える場合は、Concordeや整数計画法などの専門的なソルバーを使用する必要があります。

ワーンスドルフのヒューリスティックとは何ですか？

1823年に騎士の巡回問題のために提案されたワーンスドルフの規則は、各ステップで、まだ訪問していない隣接頂点のうち、未訪問の隣接頂点が最も少ない頂点に移動すべきであるというものです。この貪欲法的な規則は、実際にはバックトラッキングの探索木を劇的に剪定し、正則グラフなどではバックトラッキングなしでハミルトン路を見つけることもよくあります。

このツールはすべてのハミルトン路を見つけますか？

いいえ — 存在する場合に、証拠となる1つの路または閉路を見つけます。ハミルトン路の総数を数えることは、それ自体が #P完全問題であり、判定問題よりもはるかに困難です。列挙が必要な場合は、専用のツールや整数計画ソルバーが適しています。

参考文献

• ハミルトン路 — Wikipedia
• ハミルトン路問題 — Wikipedia
• Dirac's theorem on Hamiltonian cycles — Wikipedia (英語)
• オレの定理 — Wikipedia
• ワーンスドルフの規則 — Wikipedia

その他の関連ツール:

高度な数学操作:

• antilog電卓
• ベータ関数電卓
• 二項係数電卓
• 二項確率分布電卓
• ビットに基づいての電卓
• 中心極限定理電卓
• 組み合わせ電卓
• 相補誤差関数電卓
• 複素数電卓
• エントロピー電卓
• エラー関数電卓
• 指数減衰電卓-高精度
• 指数成長電卓 高精度
• 指数積分電卓
• 指数電卓-高精度 おすすめ
• 階乗電卓 おすすめ
• ガンマ関数電卓
• 黄金比電卓
• 半減期電卓 おすすめ
• パーセント成長率電卓
• 順列電卓
• ポアソン分布電卓
• 多項式の根電卓と詳細なステップ
• 確率電卓
• 確率分布電卓 おすすめ
• 比率電卓
• 二次式電卓
• 関数電卓 おすすめ
• 科学表記法電卓
• 有効数字電卓 新しい
• 立方和電卓
• 正の整数の電卓
• 平方和の計算 おすすめ
• 真理値表ジェネレーター
• 集合論電卓
• ベン図ジェネレーター3集合
• 中国剰余定理電卓 おすすめ
• オイラーのトーシェント関数電卓
• 拡張ユークリッドアルゴリズム電卓
• モジュラー乗法逆数電卓
• 連分数電卓 おすすめ
• ダイクストラ最短経路電卓
• 最小全域木電卓
• グラフ次数列バリデーター
• 完全順列 サブファクトリアル電卓
• スターリング数電卓
• 鳩の巣原理電卓
• マルコフ連鎖定常分布電卓
• 四捨五入電卓 新しい
• 負の二項分布電卓 新しい
• 重複順列電卓 新しい
• モジュラー冪乗計算機 新しい
• 原始根電卓
• ブール代数簡略化ツール 新しい
• カルノー図 (K-Map) ソルバー 新しい
• グラフ彩色電卓 新しい
• トポロジカルソート電卓 新しい
• 隣接行列電卓 新しい
• 包除原理電卓 新しい
• 線形計画法ソルバー 新しい
• 巡回セールスマン問題ソルバー TSP 新しい
• ハミルトン路チェッカー 新しい
• 平面グラフ判定 新しい
• ネットワークフロー電卓最大フロー 新しい
• 安定結婚問題ソルバー 新しい
• 群論の位数電卓 新しい
• 環と体の電卓 新しい