哈密顿回路

哈密顿图(哈密尔顿图)(英语:Hamiltoni来自an graph，或Traceable g新并移越讲去升raph)是一个无向图360百科，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。在图论中是指含较杀火整脱有哈密顿回路的图，闭合的哈密顿路径称江胡正视告教作哈密顿回路(Hamiltonian cycle)，含有图中所有顶钱升包料革据点的路径称作哈密顿路径(棉挥刘首画造众Hamiltonian path)。

• 中文名称 哈密顿回路
• 外文名称 Hamiltonian cycle
• 别名 闭合的哈密顿路径
• 说明 是一个无向图
• 提出者 天文学家哈密顿

定义

　　哈密顿回路的定义: G=(V,E)是一个图，若G中一条来自路径通过且仅通过每一个顶点一次，称这条路径为哈密顿路径。若G中一个回路通过且仅通过每一个顶点一次，称这个环为哈密顿回路。若一个图存在哈密顿回路，就称为哈密顿图。

由来

　　天文学家哈密顿(William Rowan Hamilton) 提出，在一个有多个城市的地图网络中，寻找一条从给定的起点到给定的终点沿 途恰好经过所有其他城市一次的路径。

　　这个问题和著名的七桥问题的不同之处在于，七桥问题是经过每条边一次，而360百科哈密顿问题是经过每个顶点一次。哈密顿问题寻找一条从给定的起点到给定的终点沿途恰好经过所益体得石然有其他城市一次的路径。

判断条件

　　哈密顿图的必要条件: 若G=(V,E) 是一个哈密顿图，则对于V的每一个非空子集S，唱合均有W(G-S) ≤|S|。其中|S|是S中的顶点数，W(G-S)表示图G擦去属长吧不阿早每在土且德于S中的顶点后，剩下族套坐日子图的连通分支的个数。

　　哈密顿图的充分条件来自: 设G=(V,E)是一个无向简单图，|V|=n. n≥3. 若对于任编令错当宁末意的两个顶点u，v∊V，d(u)+d(v) ≥n，那么, G是哈密尔顿图。此条件由美国图论数学家360百科奥勒在1960年给出。

算法

　　哈密顿路径问题在上世纪高械矿调七十年代初，终于被证明是"NP完全"的。据说具有这样性质的问题，难于找到一个有效的算法。实际上对于某些顶点数不到100的网络，利用现有最好的算法和计算机也需要比较荒唐的时间(比如几百年)才能确定其是否存在一条这样的路径。

六够全话育　　从图中的任意一点出发，路途中经过图中每曲技守蒸况止一个结点当且仅当一次，则成为哈密顿回路。

　　要满足两个条件:

　　⒈封闭的环

　　⒉是一个连错汉血通图，且图中任意两点可达

　　经过图(有向图或无向图)中所有顶点一次且仅一次的通路称为哈密顿通路。

　　经过图中所有顶点一次且仅一次的回路称为哈密顿回路。

　　具有哈密顿回路的图称为哈密顿图，具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图。

　　平凡图是哈密顿图。

　　⒊若以1到2、2到3、3到4、4到5、5到1，为计数规律，则各点均出现两次;这种判断方法院查该应永视放最间受压在计算机编程运算稳针孙左杨中显得尤为重要，其会精简很多掌早配令扬饭们查运算过程。

　　⒋新出炉，有待检测的代码如下:

　　注:这段代码采用分支定界法作为编写程序的依据，院践因此代码依旧局限在算法上;而且代码的使用对所要计算的数据是有要求的，决如下:

　　⒈只要数据在开始计算出的n个最小值中，其重互理命质不注求银旧复次数超过2次的点的种类只能为一种，例如:代码段中的数据五个最小值中其重复次数超过2次的点只有v5。

　　⒉数据矩阵格式要求:只允许为上三角矩阵，烟周举磁权不支持全矩阵以及下三角矩架阵的运算。

　　⒊代码扩展方法请使用者独立思考，不唯一。

　　⒋运算数据扩展方法，请使用者独立思考，不唯一。

　　⒌此代码为本人毕设的附加产品，不会对使用此代码者，因理解不当或使用不当而造成的任何不良后果，付出任何责任。

　　⒍代码仅供弱林感染密传交流。