汉密尔顿图的问题：-
定义。汉密尔顿循环是一个包含图中所有顶点的循环。如果一个图有一个汉密尔顿循环，那么这个图就被称为汉密尔顿图。
哈密顿循环，也称为哈密顿循环、哈密顿循环或哈密顿回路，是指通过一个图的循环（即闭环），每个节点正好访问一次。一个拥有汉密尔顿循环的图被称为汉密尔顿图。
汉密尔顿循环问题是旅行推销员问题的一个特例，通过设置两个城市之间的距离，如果它们是相邻的，则为1，否则为2，并验证所走的总距离是否等于n（如果是，则该路线是一个汉密尔顿循环；如果没有汉密尔顿循环，则最短路线会更长）。
例子：-
1.png
解决方案。首先，我们从顶点'a'开始搜索。这个顶点'a'成为我们隐式树的根。
2.png
接下来，我们选择与'a'相邻的顶点'b'，因为它在词汇表中排在第一位（b、c、d）。
3.png
接下来，我们选择与'b'相邻的'c'。
4.png
接下来，我们选择与'c'相邻的'd'。
5.png
接下来，我们选择与'd'相邻的'e'。
6.png
接下来，我们选择与'e'相邻的顶点'f'。与'f'相邻的顶点是d和e，但它们已经访问过了。因此，我们得到了死胡同，我们回溯一步并从部分解决方案中删除顶点'f'。
7.png
通过回溯，与'e'相邻的顶点是b、c、d和f，其中顶点'f'已经被检查过了，b、c、d已经访问过了。因此，我们再次回溯一步。现在，与d相邻的顶点是e和f，e已经被检查过了，与'f'相邻的是d和e。所以我们再次回溯一步。
8.png
现在，与c相邻的是'e'，与e相邻的是'f'，与f相邻的是'd'，与d相邻的是'a'。在这里，我们得到了汉密尔顿循环，因为除了起始顶点'a'之外，所有的顶点都只被访问了一次。(a - b - c - e - f - d - a)。
9.png
再次回溯
10.png
这里我们产生了一个哈密顿循环，但通过考虑另一个顶点也可以得到另一个哈密顿循环。
参考资料：-
geeksforgeeks.com
维基百科
Mathword.worlfram.com
无向图中的汉密尔顿路径是一条对每个顶点都精确访问一次的路径。哈密顿循环（或哈密顿回路）是一条哈密顿路径，在图中有一条边（从最后一个顶点到哈密顿路径的第一个顶点）。判断一个给定的图形是否包含哈密尔顿循环。如果包含，则打印出该路径。以下是所需函数的输入和输出。
输入。
一个二维数组graph[V][V]，其中V是图中顶点的数量，graph[V][V]是图的邻接矩阵表示。如果有一条从i到j的直接边，graph[i][j]的值就是1，否则graph[i][j]就是0。
输出。
一个数组path[V]，它应该包含哈密尔顿路径。path[i]应该代表哈密尔顿路径中的第i个顶点。如果图中没有汉密尔顿循环，代码还应该返回false。
例如，以下图形中的汉密尔顿循环是{0, 1, 2, 4, 3, 0}。
(0)--(1)--(2)
| / \ |
| / \ |
| / \ |
(3)-------(4)
而下面的图形不包含任何哈密尔顿循环。
(0)--(1)--(2)
| / \ |
| / \ |
| / \ |
(3) (4)
建议。请先在 "PRACTICE "上解决这个问题，然后再继续解决。
天真算法
生成所有可能的顶点配置，并打印一个满足给定约束条件的配置。将会有n个！（n个因子）的配置。
当有未尝试的冲突时
{
产生下一个配置
如果（这个配置的两个连续顶点之间有边
配置的两个连续顶点之间有边，并且有一条边从最后一个顶点到
的边）。
{
打印此配置。
破解。
}
}
回溯算法
创建一个空的路径数组，将顶点0添加到其中。添加其他顶点，从顶点1开始。在添加一个顶点之前，检查该顶点是否与之前添加的顶点相邻，是否已经添加。如果我们找到这样的顶点，我们就把这个顶点作为解决方案的一部分加入。如果我们没有找到顶点，我们就返回false。
逆向追踪解决方案的实现
以下是回溯解决方法的实现。
# Python program for solution of
# hamiltonian cycle problem
class Graph():
def __init__(self, vertices):
self.graph = [[0 for column in range(vertices)]
for row in range(vertices)]
self.V = vertices
''' Check if this vertex is an adjacent vertex
of the previously added vertex and is not
included in the path earlier '''
def isSafe(self, v, pos, path):
# Check if current vertex and last vertex
# in path are adjacent
if self.graph[ path[pos-1] ][v] == 0:
return False
# Check if current vertex not already in path
for vertex in path:
if vertex == v:
return False
return True
# A recursive utility function to solve
# hamiltonian cycle problem
def hamCycleUtil(self, path, pos):
# base case: if all vertices are
# included in the path
if pos == self.V:
# Last vertex must be adjacent to the
# first vertex in path to make a cycle
if self.graph[ path[pos-1] ][ path[0] ] == 1:
return True
else:
return False
# Try different vertices as a next candidate
# in Hamiltonian Cycle. We don't try for 0 as
# we included 0 as starting point in hamCycle()
for v in range(1,self.V):
if self.isSafe(v, pos, path) == True:
path[pos] = v
if self.hamCycleUtil(path, pos+1) == True:
return True
# Remove current vertex if it doesn't
# lead to a solution
path[pos] = -1
return False
def hamCycle(self):
path = [-1] * self.V
''' Let us put vertex 0 as the first vertex
in the path. If there is a Hamiltonian Cycle,
then the path can be started from any point
of the cycle as the graph is undirected '''
path[0] = 0
if self.hamCycleUtil(path,1) == False:
print ("Solution does not exist\n")
return False
self.printSolution(path)
return True
def printSolution(self, path):
print ("Solution Exists: Following",
"is one Hamiltonian Cycle")
for vertex in path:
print (vertex, end = " ")
print (path[0], "\n")
# Driver Code
''' Let us create the following graph
(0)--(1)--(2)
| / \ |
| / \ |
| / \ |
(3)-------(4) '''
g1 = Graph(5)
g1.graph = [ [0, 1, 0, 1, 0], [1, 0, 1, 1, 1],
[0, 1, 0, 0, 1,],[1, 1, 0, 0, 1],
[0, 1, 1, 1, 0], ]
# Print the solution
g1.hamCycle();
''' Let us create the following graph
(0)--(1)--(2)
| / \ |
| / \ |
| / \ |
(3) (4) '''
g2 = Graph(5)
g2.graph = [
[0, 1, 0, 1, 0],
[1, 0, 1, 1, 1],
[0, 1, 0, 0, 1],
[1, 1, 0, 0, 0],
[0, 1, 1, 0, 0],
]
# Print the solution
g2.hamCycle();
# This code is contributed by Divyanshu Mehta
网友评论