哈密顿回路算法.doc
《哈密顿回路算法.doc》由会员分享,可在线阅读,更多相关《哈密顿回路算法.doc(12页珍藏版)》请在三一文库上搜索。
1、哈密顿回路算法概念:哈密顿图:图G的一个回路,若它通过图的每一个节点一次,且仅一次,就是哈密顿回路。存在哈密顿回路的图就是哈密顿图。哈密顿图就是从一点出发,经过所有的必须且只能一次,最终回到起点的路径。图中有的边可以不经过,但是不会有边被经过两次。与欧拉图的区别:欧拉图讨论的实际上是图上关于边的可行便利问题,而哈密顿图的要求与点有关。判定:一:Dirac定理(充分条件)设一个无向图中有N个顶点,若所有顶点的度数大于等于N/2,则哈密顿回路一定存在。(N/2指的是N/2,向上取整)二:基本的必要条件设图G=V, E是哈密顿图,则对于v的任意一个非空子集S,若以|S|表示S中元素的数目,G-S表示
2、G中删除了S中的点以及这些点所关联的边后得到的子图,则W(G-S)=|S|成立。其中W(G-S)是G-S中联通分支数。三:竞赛图(哈密顿通路)N(N=2)阶竞赛图一点存在哈密顿通路。算法:一:在Dirac定理的前提下构造哈密顿回路过程:1:任意找两个相邻的节点S和T,在其基础上扩展出一条尽量长的没有重复结点的路径。即如果S与结点v相邻,而且v不在路径S - T上,则可以把该路径变成v - S - T,然后v成为新的S.从S和T分别向两头扩展,直到无法继续扩展为止,即所有与S或T相邻的节点都在路径S - T上。2:若S与T相邻,则路径S - T形成了一个回路。3:若S与T不相邻,可以构造出来一个
3、回路。设路径S - T上有k+2个节点,依次为S, v1, v2, 。, vk, T.可以证明存在节点vi(i属于1, k),满足vi与T相邻,且vi+1与S相邻。找到这个节点vi,把原路径变成S - vi - T - vi+1 - S,即形成了一个回路。4:到此为止,已经构造出来了一个没有重复节点的的回路,如果其长度为N,则哈密顿回路就找到了。如果回路的长度小于N,由于整个图是连通的,所以在该回路上,一定存在一点与回路之外的点相邻。那么从该点处把回路断开,就变回了一条路径,同时还可以将与之相邻的点加入路径。再按照步骤1的方法尽量扩展路径,则一定有新的节点被加进来。接着回到路径2.证明:可利用
4、鸽巢原理证明。伪代码:设s为哈密顿回路的起始点,t为哈密顿回路中终点s之前的点.ans为最终的哈密顿回路。倒置的意思指的是将数组对应的区间中数字的排列顺序方向。1:初始化,令s = 1,t为s的任意一个邻接点。2:如果ans中元素的个数小于n,则从t开始向外扩展,如果有可扩展点v,放入ans的尾部,并且t=v,并继续扩展,如无法扩展进入步骤3.3:将当前得到的ans倒置,s和t互换,从t开始向外扩展,如果有可扩展点v,放入ans尾部,并且t=v,并继续扩展。如无法扩展进入步骤4.4:如果当前s和t相邻,进入步骤5.否则,遍历ans,寻找点ansi,使得ansi与t相连并且ansi +与相连,将
5、从ansi + 1到t部分的ans倒置,t=ansi +,进如步骤5.5:如果当前ans中元素的个数等于n,算法结束,ans中保存了哈密顿回路(可看情况是否加入点s)。否则,如果s与t连通,但是ans中的元素的个数小于n,则遍历ans,寻找点ansi,使得ansi与ans外的一点(j)相连,则令s=ansi - 1,t = j,将ans中s到ansi - 1部分的ans倒置,将ans中的ansi到t的部分倒置,将点j加入到ans的尾部,转步骤2.时间复杂度:如果说每次到步骤5算一轮的话,那么由于每一轮当中至少有一个节点被加入到路径S - T中,所以总的轮数肯定不超过n轮,所以时间复杂度为O(n
6、)。空间上由于边数非常多,所以采用邻接矩阵来存储比较适合。代码:const int maxN = 100;inline void reverse(int arvmaxN + 7, int s, int t)/将数组anv从下标s到t的部分的顺序反向int temp;while(s t)temp = arvs;arvs = arvt;arvt = temp;s+;t-;void Hamilton(int ansmaxN + 7, bool mapmaxN + 7maxN + 7, int n)int s = 1, t;/初始化取s为1号点int ansi = 2;int i, j;int w;i
7、nt temp;bool visitmaxN + 7 = false;for(i = 1; i = n; i+) if(mapsi) break;t = i;/取任意邻接与s的点为tvisits = visitt = true;ans0 = s;ans1 = t;while(true)while(true)/从t向外扩展for(i = 1; i = n; i+)if(mapti ansansi+ = i;visiti = true;t = i;break;if(i n) break;w = ansi - 1;/将当前得到的序列倒置,s和t互换,从t继续扩展,相当于在原来的序列上从s向外扩展i
8、= 0;reverse(ans, i, w);temp = s;s = t;t = temp;while(true)/从新的t继续向外扩展,相当于在原来的序列上从s向外扩展for(i = 1; i = n; i+)if(mapti ansansi+ = i;visiti = true;t = i;break;if(i n) break;if(!mapst)/如果s和t不相邻,进行调整for(i = 1; i ansi - 2; i+)/取序列中的一点i,使得ansi与t相连,并且ansi+1与s相连if(mapansit w = ansi - 1;i+;t = ansi;reverse(ans
9、, i, w);/将从ansi +到部分的ans倒置/此时s和t相连if(ansi = n) return;/如果当前序列包含n个元素,算法结束for(j = 1; j = n; j+)/当前序列中元素的个数小于n,寻找点ansi,使得ansi与ans外的一个点相连if(visitj) continue;for(i = 1; i ansi - 2; i+)if(mapansij)break;if(mapansij) break;s = ansi - 1;t = j;/将新找到的点j赋给treverse(ans, 0, i - 1);/将ans中s到ansi-1的部分倒置reverse(ans,
10、 i, ansi - 1);/将ans中ansi到t的部分倒置ansansi+ = j;/将点j加入到ans尾部visitj = true;二:N(N=2)阶竞赛图构造哈密顿通路N阶竞赛图:含有N个顶点的有向图,且每对顶点之间都有一条边。对于N阶竞赛图一定存在哈密顿通路。数学归纳法证明竞赛图在n = 2时必存在哈密顿路:(1)n = 2时结论显然成立;(2)假设n = k时,结论也成立,哈密顿路为V1, V2, V3, 。, Vk;设当n = k+1时,第k + 1个节点为V(k+1),考虑到V(k+1)与Vi(1=i=k)的连通情况,可以分为以下两种情况。1:Vk与V(k+1)两点之间的弧为
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 哈密 回路 算法
链接地址:https://www.31doc.com/p-3406256.html