欧拉图与哈密顿图.ppt

第十五章 欧拉图与哈密顿图,第1节 欧拉图,第2节 哈密顿图,第3节 带权图与货郎担问题,第1节 欧拉图,一、欧拉通路、欧拉回路、欧拉图、半欧拉图的定义,二、欧拉图的判别定理,三、欧拉图的简单应用,问题的提出,A,B,C,D,哥尼斯堡七桥问题,A,B,C,D,哥尼斯堡镇多重图模型,定义15.1 通过图（无向图或有向图）中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路;通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路；具有欧拉回路的图称为欧拉图，具有欧拉通路而无欧拉回路的图称为半欧拉图.,一、欧拉通路、欧拉回路、欧拉图、半欧拉图的定义,从定义不难看出:欧拉通路是图中经过所有边的简单的生成通路（经过所有顶点的通路称为生成通路），欧拉回路是经过所有边的简单的生成回路。,在这里做个规定:平凡图是欧拉图.,图15.1,例1 下列各图中 是否有欧拉回路、欧位通路？,解：e1 e2 e3 e4 e5 为(1)中的欧拉回路，所以(1)图为欧拉图.,e1 e2 e3 e4 e5 为(2)中的一条欧拉通路，但图中不存在欧拉回路（为什么？），所以(2)为半欧拉图。,（3）中既没有欧拉回路也没有欧拉通路(为什么？)，所以(3)不是欧拉图，也不是半欧拉图。,e1 e2 e3 e4为(4)图中的欧拉回路，所以(4)图为欧拉图.,(5),(6)图中都既没有欧拉回路，也没有欧拉通路（为什么？）,定理15.1 无向图G是欧拉图当且仅当G是连通图，且G中没有奇度顶点。,二、欧拉图的判别定理,证明要点：当图G具有欧拉回路时，图G中每个顶点在欧拉回路中出现一次就获得2度，所以每个顶点的度数是偶数.反过来当连通图G中的顶点度数都是偶数时，则 G中必有简单回路.G中包含边数最多的简单回路就是欧拉回路.,必要性.,因为G为欧拉图，所以G中存在欧拉回路，设C为G中任意一条欧拉回路，vi,vj V，vi,vj都在C上，因而vi,vj 连通，所以G为连通图.又viV，vi在C上每出现一次获得2度，若出现k次就获得2k 度，即d(vi)=2k.所以G中无奇度顶点.,证 若G是平凡图，结论显然成立.下面设G为非平凡图，设G是 m 条边的 n 阶无向图,并设G的顶点集 V=v1,v2,vn.,由于G为非平凡的连通图可知，G中边数m1.对 m 作归纳法。(1)m=1时，由G的连通性及无奇度顶点可知，G只能是一个环，因而G为欧拉图。(2)设mk(k1)时结论成立，要证明m=k+1时，结论也成立。,充分性.,由G的连通性及无奇度顶点可知，(G)2.类似于例14.8，用扩大路径法可以证明G中存在长度大于或等于3的圈，设C为G中一个圈，删除C上的全部边，得G的生成子图G，设G有s个连通分支 每个连通分支至多有k条边，且无奇度顶点，并且设Gi与C的公共顶点为，i=1,2,s.由归纳假设可知，都是欧拉图，因而都存在欧拉回路Ci，i=1,2,s.,由定理15.1立刻可知，图15.1中（1）是欧拉图，而（2）、（3）都有奇度顶点，因而它们都不是欧拉图.,最后将C还原(即将删除的边重新加上),并从C上的某顶点vr开始行遍，每遇到，就行遍Gi中的欧拉回路Ci，i=1,2,s，最后回到 vr，得回路 此回路经过G中每条边一次且仅一次并行遍G中所有顶点，因而它是G中的欧拉回路,故G为欧拉图.,(演示),定理15.2 无向图G是半欧拉图当且仅当G是连通的，且G中恰有两个奇度顶点.,证:必要性.设G是 m 条边的 n 阶无向图，因为G为半欧拉图，因而G中存在欧拉通路（但不存在欧拉回路），设 为G中一条欧拉通路，若v不在的端点出现，显然d(v)为偶数，若v在端点出现过，则d(v)为奇数，因为只有两个端点且不同，因而G中只有两个奇数顶点.另外，G的连通性是显然的.,设G的两个奇度顶点分别为u0和v0，对G加新边（u0,v0），得G=G(u0,v0)，则G 是连通且无奇度顶点的图，由定理15.1可知，G 为欧拉图，因而存在欧拉回路C，而C=C(u0,v0)为G中一条欧拉通路，所以G为半欧拉图.,由定理15.2立即可知，图15.1中（2）是半欧拉图，但（3）不是半欧拉图。,充分性.,定理15.3 有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度都等于出度.,本定理的证明类似于定理15.1.,定理15.4 有向图D是半欧拉图当且仅当D是单向连通的，且D中恰有两个奇度顶点，其中一个的入度比出度大1，另一个的出度比入度大1，而其余顶点的入度都等于出度.,由定理15.3和15.4立即可知，图15.1中所示3个有向图中只有（4）是欧拉图，没有半欧拉图.,图15.1,图15.3,由定理15.1立即可知，图15.3(1)图为欧拉图.,本图既可以看成圈 之并(为清晰起见，将4个圈画在(2)中)，也可看成圈与圈 之并(两个圈画在(3)中)。将(1)分解成若干个边不重的圈的并不是(1)图特有的性质，任何欧拉图都有这个性质。,定理15.5 G是非平凡的欧拉图当且仅当G是连通的且为若干个边不重的圈的并.,本定理的证明可用归纳法.,例15.1 设G是非平凡的且非环的欧拉图，证明：,（2）对于G中任意两个不同顶点u,v，都存在简单回路C含 u 和 v.,（1）(G)2.,证（1）由定理15.5可知，存在圈C，e 在C中，因而 故 e 不是桥。由 e 的任意性(G)2，即G是2边-连通图。,（2）由G的连通性可知，u,v之间必存在路径1，设G=G-E(1)，则在G中u与v还必连通，否则，u 与 v 必处于G的不同的连通分支中，这说明在1上存在G中的桥，这与（1）矛盾。于是在G中存在 u 到 v 的路径2，显然1与2边不重，这说明 u,v 处于12形成的简单回路上,应用1一笔画问题（即在画图的过程中要求不重复且笔尖一直不离开纸面）,例 下列图形能否一笔画出？,注：欧拉图及具有欧拉通路的图都能一笔画出.,三、欧拉图的简单应用,应用2中国邮递员问题（最短邮路问题）邮递员发送邮件时，要走遍他负责投递范围内的街道，然后返回邮局.问他按怎样的路线走最短？,将投递范围内的每条街道用边表示，邮局及街道交叉口用点表示，得到一个图G，邮路问题便转成了图的问题了.,想一想：如果不是欧拉图，该怎么走呢？,?,如果图G是一个欧拉图，则G的任意一条欧拉回路都是最短路线.,邮局在V1处,邮局在V2处,第2节 哈密顿图,一、哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图的定义,二、哈密顿图与半哈密顿图的 一些必要与充分条件,1859年，数学家哈密顿(Hamilton)提出一个问题：能否在正十二面体上求一条初级回路，使它含图中所有顶点？他形象地将每个顶点比作一个城市，连接两个顶点之间的边看作城市之间的交通线.于是原始问题就变成了所谓的周游世界问题：能否从某个城市出发沿交通线经过每个城市一次并且仅一次，最后回到出发点？哈密顿自己做了肯定的回答.后人为了纪念这位数学家，将经过图中每个顶点一次且仅一次的回路称为哈密顿回路，将有这种回路的图称为哈密顿图.,哈密顿图名称的来历:,图示：,“周游世界”智力题,哈密顿图,(b),(a),定义15.2 经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为哈密顿通路；经过图中所有顶点一次且仅一次的回路称为哈密顿回路；具有哈密顿回路的图称为哈密顿图；具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图.平凡图是哈密顿图.,一、哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图的定义,图15.1,例1 下列各图中 是否有哈密顿回路、哈密顿通路？,图15.1中所示的三个无向图都有哈密顿回路，所以都是哈密顿图.,有向图中，（4）具有哈密顿回路，因而它是哈密顿图.,（5）只有哈密顿通路，但无哈密顿回路，因而它是半哈密顿图.,（6）中既无哈密顿回路，也没有哈密顿通路，因而不是哈密顿图，也不是半哈密顿图.,例2 下列各图中 是否有哈密顿回路、哈密顿通路？,(1)带1度顶点的图无哈密顿回路；(2)若图中有2度顶点，则关联这个顶点的两条边属于任意一条哈密顿回路；(3)当构造哈密顿回路且该回路经过某一顶点时除了回路所用的两条边，不用再考虑这个顶点关联的其它边；(4)哈密顿回路不能包含更小的回路；(5)若图中某些必须出现在哈密顿回路中的边已构成回，而图中尚有不在该回路中的点，则此图不是哈密顿图。,说明：,从定义可以看出，哈密顿通路是图中生成的初级通路，而哈密顿回路是生成的初级回路.判断一个图是否为哈密顿图，就是判断能否将图中所有顶点都放置在一个初级回路（圈）上，但这不是一件易事.与判断一个图是否为欧拉图不一样，到目前为止，人们还没有找到哈密顿图简单的充分必要条件.下面给出的定理都是哈密顿通路（回路）的必要条件或充分条件.,二、哈密顿图与半哈密顿图的 一些必要与充分条件,定理15.6设无向图G=是哈密顿图，对于任意 均有 其中，p(GV1)为 G-V1 的连通分支数.,必要条件,证：设C为G中任意一条哈密顿回路，易知，当V1中顶点在C上均不相邻时，p(C-V1)达到最大值|V1|，而当V1中顶点在C上有彼此相邻的情况时，均有 所以有 而C是G的生成子图，所以，有,可验证彼得松图满足定理中的条件，但它不是哈密顿图.,当然，若一个图不满足定理中的条件，它一定不是哈密顿图.,定理15.6的条件是哈密顿图的必要条件，但不是充分条件.常用它判断一个图不是哈密顿图。,推论 设无向图G=是半哈密顿图，对于任意的 均有,证:设P是G中起于 u 终于 v 的哈密顿通路，令G=G(u,v)（在G的顶点 u,v 之间加新边），易知G为哈密顿图，由定理15.6可知，而有,例15.3 在图15.6中给出的三个图都是二部图.它们中的那些是哈密顿图？哪些是半哈密顿图？为什么？,图15.6,解 在(1)中，易知互补顶点子集 设此二部图为G1，则由定理15.6及其推论可知，G1不是哈密顿图，也不是半哈密顿图.,设(2)中图为G2，则 其中 易知，由定理15.6可知，G2不是哈密顿图，但G2是半哈密顿图，其实，为G2中一条哈密顿通路.,设(3)中图为G3.其中 G3中存在哈密顿回路（演示），如 所以G3是哈密顿图.,通过本例，清楚地看出，哈密顿通路是经过图中所有顶点的一条初级通路，而哈密顿回路是经过图中所有顶点的初级回路.,例15.4 设G是 n 阶无向连通图.证明：若G中有割点或桥，则G不是哈密顿图.,对于二部图还能得出下面结论：,一般情况下，设二部图G=，,由定理15.6及其推论可以得出下面结论：,（2）若G是半哈密顿图，则|V2|=|V1|+1.,（3）若|V2|V1|+2，则G不是哈密顿图，也不是半哈密顿图.,（1）若G是哈密顿图，则|V1|=|V2|.,定理15.7 设G是n阶无向简单图，若对于G中任意不相邻的顶点 vi,vj，均有 d(vi)+d(vj)n1(15.1)则G中存在哈密顿通路.,充分条件,证:首先证明G是连通图.否则G至少有两个连通分支，设G1,G2是阶数为 n1,n2 的两个连通分支，设v1V(G1)，v2V(G2)，因为G是简单图，所以 这与（15.1）矛盾，所以G必为连通图.,下面证G中存在哈密顿通路.设 为G中用“扩大路径法”得到的“极大路径”，即的始点v1与终点vl不与外的顶点相邻.显然有ln.,(2)若ln，这说明不是哈密顿通路，即G中还存在着外的顶点。但可以证明G中存在过上所有顶点的圈.,(a)若v1与vl相邻，即(v1,vl)E(G)，则(v1,vl)为满足要求的圈.,(1)若 l=n，则为G中哈密顿通路.,(b)若v1与vl不相邻，设v1与上vi1=v2,vi2,vik相邻（k2，否则这与（15.1）矛盾），此时，vl至少与相邻的顶点 vi2-1,vi3-1,vik-1之一相邻（否则，设vl与vir-1相邻（2rk），见图15.7(1)所示.于是，回路C=v1 v2 vir-1 vl vl-1viivir v1过上的所有顶点.,(c)下面证明存在比更长的路径.因为 l n，所以C外还有顶点，由G的连通性可知，存在vl+1V(G)-V(C)与C上某顶点vt相邻，见图15.7(2)所示.删除边（vt-1,vt）得路径 比长度大1，对上的顶点重新排序,使其成为 对重复(a)(c)，在有限步内一定得到G的哈密顿通路.,图15.7,推论 设G为n(n3)阶无向简单图，若对于G中任意两个不相邻的顶点 vi,vj，均有 d(vi)+d(vj)n(15.2)则G中存在哈密顿回路，从而G为哈密顿图.,证:由定理15.7可知，G中存在哈密顿通路，设=v1v2vn为G中一条哈密顿通路，若v1与vn相邻，设边 e=(v1,vn)，则e为G中哈密顿回路.若v1与vn不相邻，应用（15.2），同定理15.7证明中的（2）类似，可证明存在过上各顶点的圈，此圈即为G中的哈密顿回路.,注：完全图Kn(n3)中有哈密顿回路；简单连通图GV，E，V 3，若对任意vi V,均有 d(vj)n2，则G为哈密顿图.,定理15.8 设 u,v为n阶无向图G中两个不相邻的顶点，且d(u)+d(v)n，则G为哈密顿图当且仅当G(u,v)为哈密顿图(u,v)是加的新边).,证明：略.,例15.5 在某此国际会议的预备会议中，共有8人参加，他们来自不同的国家.已知他们中任何两个无共同语言的人中的每一个，与其余有共同语言的人数之和大于或等于8，问能否将这8个人排在圆桌旁，使其任何人都能与两边的人交谈.,解:设8个人分别为v1,v2,v8，作无向简单图G=，其中V=v1,v2,v8，vi,vjV，且ij，若vi与vj由共同语言，就在vi,vj之间连无向边（vi,vj），由此组成边集合E，则G为8阶无向简单图，viV，d(vi)为与vi有共同语言的人数。由已知条件可知，vi,vjV且ij，均有d(vi)+d(vj)8.由定理15.7的推论可知，G中存在哈密顿回路，设C=vi1vi2vi8vi1为G中一条哈密顿回路，按这条回路的顺序安排座次即可.,从此例更可以看出，哈密顿图是能将图中所有顶点都能安排在某个初级回路上的图.,定理15.9 若 D为n(n2)阶竞赛图，则 D中具有哈密顿通路.,证:对n作归纳法.n=2时，D的基图为K2，结论成立.设n=k时结论成立.现在设 n=k+1.设V(D)=v1,v2,vk,vk+1.,令D1=D-vk+1,易知D1为k阶竞赛图,由归纳假设可知,D1存在哈密顿通路，设1=v1v2vk为其中一条.下面证明vk+1可扩到1中去若存在vr(1rk),有E(D),i=1,2,r-1，而E(D),见图15.8(1)所示，则=v1v2vr-1vk+1vrvk为D中哈密顿通路.否则，i1,2,k，均有E(D)，见图15.8(2)所示，则=为D中哈密顿通路.,图 15.8,例15.6 图15.9所示的三个图中哪些是哈密顿图？哪些是半哈密顿图？,图 15.9,解 在(1)中，存在哈密顿回路，所以(1)为哈密顿图.在(2)中，取V1=a,b,c,d,e，从图中删除V1得7个连通分支，由定理15.6和推论可知，(2)不是哈密顿图，也不是半哈密顿图.在(3)中，取V1=b,e,h，从图中删除V1得4个连通分支，由定理15.6可知，它不是哈密顿图.但(3)中存在哈密顿通路，所以(3)是半哈密顿图.,从以上的讨论可知，判断给定图是否为哈密顿图是个难题.如果在图中能找出哈密顿回路，或满足某充分性定理的条件，则该图为哈密顿图，但这样的定理是不多的.另外，人们可根据哈密顿图的某些必要条件判断某些图不是哈密顿图.,第3节 带权图与货郎担问题,一、带权图,二、货郎担问题,定义15.3 给定图GV，E图（G为无向图或有向图），设W：ER（R为实数集），对G中任意的边e=(vi,vj)（G为有向图时，e=），设W(e)=wij，称实数wij为边e上的权，并将wij标注在边e上，称G为带权图，并记作GV，E，W。,一、带权图,设，称 为 的权，并记作W(G),即,设有n个城市，城市之间均有道路，道路的长度均大于或等于0，可能是（对应关联的城市之间无交通线）。一个旅行商从某个城市出发，要经过每个城市一次且仅一次，最后回到出发的城市，问他如何走才能使他走的路线最短？这就是著名的旅行商问题或货郎担问题。,二、货郎担问题,这个问题可化归为如下的图论问题。,设G=，为一个n阶完全带权图Kn，各边的权非负，且有的边的权可能为。求G中一条最短的哈密顿回路，这就是货郎担问题的数学模型。,在讨论货郎担问题之前，首先应该弄清楚，在此问题中不同哈密顿回路的含义。将图中生成圈看成一个哈密顿回路，即不考虑始点（终点）的区别以及顺时针行遍与逆时针行遍的区别。,货郎担问题的数学模型,解 由于货郎担问题中不同哈密顿回路的含义可知，求哈密顿回路从任何顶点出发都可以。下面先求出从a点出发，考虑顺时针与逆时针顺序的不同的哈密顿回路。C1=a b c d aC2=a b d c aC3=a c b d aC4=a c d b aC5=a d b c aC6=a d c b a若不考虑顺（逆）时针顺序，则C1=C6，以C1为代表，W(C1)=8；C2=C4，以C2为代表，W(C2)=10；C3=C5，以C3为代表，W(C3)=12.经过比较可知，C1是最短的哈密顿回路。,例15.7 图(1)为4阶完全带权图K4。求出它的不同的哈密顿回路，并指出最短的哈密顿回路。,由例15.7的分析可知：n阶完全带权图中共存在 种不同的哈密顿回路,经过比较，可找出最短哈密顿回路。n=4时，有3种不同哈密顿回路，n=5时有12种，n=6时，有60种，n=7时，有360种，n=10时，有59!=1 814 400种，由此可见货郎担问题的计算量是相当大的。对于货郎担问题，人们一方面还在寻找好的算法，另一方面也在寻找各种近似算法。,作业,P303.,