欧拉图和哈密尔顿图

欧拉图和哈密尔顿图欧拉图和哈密尔顿图欧拉图和哈密尔顿图欧拉路径/回路一.欧拉回路：一般不限于简单图，一般指无向图原问题：“右边的图中是否存在包含每条边一次且恰好一次的回路？”原问题等价于：欧拉图

CDABACBDEg.哥尼斯堡七桥问题<定义>欧拉回路，欧拉通路图G的一个回路/通路,它经过G中每条边恰好一次，则回路/通路称为欧拉回路/通路。定义：如果图G中含欧拉回路，则图G称为欧拉图。定义：如果图G中仅有欧拉通路，但没有欧拉回路，则图G称为半欧拉图。

例“一笔划”问题——G中有欧拉通路？实例上图中，(1),(4)为欧拉图我们定义奇点是指跟这个点相连的边数目有奇数个的点。对于能够一笔画的图，我们有以下两个定理。

定理1：存在欧拉路的条件：图是连通的，有且只有2个奇点。

定理2：存在欧拉回路的条件：图是连通的，有0个奇点。两个定理的正确性是显而易见的，既然每条边都要经过一次，那么对于欧拉路，除了起点和终点外，每个点如果进入了一次，显然一定要出去一次，显然是偶点。对于欧拉回路，每个点进入和出去次数一定都是相等的，显然没有奇点。

欧拉图

练习1、下图是某展览馆的平面图，一个参观者能否不重复地穿过每一扇门？如果不能，请说明理由。如果能，应从哪开始走？

欧拉图右图中只有A，D两个奇点，是一笔画，所以答案是肯定的，应该从A或D展室开始走。

欧拉图

例一个邮递员投递信件要走的街道如下左图所示，图中的数字表示各条街道的千米数，他从邮局出发，要走遍各街道，最后回到邮局。怎样走才能使所走的行程最短？全程多少千米？邮局212111

怎么样使非欧拉图变为欧拉图？除去奇点！添加边或删除边。怎么样除去奇点？该题应该采用的办法？重复某些边（添加边）。

欧拉图解：图中共有8个奇点，不可能不重复地走遍所有的路。必须在8个奇点间添加4条线，才能消除所有奇点，从而成为能从邮局出发最后返回邮局的一笔画。当然要在距离最近的两个奇点间添加一条连线，如图中虚线所示，共添加4条连线，这4条连线表示要重复走的路显然，这样重复走的路程最短，全程34千米。走法参考下右图(走法不唯一)。212111

欧拉图2、右图中每个小正方形的边长都是100米。小明沿线段从A点到B点，不许走重复路，他最多能走多少米？该题应该采用的办法？删除某些边，除去奇点对，将A、B变为基点！

欧拉图解：这道题大多数同学都采用试画的方法，实际上还是用欧拉图的判定定理来求解更合理、快捷。首先，图中有8个奇点，在8个奇点之间至少要去掉4条线段，才能使这8个奇点变成偶点；其次，从A点出发到B点，A，B两点必须是奇点，现在A，B都是偶点，必须在及A，B连接的线段中各去掉1条线段，使A，B成为奇点。所以至少要去掉6条线段，也就是最多能走1800米，走法如下图。

欧拉图求欧拉路的算法很简单，使用深度优先遍历即可。根据一笔画的两个定理，如果寻找欧拉回路，对任意一个点执行深度优先遍历；找欧拉路，则对一个奇点执行DFS，时间复杂度为O(m+n)，m为边数，n是点数。

欧拉图算法以下是寻找一个图的欧拉路的算法实现：样例输入:第一行n，m，有n个点，m条边，以下m行描述每条边连接的两点。551223344551样例输出:欧拉路或欧拉回路154321

欧拉图算法【参考程序】Euler.cpp#include<iostream>#include<cstring>usingnamespacestd;#definemaxn101intg[maxn][maxn];//此图用邻接矩阵存储intdu[maxn];//记录每个点的度，就是相连的边的数目intcircuit[maxn];//用来记录找到的欧拉路的路径intn,e,circuitpos,i,j,x,y,start;voidfind_circuit(inti)//这个点深度优先遍历过程寻找欧拉路{intj;for(j=1;j<=n;j++)if(g[i][j]==1)//从任意一个及它相连的点出发{g[j][i]=g[i][j]=0;find_circuit(j);}circuit[++circuitpos]=i;//记录下路径}

欧拉图算法intmain(){memset(g,0,sizeof(g));cin>>n>>e;for(i=1;i<=e;i++){cin>>x>>y;g[y][x]=g[x][y]=1;du[x]++;//统计每个点的度du[y]++;}start=1;//如果有奇点，就从奇点开始寻找，这样找到的就是for(i=1;i<=n;i++)//欧拉路。没有奇点就从任意点开始，if(du[i]%2==1)//这样找到的就是欧拉回路。(因为每一个点都是偶点)start=i;circuitpos=0;find_circuit(start);for(i=1;i<=circuitpos;i++)cout<<circuit[i]<<'';cout<<endl;return0;}

欧拉图算法注意以上程序具有一定的局限性，对于下面这种情况它不能很好地处理：上图具有多个欧拉回路，而本程序只能找到一个回路。读者在遇到具体问题时，还应对程序作出相应的修改。

欧拉图算法2、铲雪车snow【问题描述】随着白天越来越短夜晚越来越长，我们不得不考虑铲雪问题了。整个城市所有的道路都是双车道，因为城市预算的削减，整个城市只有1辆铲雪车。铲雪车只能把它开过的地方（车道）的雪铲干净，无论哪儿有雪，铲雪车都得从停放的地方出发，游历整个城市的街道。现在的问题是：最少要花多少时间去铲掉所有道路上的雪呢？【输入格式】输入数据的第1行表示铲雪车的停放坐标（x,y），x，y为整数，单位为米。下面最多有100行，每行给出了一条街道的起点坐标和终点坐标，所有街道都是笔直的，且都是双向一个车道。铲雪车可以在任意交叉口、或任何街道的末尾任意转向，包括转U型弯。铲雪车铲雪时前进速度为20km/h，不铲雪时前进速度为50km/h。保证：铲雪车从起点一定可以到达任何街道。【输出格式】

铲掉所有街道上的雪并且返回出发点的最短时间，精确到分种。【输入样例】

1

00

001000010000

5000-10000500010000

5000100001000010000【输出样例】

3:55【注解】

3小时55分钟3、骑马修栅栏【问题描述】农民John每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。

John是一个及其他农民一样懒的人。他讨厌骑马，因此从来不两次经过一个一个栅栏。你必须编一个程序，读入栅栏网络的描述，并计算出一条修栅栏的路径，使每个栅栏都恰好被经过一次。John能从任何一个顶点(即两个栅栏的交点)开始骑马，在任意一个顶点结束。每一个栅栏连接两个顶点，顶点用1到500标号(虽然有的农场并没有500个顶点)。一个顶点上可连接任意多(>=1)个栅栏。所有栅栏都是连通的(也就是你可以从任意一个栅栏到达另外的所有栅栏)。你的程序必须输出骑马的路径(用路上依次经过的顶点号码表示)。我们如果把输出的路径看成是一个500进制的数，那么当存在多组解的情况下，输出500进制表示法中最小的一个(也就是输出第一个数较小的，如果还有多组解，输出第二个数较小的，等等)。输入数据保证至少有一个解。【输入格式】fence.in第1行:一个整数F(1<=F<=1024)，表示栅栏的数目第2到F+1行:每行两个整数i,j(1<=i,j<=500)表示这条栅栏连接i与j号顶点。【输出格式】fence.out输出应当有F+1行，每行一个整数，依次表示路径经过的顶点号。注意数据可能有多组解，但是只有上面题目要求的那一组解是认为正确的。【输入样例】【输出样例】91223344245255657461234254657哈密尔顿图问题也是由一则游戏引入的：1859年，爱尔兰数学家Hamilton提出的，如图的正十二面体，以12个正五边形为面。又称为正则柏拉图体。这些正五边形的三边相交及20个顶点的一个多面体。Hamilton用正十二面体代表地球。游戏题的内容是：沿着正十二面体的棱寻找一条旅行路线，通过每个城市恰好一次又回到出发城市。这便是Hamilton回路问题。哈密尔顿图

欧拉回路是指不重复地走过所有路径的回路，而哈密尔顿环是指不重复地走过所有的点，并且最后还能回到起点的回路定义：通过图G的每个结点一次且仅一次的环称为哈密尔顿环。具有哈密尔顿环的图称为哈密尔顿图。通过图G的每个结点一次且仅一次的开路称为哈密尔顿路。具有哈密尔顿路的图称为半哈密尔顿图。

例半哈密尔顿图

哈密尔顿图

哈密尔顿图N哈密尔顿图周游世界的游戏——的解哈密顿图

哈密顿图哈密顿图无哈密顿通路存在哈密顿通路实例在上图中，(1),(2)是哈密顿图;实例

已知有关人员a,b,c,d,e,f,g的有关信息

a：说英语；

b：说英语或西班牙语；

c；说英语，意大利语和俄语；

d：说日语和西班牙语

e：说德语和意大利语；

f：说法语、日语和俄语；

g：说法语和德语.试问：上述7人中是否任意两人都能交谈？

(可借助其余5人中组成的译员链帮助) 解设7个人为7个结点,将两个懂同一语言的人之间连一条边(即他们能直接交谈),这样就得到一个简单图G,问题就转化为G是否连通.如图所示,因为G的任意两个结点是连通的,所以G是连通图.因此,上述7个人中任意两个人能交谈.

a：说英语；b：说英语或西班牙语；C:说英语,意大利语和俄语；d：说日语和西班牙语e：说德语和意大利语；f：说法语、日语和俄语；g：说法语和德语.abcdefg解一解二abcdefg英英西日法德意如果题目改为：试问这7个人应如何安排座位,才能使每个人都能及他身边的人交谈？解：用结点表示人，用边表示连接的两个人能说讲一种语言，够造出哈密顿图如右上图所示。a：说英语；b：说英语或西班牙语；c；说英语，意大利语和俄语；d：说日语和西班牙语e：说德语和意大利语；f：说法语、日语和俄语；g：说法语和德语.判断H-图任何一个H_图都可以看成是一个基本回路，再加上其他若干条边H_图的充分条件和必要条件均有，但尚无充要条件H_图的必要条件定理：若图G=（V，E）是哈密尔顿图，则对于V的任意一个非空子集V1，有p（G–V1）≤|V1|

这里p（G–V1）表示从G中删除V1（删除S中的各结点及相关联的边）后所剩图的分图（连通分支）数。|V1|表示V1中的结点数。推论若图G=（V，E）是半哈密尔顿图，则对于V的任意一个非空子集V1，有p（G–V1）≤|V1|＋1.H_图的必要条件例.有H_通路，无H_回路设S={v1,v4}，

|S|=2

W(G-S)=3

2

=

|S|

例

在图（a）中去掉结点u以后p（G–{u}）=2，（b）中去掉结点u1和u2以后，p（G–{u1，u2}）=3，由此可以判定，这两个图都不是哈密尔顿图。u1u1u1(a)(b)H_图的必要条件但必须要说明的是满足定理条件的不一定是哈密顿图。如下图著名的彼得森(Petersen)图是满足定理条件的，但不是哈密顿图。利用哈密顿图的必要条件可以用来判定某些图不是哈密顿图,但不便于应用。因为要检查G的顶点集V的所有子集。H_图的必要条件必要条件的局限性

——只能判定一个图不是哈密尔顿图下图(Petersen图)满足上述必要条件。

Petersen图不是H_图。H-图的充分条件[定理]简单G有n个结点，n3，若G中任二点度数和大于等于n，则G有H-图注意此为充分条件，非必要条件例.N边形，n5任一对结点度数和=4<5但它显然是H_图例.Kn是完全图

d(vi)+d(vj)=(n-1)+(n-1)=2n-2n(n3)∴Kn是H-图至今没有一个像欧拉图的充要条件那样关于哈密顿图、半哈密顿图的充分必要条件但能体会到是边多还是边少是哈密顿图的可能大？只要图中边足够多，G易为H_图只要图中成对节点度数足够大，G易为H_图使用简单的深度优先搜索，就能求出一张图中所有的哈密尔顿环。下面给出一段参考程序：#include<iostream>#include<cstring>usingnamespacestd;intstart,length,x,n;boolvisited[101],v1[101];intans[101],num[101];intg[101][101];voidprint(){inti;for(i=1;i<=length;i++)cout<<''<<ans[i];cout<<endl;}voiddfs(intlast,inti)//图用数组模拟邻接表存储，访问点i，last表示上次访问的点{visited[i]=true;//标记为已经访问过v1[i]=true;//标记为已在一张图中出现过ans[++length]=i;//记录下答案for(intj=1;j<=num[i];j++){if(g[i][j]==x&&g[i][j]!=last)//回到起点，构成哈密尔顿环{ ans[++length]=g[i][j];print();//这里说明找到了一个环，则输出ans数组。 length--; break; }if(!visited[g[i][j]])dfs(i,g[i][j]);//遍历及i相关联的所有未访问过的顶点}length--;visited[i]=false;//这里是回溯过程，注意v1的值不恢复。}intmain(){memset(visited,false,sizeof(visited));memset(v1,false,sizeof(v1));for(x=1;x<=n;x++)//每一个点都作为起点尝试访问，因为不是从任何一点开始都能找过整个图的if(!v1[x])//如果点x不在之前曾经被访问过的图里。{length=0;//定义一个ans数组存答案，length记答案的长度。dfs(x);}return0;}POJ2488-AKnight'sJourney【骑士游历】DescriptionBackground

Theknightisgettingboredofseeingthesameblackandwhitesquaresagainandagainandhasdecidedtomakeajourney

aroundtheworld.Wheneveraknightmoves,itistwosquaresinonedirectionandonesquareperpendiculartothis.Theworldofaknightisthechessboardheislivingon.Ourknightlivesonachessboardthathasasmallerareathanaregular8*8board,butitisstillrectangular.Canyouhelpthisadventurousknighttomaketravelplans?

Problem

Findapathsuchthattheknightvisitseverysquareonce.Theknightcanstartandendonanysquareoftheboard.InputTheinputbeginswithapositiveintegerninthefirstline.Thefollowinglinescontainntestcases.Eachtestcaseconsistsofasinglelinewithtwopositiveintegerspandq,suchthat1<=p*q<=26.Thisrepresentsap*qchessboard,wherepdescribeshowmanydifferentsquarenumbers1,...,pexist,qdescribeshowmanydifferentsquarelettersexist.ThesearethefirstqlettersoftheLatinalphabet:A,...OutputTheoutputforeveryscenariobeginswithalinecontaining"Scenario#i:",whereiisthenumberofthescenariostartingat1.Thenprintasinglelinecontainingthelexicographicallyfirstpaththatvisitsallsquaresofthechessboardwithknightmovesfollowedbyanemptyline.Thepathshouldbegivenonasinglelinebyconcatenatingthenamesofthevisitedsquares.Eachsquarenameconsistsofacapitalletterfollowedbyanumber.

Ifnosuchpathexist,youshouldoutputimpossibleonasingleline.SampleInput3112343SampleOutputScenario#1:A1Scenario#2:impossibleScenario#3:A1B3C1A2B4C2A3B1C3A4B2C4背景骑士厌倦了一次又一次地看到同样的黑白格子，于是决定去旅行。全世界.每当骑士移动，它是两个正方形在一个方向和一个正方形垂直于此。一个骑士的世界是棋盘，他是生活在。我们的骑士生活在棋盘上，它的面积比普通的8×8板还小，但它还是长方形的。你能帮助这个冒险的骑士做旅行计划吗？问题发现骑士访问每平方一次这样的路径。骑士可以开始和结束在任何一方的董事会。POJ2488-AKnight'sJourney【骑士游历】大致题意:给出一个国际棋盘的大小，判断马能否不重复的走过所有格，并记录下其中按字典序排列的第一种路径。经典的“骑士游历”问题，DFS即可棋盘上的哈密尔顿回路问题在44或55的缩小了的国际象棋棋盘上，马(Knight)不可能从某一格开始，跳过每个格子一次，并返回起点。POJ2488-Children'sDiningDescriptionUsuallychildreninkindergartenliketoquarrelwitheachother.Thissituationannoysthechild-carewomen.Forinstant,whendinertimecomes,afierceconflictmaybreakoutwhenacertaincoupleofchildrensittingsidebysidewhoarehostilewitheachother.Althoughtherearen'ttoomanychildrendiningatthesameroundtable,buttherelationshipof"enemy"or"friend"maybeverycomplex.Thechild-carewomendocomeacrossabigproblem.Nowitistimeforyoutohelpthemtofigureoutaproperarrangementofsitting,withwhichnotwo"enemy"childrenisadjacent.

Nowweassumethatthereare2*nchildrenwhositaroundabigtable,andthatnonehasmorethann-1"enemies".InputTheinputisconsistedofseveraltestblocks.Foreachblock,thefirstlinecontainstwointegersnandm(1<=n<=200,0<=m<=n(n-1)).Weusepositiveintegersfrom1to2*ntolabelthechildrendiningroundtable.Thenmlinesfollowed.Eachcontainspositiveintegersiandj(iisnotequaltoj,1<=i,j<=2*n),whichindicatethatchildiandchildjconsidereachotheras"enemy".Inainputblock,asamerelationshipisn'tgivenmorethanonce,whichmeansthatif"ij"hasbeengiven,"ji"willnotbegiven.

Therewillbeablanklinebetweeninputblocks.Andm=n=0indicatestheendofinputandthiscaseshouldn'tbeprocessed.OutputForeachtestblock,iftheproperarrangementexist,youshouldprintalinewithaproperone;otherwise,printalinewith"Nosolution!".SampleInput102212343612132435465641212131425263738484756576800SampleOutput12423116325416723458通常孩子在幼儿园喜欢吵架。这种情况让照顾孩子的妇女。在用餐时间到来之际，当一对夫妇肩并肩坐在一起时，一场激烈的冲突可能爆发。虽然没有太多的孩子在同一个圆桌吃饭，但“敌人”或“朋友”的关系可能是非常复杂的。照顾孩子的女人遇到一个大问题。现在是你帮助他们想出一个适当的坐姿安排的时候了，没有两个“敌人”孩子在旁边。现在我们假设有2个**的孩子围坐在一张大桌子旁边，没有一个孩子有超过1个“敌人”。POJ2488-Children'sDining题意:

有2*N个小朋友要坐在一张圆桌上吃饭,但是每两个小朋友之间存在一种关系,即敌人或者朋友,然后需要让你安排一个座位次序,使得相邻的两个小朋友都不会是敌人.假设每个人最多有N-1个敌人.如果没有输出"Nosolution!".思路:

如果按照题意直接建图,每个点表示一个小朋友,小朋友之间的敌对关系表示两个点之间有边.问题是求小朋友围着桌子的座次就是求图中的一个环,但是要求这个环不能包含所给出的每条边,所有没给出的边却是可以用的,也就是说本题实际上是在上面建的图的反图上求解一个环,使得该环包含所有点.包含所有点的环一定是一条哈密顿回路,所以题目就是求所给图的反图上的一条哈密顿回路.题目中给了一个特殊条件,就是一共有2*N个小朋友,但是每个人最多有N-1个敌人,也就是说,每个小朋友可以选择坐在身边的小朋友数大于n+1,这就意味着在建立的反图中,每个点的度数大于N+1,由定理可知,此图一定存在哈密顿回路,所以答案不会出现"Nosolution!",即直接构造哈密顿回路就可以了.参考文档/problem?id=2488/problem?id=2438/inuyasha1027/article/details/40892407/Ash-ly/p/5452615.html/lyy289065406/article/details/664766647货郎担/旅行推销员(TSP)问题：货郎担问题设有n个城市,城市之间有道路,道路的长度均大于或等于0,可能是∞(城市之间无交通线)。一个旅行商从某个城市出发,要经过每个城市一次且仅一次,最后回到出发的城市,问如何才能使他所走的路线最短？这就是著名的旅行商问题或货郎担问题。这个问题可化归为图论问题。货郎担/旅行推销员(TSP)问题：设G=<V,E,W>为一个n阶完全带权图Kn,各边的权非负,且有些边的权可能为∞。求G中一条最短的哈密顿回路,这就是货郎担问题的数学模型。在一个赋权的完全图中，找出一个具有最小权的H_回路，也即回路边的权之和最小对该赋权图上的边，满足三角不等式（距离不等式）W(a,b)W(a,c)+W(c,b)例下图(a)为完全带权图K4,求出其不同的哈密顿回路,并指出最短的哈密顿回路。由货郎担问题中不同哈密顿回路的含义可知:求哈密顿回路可从任何顶点出发。下面先求出从a点出发,考虑顺时针及逆时针顺序的不同的哈密顿回路。