FindHamiltonianCycle

FindHamiltonianCycle[g]
求图 g 中的哈密顿圈.

FindHamiltonianCycle[g,k]
求至多 k 个哈密顿圈.

更多信息和选项更多信息和选项

背景
背景

  • FindHamiltonianCycle attempts to find one or more distinct Hamiltonian cycles, also called Hamiltonian circuits, Hamilton cycles, or Hamilton circuits. Cycles are returned as a list of edge lists or as if none exist. A Hamiltonian cycle (more properly called a Hamiltonian circuit when the cycle is identified using a explicit path with particular endpoints) is a consecutive sequence of distinct edges such that the first and last edges coincide at their endpoints and in which each vertex appears exactly once. A Hamiltonian cycle is therefore a graph cycle of length , where is the number of nodes in the graph. Hamiltonian cycles are used to reconstruct genome sequences, to solve some games (most obviously the Icosian game), to find a knight's tour on a chessboard, and to find attractive circular embeddings for regular graphs. A graph possessing a Hamiltonian cycle is known as a Hamiltonian graph.
  • FindHamiltonianCycle[g,k] attempts to find k Hamiltonian cycles, where the count specification k may be omitted (in which case it is taken as 1), may be a positive integer, or may be All.
  • Finding a Hamiltonian cycle is an NP-complete problem. However, various heuristic algorithms exist that sometimes (but not always) can find Hamiltonian cycles very quickly. For this reason, simply permuting the vertices in a graph may give a vastly different run time for FindHamiltonianCycle. A number of Method options may be specified to FindHamiltonianCycle, with the default being Automatic.
  • A graph may be tested to see if it is Hamiltonian using HamiltonianGraphQ. FindShortestTour is another function that attempts to find a single Hamiltonian cycle on a graph (or more generally specified set of vertices), with the advantage that it sometimes succeeds more quickly than FindHamiltonianCycle.
  • While Hamiltonian cycles in an -node graph correspond to cycles of length , a cycle of arbitrary length may be found using FindCycle. Hamiltonian cycles visit all vertices, but do not necessarily pass through each edge. A cycle that visits each edge exactly once is known as an Eulerian cycle and may be found using FindEulerianCycle.
2010年引入
(8.0)
| 2012年更新
(9.0)