哈密顿环

哈密​​顿环 (Hamiltonian Cycle)

A Hamiltonian graph is the directed or undirected graph containing a Hamiltonian cycle. The Hamiltonian cycle is the cycle that traverses all the vertices of the given graph G exactly once and then ends at the starting vertex.

哈密​​顿图是包含哈密顿循环的有向图或无向图。 哈密​​顿循环是这样的循环：该循环精确地遍历给定图G的所有顶点一次，然后在起始顶点处结束。

The input for the Hamiltonian graph problem can be the directed or undirected graph. The Hamiltonian problem involves checking if the Hamiltonian cycle is present in a graph G or not. The following graph illustrates the presence of the Hamiltonian cycle in a graph G.

哈密​​顿图问题的输入可以是有向图或无向图。 哈密​​顿问题涉及检查图G中是否存在哈密顿循环。 下图说明了图G中哈密​​顿环的存在。

While generating the state space tree following bounding functions are to be considered, which are as follows:

在生成状态空间树时，要考虑以下边界函数：

1. The i^th vertex in the path must be adjacent to the (i-1)^th vertex in any path.

   路径中的第i ^个顶点必须与任何路径中的^第 (i-1) ^个顶点相邻。

2. The starting vertex and the (n-1)^th vertex should be adjacent.

   起始顶点和第(n-1) ^个顶点应该相邻。

3. The ith vertex cannot be one of the first (i-1)^th vertex in the path.

   第i个顶点不能是路径中^第一个(i-1) ^个顶点之一。

Algorithm:

算法：

Algorithm Hamiltonian (k)    1.	{    2.	Repeat    3.	{    4.	Next value (k);    5.	If (x[k] == 0) then return;    6.	If ( x[k] == n) then write x[1:n];    7.	Else Hamiltonian (k+1)    8.	}    9.	Until (false);    Algorithm Next value (k)    1.	{    2.	Repeat    3.	{    4.	X [k] = (x[k] + 1 mod (n+1));    5.	If (x[k] == 0) then return;    6.	If (G (x[k-1]), x[k] =! 0) then    7.	{    8.	For j=1 to k-1    9.	Do if ( x[ j ] == x[ k ]) then break;    10.	If ( j == k) true    11.	If ( k

This algorithm uses the recursive formulated of backtracking to find all the Hamiltonian cycles of a graph. The graph is stored as an adjacency matrix G [1: n, 1: n].

该算法使用回溯的递归公式来查找图的所有哈密顿环。 该图被存储为邻接矩阵G [1：n，1：n] 。

In the next value k, x [1: k-1] is a path with k-1 distinct vertices. if x[k] == 0 then no vertex has to be yet been assign to x[k]. After execution x[k] is assigned to the next highest numbered vertex which does not already appear in the path x [1: k-1] and is connected by an edge to x [k – 1] otherwise x[k] == 0.

在下一个值k中，x [1：k-1]是具有k-1个不同顶点的路径。 如果x [k] == 0，则无需将顶点分配给x [k] 。 执行后， x [k]被分配给下一个编号最高的顶点，该顶点尚未出现在路径x [1：k-1]中，并且通过边连接到x [k – 1]，否则x [k] == 0 。

If k == n, (here n is the number of vertices) then in addition x[n] is connected to x [1].

如果k == n ，(这里n是顶点的数目)，则x [n]另外连接到x [1] 。

翻译自:

哈密顿环