「ハミルトン路」の版間の差分
削除された内容 追加された内容
編集の要約なし |
Meine Libe (会話 | 投稿記録) m Category:ウィリアム・ローワン・ハミルトンを追加 (HotCat使用) |
||
1行目:
'''ハミルトン路'''（ハミルトンろ、英: Hamilton trail）とは、[[グラフ理論|グラフ]]上の全ての頂点を 1 度ずつ通る[[路]]のこと。特に、グラフ上の全ての頂点を 1 度ずつ通る[[閉路]]は'''ハミルトン閉路'''という。また、ハミルトン閉路を含むグラフのことを'''ハミルトングラフ'''といい、ハミルトン路は含むがハミルトン閉路は含まないようなグラフのことを'''準ハミルトングラフ'''という。
与えられたグラフがハミルトン路を含むかどうか判定する問題は、[[NP完全問題]]。与えられたグラフがハミルトングラフかどうか判定する問題については、[[ハミルトン閉路問題]]を参照のこと。
==性質==
17行目:
* [[オイラー路]]
[[category:グラフ理論]]
[[Category:数学に関する記事|はみるとんろ]]▼
[[Category:ウィリアム・ローワン・ハミルトン]]
| |||