哈密顿回路（怎么判断有没有哈密顿回路）
温馨提示：这篇文章已超过35天没有更新，请注意相关的内容是否还可用！
今天给各位分享哈密顿回路的知识，其中也会对怎么判断有没有哈密顿回路进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，如果有不同的见解与看法，请积极在评论区留言，现在开始进入正题！
本文目录一览：
n阶完全图中有多少条哈密顿回路
n阶完全图中哈密顿回路的条数为：（n-1)!/2
选定一个点，从这点开始到每个点的走法，只要有三个点以上就是圈，因此只管走的方法，选定构成一个圈的点算了两次，所以要除以2。
若一个图的每一对不同顶点恰有一条边相连，则称为完全图。完全图是每对顶点之间都恰连有一条边的简单图。n个端点的完全图有n个端点及n(n
−
1)
/
2条边，以Kn表示。它是(k
−
1)-正则图。所有完全图都是它本身的团（clique）。
哈密顿回路的算法
哈密顿路径问题在上世纪七十年代初，终于被证明是“NP完备”的。据说具有这样性质的问题，难于找到一个有效的算法。实际上对于某些顶点数不到100的网络，利用现有最好的算法和计算机也需要比较荒唐的时间（比如几百年）才能确定其是否存在一条这样的路径。
从图中的任意一点出发，路途中经过图中每一个结点当且仅当一次，则成为哈密顿回路。
要满足两个条件：
⒈封闭的环
⒉是一个连通图，且图中任意两点可达
经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为哈密顿通路。
经过图中所有顶点一次且仅一次的回路称为哈密顿回路。
具有哈密顿回路的图称为哈密顿图，具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图。
平凡图是哈密顿图。
⒊若以1到2、2到3、3到4、4到5、5到1，为计数规律，则各点均出现两次；这种判断方法在计算机编程运算中显得尤为重要，其会精简很多运算过程。
⒋新出炉，有待检测的代码如下：
%-------输入的数据的原数据参照
% v1 v2 v3 v4 v5
%v1 0 20 1 11 2
%v2 0 0 9 1 3
%v3 0 0 0 13 8
%v4 0 0 0 0 6
%v5 0 0 0 0 0
%以上为输入数据的原数据参照
%建议所计算的数据矩阵长度为5，不会产生bug，且不会对任何计算机造成计算负担
%输入数据矩阵长度可以超过5，但是最初计算出的n个最小值中，重复次数超过2的点的种类只允许为一种
a=[0 20 1 11 2
0 0 9 1 3
0 0 0 13 8
0 0 0 0 6
0 0 0 0 0];
l=length(a)
s1=inf
zp=inf
n2=1
f=a
f(a==0)=inf
b=zeros(l)
i1=0
while i1=l-1
[r c]=find(f==min(min(f)))
b(r⑴，c⑴)=f(r⑴，c⑴)
f(r⑴，c⑴)=inf
i1=i1+1
end
f1=f
[rz cz]=find(b0)
pathz=[rz cz]
pz=[rz;cz]
p2z=zeros（2*l,1）
i2z=1
n2z=0
while i2z=2*l
[r2z c2z]=find(pz==pz(i2z,1）)
k1z=size(r2z)
if k1z（1,1）2
p2z(r2z,1）=pz(r2z,1）
n2z=n2z+1
end
i2z=i2z+1
end
if n2z==2
HHL=b
zp=sum(sum(b))
else
while min(min(f1）)~=inf
if n22
b=snh
end
[r1 c1]=find(b0)
path1=[r1 c1]
p1=[r1;c1]
p2=zeros（2*l,1）
i2=1
n2=0
while i2=2*l
[r2 c2]=find(p1==p1(i2,1）)
k1=size(r2）
if k1（1,1）2
p2(r2,1）=p1(r2,1）
n2=n2+1
end
i2=i2+1
end
[r3 c3]=find(p20)
p3=zeros(l,2）
i3=0
while i3=n2-1
if r3⑴=l
p3(r3⑴，：)=path1(r3⑴，：)
else
p3(r3⑴-l,:)=path1(r3⑴-l,:)
end
r3⑴=[]
i3=i3+1
end
p3(p3==0)=[]
p3=reshape(p3,n2,2）
p8=p2
[r8 c8]=find(p80)
p9=p8
r9=r8
i4=1
while i4=n2
f1(p9(r9⑴，1），：)=inf
f1(:,p9(r9⑴，1）)=inf
r9⑴=[]
i4=i4+1
end
[r4 c4]=find(f1==min(min(f1）))
f1(r4,c4）=inf
b1=b
b1(r4,c4）=a(r4,c4）
i5=1
p4=p3
while i5=n2
b1=b
b1(r4⑴，c4⑴)=a(r4⑴，c4⑴)
b1(p4（1,1），p4（1,2）)=0
p4（1,:)=[]
[r5 c5]=find(b10)
p5=[r5;c5]
i6=1
n6=0
while i6=2*l
[r6 c6]=find(p5==p5(i6,1）)
k6=size(r6）
if k6（1,1）2
n6=n6+1
end
i6=i6+1
end
if n62
if sum(sum(b1）)s1
snh=[]
s1=sum(sum(b1）)
snh=b1
end
else
if sum(sum(b1）)zp
HHL=[]
zp=sum(sum(b1）)
HHL=b1
end
end
i5=i5+1
end
end
[rs cs]=find(HHL0)
minpaths=[rs cs]
journeys=zp
注：这段代码采用分支定界法作为编写程序的依据，因此代码依旧局限在算法上；而且代码的使用对所要计算的数据是有要求的，如下：
⒈只要数据在开始计算出的n个最小值中，其重复次数超过2次的点的种类只能为一种，例如：代码段中的数据五个最小值中其重复次数超过2次的点只有v5。
⒉数据矩阵格式要求：只允许为上三角矩阵，不支持全矩阵以及下三角矩阵的运算。
⒊代码扩展方法请使用者独立思考，不唯一。
⒋运算数据扩展方法，请使用者独立思考，不唯一。
⒌此代码为本人毕设的附加产品，不会对使用此代码者，因理解不当或使用不当而造成的任何不良后果，付出任何责任。
⒍代码仅供交流。
如何判定哈密顿回路 离散数学中 谢谢
依据如下可以判断
1包含个顶点的图, 如果任意两个顶点的度数之和都不小于n-1（即大于等于n-1）, 则存在哈密尔顿通路。
2包含个顶点的图, 如果任意两个顶点的度数之和都不小于n（即大于等于n）, 则存在哈密尔顿回路。
存在哈密尔顿路也就是存在哈密尔顿回路。
“通路”(连通)，“回路”（任意一顶点出发，都可以回到该顶点）
哈密尔顿回路问题具体指什么？
1857年，英国数学家汉密尔顿(Hamilton)提出了著名的汉密尔顿回路问题，其后，该问题进一步被发展成为所谓的“货郎担问题”，即赋权汉密尔顿回路最小化问题：这两个问题成为数学史上著名的难题。而后者在工程优化、现场管理等现实生活中有重要作用：以电站建设为例，如何使若干供货点的总运费最小，施工现场如何使供货时间最短等等，最终都归结为赋权汉密尔顿问题，是电站建设中成本控制和进度优化的关键技术；因而，赋权汉密尔顿问题与主生产计划安排成为电站建设中成本控制和进度优化的两大技术难题。而且，主生产计划安排，又可以分解为有向图的赋权汉密尔顿问题进行解决；因此，赋权汉密尔顿问题在包括电站建设的大型工程建设项目占有重要的地位，具有重大的理论和现实意义。理论上讲，赋权汉密尔顿问题的最优解总可以用枚举法求出；但在实际工作中，枚举法的计算量巨大，对于n个点的问题存在(n－1)!条汉密尔顿回路，当n比较大时，枚举法显然是行不通的，为此，优化专家们提出了启发式算法[1]，以期求得该问题的近似最优解。而不同算法之目的是共同的，即在多项式的运算量内，尽可能提高其解的精度。其中应用比较广泛的有Clarke和Wright的C－W算法，Norback和Love的几何算法[2]，在此，称这些算法为经典启发式算法，简称经典算法，这些算法的一个共同特点就是非优化性。针对这一特点，本文提出一种局部优化的算法，对业已求得的汉密尔顿回路进行优化。这种算法的结果是以经典算法结果为起点的局部优化解，因此，该算法极大改进了经典启发式算法的性能，且在目前可考证的情况下，均能求得最优解；但是，是否在任何情况下都能求得最优解则尚待证明。
哈密顿回路的介绍
哈密顿图（哈密尔顿图）（英语：Hamiltonian path，或Traceable path）是一个无向图，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路（Hamiltonian cycle），含有图中所有顶点的路径称作哈密顿路径。
哈密顿回路的算法是怎样的？
哈密顿回路的算法是指:
在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路。
哈密顿图（哈密尔顿图）（英语：Hamiltonian path，或Traceable path）是一个无向图，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。
这个问题和著名的七桥问题的不同之处在于，过桥只需要确定起点，而不用确定终点。哈密顿问题寻找一条从给定的起点到给定的终点沿 途恰好经过所有其他城市一次的路径。