ハミルトン路
(Hamiltonian path から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/04/19 05:20 UTC 版)
|
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。（2022年11月）
|
ハミルトン路（ハミルトンろ、英語: Hamiltonian path）とは、グラフ上の全ての頂点を 1 度ずつ通る路のこと。特に、グラフ上の全ての頂点を 1 度ずつ通る閉路はハミルトン閉路という。また、ハミルトン閉路を含むグラフのことをハミルトングラフといい、ハミルトン路は含むがハミルトン閉路は含まないようなグラフのことを準ハミルトングラフという。
与えられたグラフがハミルトン路を含むかどうか判定する問題は、NP完全問題。与えられたグラフがハミルトングラフかどうか判定する問題については、ハミルトン閉路問題を参照のこと。
まだ、ハミルトングラフかどうかを判定する簡単な定理は見つかっていない。
性質
- |V(G)| ≥ 3、δ(G) ≥ |V(G)|/2 を満たす単純グラフ G は、ハミルトングラフ (Dirac, 1952年)
- グラフ G (|V(G)| ≥ 3) がハミルトングラフ ⇔ d(u) + d(v) ≥ V(G) を満たす隣接していない頂点 u, v について、G + (u, v) がハミルトングラフ
- グラフ G (|V(G)| ≥ 3) がハミルトングラフで、(u, v) ∈ E(G) かつ d(u) + d(v) ≥ n + 2 ならば、G - e もハミルトングラフ。
- 完全グラフ K2n+1 は、n 個のハミルトン閉路に分解できる。
- 完全グラフ K2n は、n-1 個のハミルトン閉路と 1 個の 1-正則な全域部分グラフに分解できる。
関連項目
- ハミルトン路のページへのリンク
