《哈密顿回路的应用.doc》由会员分享,可在线阅读,更多相关《哈密顿回路的应用.doc(10页珍藏版)》请在三一文库上搜索。
1、哈密顿回路的应用哈密顿图定义概念哈密顿通路(回路)与哈密顿图(Hamilton图)通过图G的每个结点一次,且仅一次的通路(回路),就是哈密顿通路(回路)。存在哈密顿回路的图就是哈密顿图。1.哈密顿通路设G=V,E为一图(无向图或有向图).G中经过每个顶点一次且仅一次的通路称作哈密顿通路2.哈密顿回路G中经过每个顶点一次且仅一次的回路称作哈密顿回路3.哈密顿图若G中存在哈密顿回路,则称它是哈密顿图4.定义详解:(1)存在哈密顿通路(回路)的图一定是连通图;(2)哈密顿通路是初级通路,哈密顿回路是初级回路;(3)若G中存在哈密顿回路,则它一定存在哈密顿通路,反之不真(4)只有哈密顿通路,无哈密顿回
2、路的图不交哈密顿图;注意:目前没有找到哈密顿图的简单的充要条件(1)设无向图G=V,E为哈密顿图,V1是V的任意真子集,则(注:n阶xx图指的是n个顶点,不要迷!)其中,p(G-V1)为G中删除V1后的所得图的连通分支数目,|V1|为V1集合中包含的顶点个数。【哈密顿图存在的必要条件】推论:有割点的图一定不是哈密顿图设v是图中的割点,则p(G-v)=2,由上述定理知G不是哈密顿图(2)设G是n(n=3)阶无向简单图,若对于G中的每一对不相邻的顶点u,v,均有则G中存在哈密顿通路。又若则G中存在哈密顿回路,即G为哈密顿图。【哈密顿图存在的充分条件,不是必要条件】其中d(u),d(v)分别代表顶点
3、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阶
4、图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”#includeiostream#includefstream#includestack#includeq
5、ueue#includelimitsusing namespace std;templateclass T,class Eint sb(int start,GraphT,E E minDistance=std:numeric_limitsE:max();stackint myStack;myStack.push(start);int numVertices=myGraph.NumberOfVertices();bool *visited=new boolnumVertices;memset(visited,false,numVertices);int v;int w=-1;while(!myS
6、tack.empty() /栈不为空v=myStack.top();visitedv=true;if(w=-1)w=myGraph.getFirstNeighbor(v);elsew=myGraph.getNextNeighbor(v,w);for(;w!=-1w=myGraph.getNextNeighbor(v,w)if(w=-1) /未找到可行的下一个顶点myStack.pop(); /回溯w=v;visitedv=false;else /找到可行的下一个顶点myStack.push(w); /放入栈中if(myStack.size()=numVertices)/走过所有的顶点if(my
7、Graph.getWeight(start,w)=std:numeric_limitsE:max() /判断最后一个顶点有没有回到起点的边myStack.pop();visitedw=false;else /成功找到回路/输出回路 并记录下回路的长度stackint 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;foutn“-”;
8、while(!temp.empty()n=temp.top();myStack.push(n);temp.pop();distance+=myGraph.getWeight(last,n);last=n;foutn“-”;foutstart“-”endl;distance+=myGraph.getWeight(last,start);fout“总长度为:”distanceendl;/记录最短长度if(minDistancedistance)minDistance=distance;/myStack.pop();visitedw=false;elsew=-1;fout“最短哈密顿回路的长度为:”
9、minDistanceendl;return 1;/分支限界法求解最短哈密顿回路问题templateclass Estruct NODEint dep; /表示该结点在搜索树的第几层int *vertices; /该节点力包含的各个顶点E length; /从根到当前结点已经走过的路径长度NODE(int depth)dep=depth;vertices=new intdep;void cpy(int *for(int i=0;idep;i+)desi=verticesi;bool find(int v)for(int i=0;idep;i+)if(verticesi=v)return tru
10、e;return false;templateclass T,class Eint bb(int start,GraphT,E stackNODEE myStack; /队列E minDistance=std:numeric_limitsE:max();int s=myGraph.getFirstNeighbor(start);for(s=myGraph.getNextNeighbor(start,s);s!=-1;s=myGraph.getNextNeighbor(start,s)NODEE n(2);n.vertices0=start;n.vertices1=s;n.length=myGr
11、aph.getWeight(start,s);myStack.push(n);while(!myStack.empty() /队列不为空NODEE n=myStack.top();myStack.pop();int v=n.verticesn.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(my
12、Graph.getWeight(w,start)std:numeric_limitsE:max()/形成回路fout“哈密顿回路为:”;for(int i=0;in.dep;i+)foutn.verticesi“ ”;foutw“ ”startendl;E tempDistance=n.length+myGraph.getWeight(v,w)+myGraph.getWeight(w,start);fout“总长度为: ”tempDistanceendl;if(minDistancetempDistance)minDistance=tempDistance;for(int w=myGraph.
13、getFirstNeighbor(v);w!=-1;w=myGraph.getNextNeighbor(v,w)if(n.find(w)=false)NODEE ne(n.dep+1);ne.length=n.length+myGraph.getWeight(v,w);if(ne.lengthminDistance)n.cpy(ne.vertices);ne.verticesne.dep-1=w;myStack.push(ne);fout“最短长度为 ”minDistanceendl;return minDistance;int _tmain(int argc, _TCHAR* argv)Graphchar,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;
链接地址:https://www.31doc.com/p-3406258.html