哈密顿路径维基百科,自由的 encyclopedia 在图论中,哈密顿路径(中国大陆作哈密顿路径,台湾作汉米顿路径)是在无向图或有向图中,恰好能将图中所有顶点各拜访一次的路径。与之相近的概念为哈密顿环(中国大陆作哈密顿环,台湾作汉米顿环),即该路径在拜访完图中所有顶点后会回到出发点,而构成一个环。要确定图中是否存在哈密顿路径或哈密顿环的问题称为哈密顿路径问题[1],这个问题是一个NP完全的问题。哈密顿路径有时会跟尤拉路径一起讨论,因为哈密顿路径要求通过所有顶点(哈密顿路径问题)而尤拉路径要求通过所有边(一笔画问题)。[2]:218[3] 经过图中所有顶点的回路称为哈密顿环 8x8网格图上的三个例子
在图论中,哈密顿路径(中国大陆作哈密顿路径,台湾作汉米顿路径)是在无向图或有向图中,恰好能将图中所有顶点各拜访一次的路径。与之相近的概念为哈密顿环(中国大陆作哈密顿环,台湾作汉米顿环),即该路径在拜访完图中所有顶点后会回到出发点,而构成一个环。要确定图中是否存在哈密顿路径或哈密顿环的问题称为哈密顿路径问题[1],这个问题是一个NP完全的问题。哈密顿路径有时会跟尤拉路径一起讨论,因为哈密顿路径要求通过所有顶点(哈密顿路径问题)而尤拉路径要求通过所有边(一笔画问题)。[2]:218[3] 经过图中所有顶点的回路称为哈密顿环 8x8网格图上的三个例子