哈密顿回路的应用
哈密顿图定义概念
哈密顿通路（回路）与哈密顿图（hamilton图）通过图g的每个结点一次，且仅一次的通路（回路），就是哈密顿通路（回路）。存在哈密顿回路的图就是哈密顿图。
1.哈密顿通路 设g=《v，e》为一图（无向图或有向图）.g中经过每个顶点一次且仅一次的通路称作哈密顿通路
2.哈密顿回路 g中经过每个顶点一次且仅一次的回路称作哈密顿回路
3.哈密顿图 若g中存在哈密顿回路，则称它是哈密顿图
4.定义详解： （1）存在哈密顿通路（回路）的图一定是连通图；
（2）哈密顿通路是初级通路，哈密顿回路是初级回路；
（3）若g中存在哈密顿回路，则它一定存在哈密顿通路，反之不真
（4）只有哈密顿通路，无哈密顿回路的图不交哈密顿图；
二、判定定理 注意：目前没有找到哈密顿图的简单的充要条件
（1）设无向图g=《v，e》为哈密顿图，v1是v的任意真子集，则（注：n阶xx图指的是n个顶点，不要迷！）
p（g-v1）《=|v1|
其中，p（g-v1）为g中删除v1后的所得图的连通分支数目，|v1|为v1集合中包含的顶点个数。【哈密顿图存在的必要条件】
推论：有割点的图一定不是哈密顿图
设v是图中的割点，则p（g-v）》=2，由上述定理知g不是哈密顿图
（2）设g是n（n》=3）阶无向简单图，若对于g中的每一对不相邻的顶点u，v，均有
d（u）+d（v）》=n-1
则g中存在哈密顿通路。又若
d（u）+d（v）》=n
则g中存在哈密顿回路，即g为哈密顿图。【哈密顿图存在的充分条件，不是必要条件】
其中d（u），d（v）分别代表顶点u，v的度数。
推论：设g是n（n》=3）阶无向简单图，若g的最小度》=n/2，则g是哈密顿图。
由推论知，对于完全图kn，当n》=3时，是哈密顿图，完全二部图kr，s当r==s》=2时是哈密顿图。
（3）在n（n》=2）阶有向图d=《v，e》中，如果略去所有有向边的方向，所得无向图中含生成子图kn，则d中存在哈密顿通路。
推论：n（n》=3）阶有向完全图是哈密顿图。
1.常用方法判断是哈密顿图： （1）若能通过观察找出图g中的一条哈密顿回路，则g当然是哈密顿图。
（2）若一个无向图g满足上述（2）中的条件，一个有向图d满足上述（3）的推论的条件，则g、d都是哈密顿图。
2.破坏哈密顿图存在的必要条件，判定不是哈密顿图： 设n阶图g是哈密顿图，则g应该满足以下诸条件：
（1）g必须是连通图；
（2）g中的边数m必须大于等于顶点数n；
（3）若g中存在2度顶点v，即d（v）=2，则与v关联的两条边ei，ej必须在g中的任何哈密顿回路上；
（4）若g中存在每条哈密顿回路中出现的边，不能构成边数小于n的初级回路（圈）；
破坏以上诸条件中的一条，都不是哈密顿图。
哈密顿回路的应用 随机生成并哈密顿回路求解： // graph.cpp ： 定义控制台应用程序的入口点。
//
#include “stdafx.h”
#include“graph.h”
#include《iostream》
#include《fstream》
#include《stack》
#include《queue》
#include《limits》
using namespace std;
template《class t，class e》
int sb（int start，graph《t，e》 &mygraph，ostream & fout）//simple backtracking 算法解决图的最小哈密顿回路问题 v为回路的起点和终点
{
e mindistance=std：：numeric_limits《e》：：max（）;
stack《int》 mystack;
mystack.push（start）;
int numvertices=mygraph.numberofvertices（）;
bool *visited=new bool［numvertices］;
memset（visited，false，numvertices）;
int v;
int w=-1;
while（！mystack.empty（）） //栈不为空
{
v=mystack.top（）;
visited［v］=true;
if（w==-1）
{
w=mygraph.getfirstneighbor（v）;
}
else
{
w=mygraph.getnextneighbor（v，w）;
}
for（;w！=-1&&visited［w］==true;w=mygraph.getnextneighbor（v，w））
{
}
if（w==-1） //未找到可行的下一个顶点
{
mystack.pop（）; //回溯
w=v;
visited［v］=false;
}
else //找到可行的下一个顶点
{
mystack.push（w）; //放入栈中
if（mystack.size（）==numvertices）//走过所有的顶点
{
if（mygraph.getweight（start，w）==std：：numeric_limits《e》：：max（）） //判断最后一个顶点有没有回到起点的边
{
mystack.pop（）;
visited［w］=false;
}
else //成功找到回路
{
//输出回路 并记录下回路的长度
stack《int》 temp;
while（！mystack.empty（））
{
int n=mystack.top（）;
temp.push（n）;
mystack.pop（）;
}
fout《《“哈密顿回路 ： ”;
e distance=0;
int n=temp.top（）;
mystack.push（n）;
temp.pop（）;
int last=n;
fout《《n《《“--”;
while（！temp.empty（））
{
n=temp.top（）;
mystack.push（n）;
temp.pop（）;
distance+=mygraph.getweight（last，n）;
last=n;
fout《《n《《“--”;
}
fout《《start《《“--”《《endl;
distance+=mygraph.getweight（last，start）;
fout《《“总长度为：”《《distance《《endl;
//记录最短长度
if（mindistance》distance）
{
mindistance=distance;
}
//
mystack.pop（）;
visited［w］=false;
}
}
else
{
w=-1;
}
}
}
fout《《“最短哈密顿回路的长度为：”《《mindistance《《endl;
return 1;
}
//分支限界法求解最短哈密顿回路问题
template《class e》
struct node
{
int dep; //表示该结点在搜索树的第几层
int *vertices; //该节点力包含的各个顶点
e length; //从根到当前结点已经走过的路径长度
node（int depth）
{
dep=depth;
vertices=new int［dep］;
};
void cpy（int *&des）
{
for（int i=0;i《dep;i++）
{
des［i］=vertices［i］;
}
}
bool find（int v）
{
for（int i=0;i《dep;i++）
{
if（vertices［i］==v）
return true;
}
return false;
}
};
template《class t，class e》
int bb（int start，graph《t，e》 & mygraph，ostream & fout）
{
stack《node《e》》 mystack; //队列
e mindistance=std：：numeric_limits《e》：：max（）;
int s=mygraph.getfirstneighbor（start）;
for（s=mygraph.getnextneighbor（start，s）;s！=-1;s=mygraph.getnextneighbor（start，s））
{
node《e》 n（2）;
n.vertices［0］=start;n.vertices［1］=s;
n.length=mygraph.getweight（start，s）;
mystack.push（n）;
}
while（！mystack.empty（）） //队列不为空
{
node《e》 n=mystack.top（）;
mystack.pop（）;
int v=n.vertices［n.dep-1］;
if（n.dep+1==mygraph.numberofvertices（））//到了最后一层 判断是不是哈密顿回路
{
int w;
for（ w=mygraph.getfirstneighbor（v）;w！=-1;w=mygraph.getnextneighbor（v，w））
{
if（ n.find（w）==false）
break;
}
if（w！=-1）
{
if（mygraph.getweight（w，start）《std：：numeric_limits《e》：：max（））
{
//形成回路
fout《《“哈密顿回路为：”;
for（int i=0;i《n.dep;i++）
{
fout《《n.vertices［i］《《“ ”;
}
fout《《w《《“ ”《《start《《endl;
e tempdistance=n.length+mygraph.getweight（v，w）+mygraph.getweight（w，start）;
fout《《“总长度为： ”《《tempdistance《《endl;
if（mindistance》tempdistance）
{
mindistance=tempdistance;
}
}
}
}
for（int w=mygraph.getfirstneighbor（v）;w！=-1;w=mygraph.getnextneighbor（v，w））
{
if（n.find（w）==false）
{
node《e》 ne（n.dep+1）;
ne.length=n.length+mygraph.getweight（v，w）;
if（ne.length《mindistance）
{
n.cpy（ne.vertices）;
ne.vertices［ne.dep-1］=w;
mystack.push（ne）;
}
}
}
}
fout《《“最短长度为 ”《《mindistance《《endl;
return mindistance;
}
int _tmain（int argc， _tchar* argv［］）
{
graph《char，int》 mygraph（10）;
//ifstream fin（“input.txt”）;
//mygraph.init（fin）;
mygraph.randinit（）;//随机初始化图
ofstream fout（“outputsb.txt”）;
//sb（0，mygraph，fout）;
ofstream fout1（“outputbb.txt”）;
bb（0，mygraph，fout1）;
system（“pause”）;
return 0;
}
超导体的临界条件_超导体的分类
中国卫通拟 39.18 亿元采购卫星项目，新增大容量宽带卫星资源
2024计算机创新大会，极海斩获2项大奖
兰和智能门锁的安全性能
2018世界物联网博览会9月无锡举办，将举办相关主题活动28个
哈密顿回路的应用
华为鸿蒙系统官方下载入口在哪里
开关电源的空载电压怎么用开关电源智能测试系统测量？
安徽英力“YL-NB6368精密笔记本电脑结构件模组” 等技术达到国内领先水平
高频无铅焊台的工作原理_高频无铅焊台的功能
国芯思辰｜基本半导体低开关损耗碳化硅肖特基二极管B1D02065E(替代C3D02065E)助力LED电源效率的提升
使用Arduino制作基本的微型家庭安全系统
台积电3纳米投资计划有望在今年动工 并如期在2022年量产
基于多频段全波形雷电电磁脉冲的实时探测
百度研究院发布了2020年十大科技趋势预测
RA6T2的16位模数转换器操作之验证应用项目
realme X系列手机将于6月1日正式开售搭载骁龙710平台支持VOOC闪充3.0
华为mate9出货量抢跑 2017年手机品牌和渠道大战拉开
如何把LED显示屏安装在玻璃幕墙上
哪些机构可以掌握ETC的大市场
1.哈密顿通路 设g=《v，e》为一图（无向图或有向图）.g中经过每个顶点一次且仅一次的通路称作哈密顿通路
2.哈密顿回路 g中经过每个顶点一次且仅一次的回路称作哈密顿回路
3.哈密顿图 若g中存在哈密顿回路，则称它是哈密顿图
4.定义详解： （1）存在哈密顿通路（回路）的图一定是连通图；
（2）哈密顿通路是初级通路，哈密顿回路是初级回路；
（3）若g中存在哈密顿回路，则它一定存在哈密顿通路，反之不真
（4）只有哈密顿通路，无哈密顿回路的图不交哈密顿图；
二、判定定理 注意：目前没有找到哈密顿图的简单的充要条件
（1）设无向图g=《v，e》为哈密顿图，v1是v的任意真子集，则（注：n阶xx图指的是n个顶点，不要迷！）
p（g-v1）《=|v1|
其中，p（g-v1）为g中删除v1后的所得图的连通分支数目，|v1|为v1集合中包含的顶点个数。【哈密顿图存在的必要条件】
推论：有割点的图一定不是哈密顿图
设v是图中的割点，则p（g-v）》=2，由上述定理知g不是哈密顿图
（2）设g是n（n》=3）阶无向简单图，若对于g中的每一对不相邻的顶点u，v，均有
d（u）+d（v）》=n-1
则g中存在哈密顿通路。又若
d（u）+d（v）》=n
则g中存在哈密顿回路，即g为哈密顿图。【哈密顿图存在的充分条件，不是必要条件】
其中d（u），d（v）分别代表顶点u，v的度数。
推论：设g是n（n》=3）阶无向简单图，若g的最小度》=n/2，则g是哈密顿图。
由推论知，对于完全图kn，当n》=3时，是哈密顿图，完全二部图kr，s当r==s》=2时是哈密顿图。
（3）在n（n》=2）阶有向图d=《v，e》中，如果略去所有有向边的方向，所得无向图中含生成子图kn，则d中存在哈密顿通路。
推论：n（n》=3）阶有向完全图是哈密顿图。
1.常用方法判断是哈密顿图： （1）若能通过观察找出图g中的一条哈密顿回路，则g当然是哈密顿图。
（2）若一个无向图g满足上述（2）中的条件，一个有向图d满足上述（3）的推论的条件，则g、d都是哈密顿图。
2.破坏哈密顿图存在的必要条件，判定不是哈密顿图： 设n阶图g是哈密顿图，则g应该满足以下诸条件：
（1）g必须是连通图；
（2）g中的边数m必须大于等于顶点数n；
（3）若g中存在2度顶点v，即d（v）=2，则与v关联的两条边ei，ej必须在g中的任何哈密顿回路上；
（4）若g中存在每条哈密顿回路中出现的边，不能构成边数小于n的初级回路（圈）；
破坏以上诸条件中的一条，都不是哈密顿图。
哈密顿回路的应用 随机生成并哈密顿回路求解： // graph.cpp ： 定义控制台应用程序的入口点。
//
#include “stdafx.h”
#include“graph.h”
#include《iostream》
#include《fstream》
#include《stack》
#include《queue》
#include《limits》
using namespace std;
template《class t，class e》
int sb（int start，graph《t，e》 &mygraph，ostream & fout）//simple backtracking 算法解决图的最小哈密顿回路问题 v为回路的起点和终点
{
e mindistance=std：：numeric_limits《e》：：max（）;
stack《int》 mystack;
mystack.push（start）;
int numvertices=mygraph.numberofvertices（）;
bool *visited=new bool［numvertices］;
memset（visited，false，numvertices）;
int v;
int w=-1;
while（！mystack.empty（）） //栈不为空
{
v=mystack.top（）;
visited［v］=true;
if（w==-1）
{
w=mygraph.getfirstneighbor（v）;
}
else
{
w=mygraph.getnextneighbor（v，w）;
}
for（;w！=-1&&visited［w］==true;w=mygraph.getnextneighbor（v，w））
{
}
if（w==-1） //未找到可行的下一个顶点
{
mystack.pop（）; //回溯
w=v;
visited［v］=false;
}
else //找到可行的下一个顶点
{
mystack.push（w）; //放入栈中
if（mystack.size（）==numvertices）//走过所有的顶点
{
if（mygraph.getweight（start，w）==std：：numeric_limits《e》：：max（）） //判断最后一个顶点有没有回到起点的边
{
mystack.pop（）;
visited［w］=false;
}
else //成功找到回路
{
//输出回路 并记录下回路的长度
stack《int》 temp;
while（！mystack.empty（））
{
int n=mystack.top（）;
temp.push（n）;
mystack.pop（）;
}
fout《《“哈密顿回路 ： ”;
e distance=0;
int n=temp.top（）;
mystack.push（n）;
temp.pop（）;
int last=n;
fout《《n《《“--”;
while（！temp.empty（））
{
n=temp.top（）;
mystack.push（n）;
temp.pop（）;
distance+=mygraph.getweight（last，n）;
last=n;
fout《《n《《“--”;
}
fout《《start《《“--”《《endl;
distance+=mygraph.getweight（last，start）;
fout《《“总长度为：”《《distance《《endl;
//记录最短长度
if（mindistance》distance）
{
mindistance=distance;
}
//
mystack.pop（）;
visited［w］=false;
}
}
else
{
w=-1;
}
}
}
fout《《“最短哈密顿回路的长度为：”《《mindistance《《endl;
return 1;
}
//分支限界法求解最短哈密顿回路问题
template《class e》
struct node
{
int dep; //表示该结点在搜索树的第几层
int *vertices; //该节点力包含的各个顶点
e length; //从根到当前结点已经走过的路径长度
node（int depth）
{
dep=depth;
vertices=new int［dep］;
};
void cpy（int *&des）
{
for（int i=0;i《dep;i++）
{
des［i］=vertices［i］;
}
}
bool find（int v）
{
for（int i=0;i《dep;i++）
{
if（vertices［i］==v）
return true;
}
return false;
}
};
template《class t，class e》
int bb（int start，graph《t，e》 & mygraph，ostream & fout）
{
stack《node《e》》 mystack; //队列
e mindistance=std：：numeric_limits《e》：：max（）;
int s=mygraph.getfirstneighbor（start）;
for（s=mygraph.getnextneighbor（start，s）;s！=-1;s=mygraph.getnextneighbor（start，s））
{
node《e》 n（2）;
n.vertices［0］=start;n.vertices［1］=s;
n.length=mygraph.getweight（start，s）;
mystack.push（n）;
}
while（！mystack.empty（）） //队列不为空
{
node《e》 n=mystack.top（）;
mystack.pop（）;
int v=n.vertices［n.dep-1］;
if（n.dep+1==mygraph.numberofvertices（））//到了最后一层 判断是不是哈密顿回路
{
int w;
for（ w=mygraph.getfirstneighbor（v）;w！=-1;w=mygraph.getnextneighbor（v，w））
{
if（ n.find（w）==false）
break;
}
if（w！=-1）
{
if（mygraph.getweight（w，start）《std：：numeric_limits《e》：：max（））
{
//形成回路
fout《《“哈密顿回路为：”;
for（int i=0;i《n.dep;i++）
{
fout《《n.vertices［i］《《“ ”;
}
fout《《w《《“ ”《《start《《endl;
e tempdistance=n.length+mygraph.getweight（v，w）+mygraph.getweight（w，start）;
fout《《“总长度为： ”《《tempdistance《《endl;
if（mindistance》tempdistance）
{
mindistance=tempdistance;
}
}
}
}
for（int w=mygraph.getfirstneighbor（v）;w！=-1;w=mygraph.getnextneighbor（v，w））
{
if（n.find（w）==false）
{
node《e》 ne（n.dep+1）;
ne.length=n.length+mygraph.getweight（v，w）;
if（ne.length《mindistance）
{
n.cpy（ne.vertices）;
ne.vertices［ne.dep-1］=w;
mystack.push（ne）;
}
}
}
}
fout《《“最短长度为 ”《《mindistance《《endl;
return mindistance;
}
int _tmain（int argc， _tchar* argv［］）
{
graph《char，int》 mygraph（10）;
//ifstream fin（“input.txt”）;
//mygraph.init（fin）;
mygraph.randinit（）;//随机初始化图
ofstream fout（“outputsb.txt”）;
//sb（0，mygraph，fout）;
ofstream fout1（“outputbb.txt”）;
bb（0，mygraph，fout1）;
system（“pause”）;
return 0;
}
超导体的临界条件_超导体的分类
中国卫通拟 39.18 亿元采购卫星项目，新增大容量宽带卫星资源
2024计算机创新大会，极海斩获2项大奖
兰和智能门锁的安全性能
2018世界物联网博览会9月无锡举办，将举办相关主题活动28个
哈密顿回路的应用
华为鸿蒙系统官方下载入口在哪里
开关电源的空载电压怎么用开关电源智能测试系统测量？
安徽英力“YL-NB6368精密笔记本电脑结构件模组” 等技术达到国内领先水平
高频无铅焊台的工作原理_高频无铅焊台的功能
国芯思辰｜基本半导体低开关损耗碳化硅肖特基二极管B1D02065E(替代C3D02065E)助力LED电源效率的提升
使用Arduino制作基本的微型家庭安全系统
台积电3纳米投资计划有望在今年动工 并如期在2022年量产
基于多频段全波形雷电电磁脉冲的实时探测
百度研究院发布了2020年十大科技趋势预测
RA6T2的16位模数转换器操作之验证应用项目
realme X系列手机将于6月1日正式开售搭载骁龙710平台支持VOOC闪充3.0
华为mate9出货量抢跑 2017年手机品牌和渠道大战拉开
如何把LED显示屏安装在玻璃幕墙上
哪些机构可以掌握ETC的大市场