Hamiltonian Cycle

释义 Definition

哈密顿回路（哈密顿环）：图论中的一种环路，指在一个图中存在一条闭合路径，恰好经过每个顶点一次并回到起点。（常见于组合数学与算法/复杂性理论；相关判定问题是经典难题。）

发音 Pronunciation (IPA)

/həˈmɪl.tə.ni.ən ˈsaɪ.kəl/

例句 Examples

A Hamiltonian cycle visits every vertex exactly once and returns to the start.
哈密顿回路会恰好访问每个顶点一次，并返回起点。

In many graphs, finding a Hamiltonian cycle is difficult, and the decision version is NP-complete.
在许多图中，寻找哈密顿回路很困难，而且其判定版本是 NP-完全的。

词源 Etymology

“Hamiltonian” 源自爱尔兰数学家 William Rowan Hamilton（威廉·罗文·哈密顿） 的姓氏；该术语用来纪念他与相关路径/循环思想的影响。与之对应的概念还有 Hamiltonian path（哈密顿路径）。

相关词 Related Words

• Hamiltonian Path
• Graph
• Vertex
• Edge
• Cycle
• Eulerian Cycle
• NP-Complete
• Traveling Salesman Problem

文学与经典著作中的出现 Literary Works

• Douglas B. West, Introduction to Graph Theory（《图论导论》）
• Reinhard Diestel, Graph Theory（《图论》）
• Michael R. Garey & David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness（《计算机与难解性》；讨论哈密顿回路问题的 NP-完全性）
• Christos H. Papadimitriou, Computational Complexity（《计算复杂性》；以哈密顿回路作为经典复杂性例题）