ハミルトン路のソースを表示

'''ハミルトン路'''とは、[[グラフ理論|グラフ]]上の全ての頂点を 1 度ずつ通る[[路]]のこと。特に、グラフ上の全ての頂点を 1 度ずつ通る[[閉路]]は'''ハミルトン閉路'''という。また、ハミルトン閉路を含むグラフのことを'''ハミルトングラフ'''といい、ハミルトン路は含むがハミルトン閉路は含まないようなグラフのことを'''準ハミルトングラフ'''という。

与えられたグラフがハミルトン路を含むかどうか判定する問題は、[[NP完全]]。与えられたグラフがハミルトングラフかどうか判定する問題については、[[ハミルトン閉路問題]]を参照のこと。

==性質==
* |''V''(''G'')| &ge; 3、δ(''G'') &ge; |''V''(''G'')|/2 を満たす単純グラフ ''G'' は、ハミルトングラフ (Dirac, 1952年)
* グラフ ''G'' (|''V''(''G'')| &ge; 3) がハミルトングラフ &hArr; ''d''(''u'') + ''d''(''v'') &ge; ''V''(''G'') を満たす隣接していない頂点 ''u'', ''v'' について、''G'' + (''u'', ''v'') がハミルトングラフ
* グラフ ''G'' (|''V''(''G'')| &ge; 3) がハミルトングラフで、(''u'', ''v'') &isin; ''E''(''G'') かつ ''d''(''u'') + ''d''(''v'') &ge; ''n'' + 2 ならば、''G'' - ''e'' もハミルトングラフ。
* 完全グラフ ''K''<sub>2''n''+1</sub> は、''n'' 個のハミルトン閉路に分解できる。
* 完全グラフ ''K''<sub>2''n''</sub> は、''n''-1 個のハミルトン閉路と 1 個の 1-[[正則グラフ|正則]]な全域部分グラフに分解できる。

== 関連項目 ==
* [[閉路グラフ]]

[[category:グラフ理論|はみるとんろ]]
[[Category:数学に関する記事|はみるとんろ]]