4.4_欧拉图与汉密尔顿图

欧拉图与汉密尔顿图主要内容欧拉图欧拉图的判定汉密尔顿图汉密尔顿图的必要条件汉密尔顿图的充分条件学习要点与基本要求实例分析问题的提出哥尼斯堡七桥问题欧拉图及相关概念定义7-4.1给定无孤立结点图G，欧拉路：经过图中每边一次而且仅一次的一条路。欧拉回路：经过图中每边一次而且仅一次的一条回路.欧拉图：含有欧拉回路的图。半欧拉图：含有欧拉路的图。几点说明：(1)上述定义对无向图和有向图都适用.(2)规定平凡图为欧拉图.(3)欧拉路是迹,欧拉回路是封闭的迹.(4)环不影响图的欧拉性.举例下列图中，哪些是欧拉图？哪些是半欧拉图？在非（半）欧拉图中至少增加几条边才能成为欧拉图？欧拉图半欧拉图非（半）欧拉图欧拉图半欧拉图非（半）欧拉图欧拉图的判别定理7-4.1无向图G具有一条欧拉路，当且仅当G是连通的，且有零个或两个奇数度结点。证明必要性。设G具有欧拉路P=v0e1v1e2v2…eiviei+1…ekvk，其中结点可能重复出现，但边不重复且包括了G中的所有边。因此P经过图G中的所有结点，所以G是连通的。对任意非端点的结点vi，在欧拉路中每当vi出现一次，必然关联两条边，vi所关联的所有边必然都出现在欧拉路中一次而且仅一次，所以deg(vi)为偶数。定理7-4.1的证明对于端点，若v0=vk，则d(v0)为偶数，即G中奇数度结点数为零，这时G是欧拉图。若v0≠vk，则d(v0)为奇数，d(vk)为奇数，因此G中就有两个奇数度结点，这时G是半欧拉图。充分性。若图G连通，有零个或两个奇数度结点，用如下方法构造一条欧拉路：(1)若有两个奇数度结点，则从其中一个结点开始构造一条迹，即从v0出发经关联边e1进入v1，若deg(v1)为偶数，则必可由v1经关联边e2进入v2，依此类推，每边仅取一次。定理7-4.1的证明由于G是连通的，故必可到达另一个奇数度结点停止，得到一条迹L1：v0e1v1e2v2…eiviei+1…ekvk。若G中没有奇数度结点，则从任意结点v0出发，用上述方法必可回到v0，得到一条闭迹L1。(2)若L1经过G的所有边，则L1就是欧拉路。(3)否则，在G中删掉L1中的边，得到G’，则G’中每个结点的度必为偶数。这是因为：如果L1是不封闭的，则对每个非端点vi，L1包含了与vi关联的所有边中的偶数条，即deg’(vi)=deg(vi)-L1中与vi关联的边数，因为deg(vi)为偶数，所以deg’(vi)为偶数，而deg’(v0)=deg(v0)-1为偶数，定理7-4.1的证明deg’(vk)=deg(vk)-1为偶数.如果L1是封闭的，同样G’中每个结点的度为偶数。因为G是连通的，所以L1与G’至少有一个结点vj是重合的，则按照上面的方法可以在G’中从vj出发构造一条闭迹L2。(4)若L1与L2组合在一起恰好包含了G中的所有边，则得到欧拉路。否则重复(3)得到闭迹L3，依次类推直到得到一条欧拉路。欧拉路的演示定理7-4.1的推论推论无向图G具有一条欧拉回路，当且仅当G是连通的，并且所有结点度数全为偶数。思考题：无向连通图含G有m个奇数度结点，问（1）至少加入多少条边才能使图G变为欧拉图？（2）至少加入多少条边才能使图G变为半欧拉图？欧拉图的应用：一笔画问题七桥问题的解：没有满足要求的路线。一笔画问题的判别：图可一笔画有两种情况：(1)从图G中某一结点出发，经过图G的每一边一次仅一次到达另一结点。——欧拉路(2)从图G中某一结点出发，经过图G的每一边一次仅一次再回到该结点。——欧拉回路实例例下图可以一笔画吗？请找出一种画法。有向图中的欧拉路与欧拉回路定义7-4.2给定有向图G，通过图中每边一次且仅一次的一条单向路（回路），称作单向欧拉路（回路）。定理7-4.2有向图G具有一条单向欧拉回路，当且仅当是连通的，且每个结点入度等于出度。一个有向图G具有单向欧拉路，当且仅当它是连通的，而且除两个结点外，每个结点的入度等于出度，但这两个结点中，一个结点的入度比出度大，另一个结点的入度比出度小1。应用举例例1计算机鼓轮的设计。导体，1绝缘体，0设有旋转鼓轮其表面被分成24个部分，如左图所示。其中每部分分别用绝缘体或导体组成，其输出信号分别为0和1。有4个触点，鼓轮每旋转1个部分，触点输出一个4位二进制数，如图所示的位置输出：1101问鼓轮上16个部分怎样安排导体及绝缘体，才能使鼓轮每旋转一个部分，四个触点能得到一组不同的四位二进制信息。设一个8结点的有向图，其结点分别记为3位二进制数{000,001,010,011,100,101,110,111}，设ai∈{0,1}，从结点a1a2a3可引出两条边，其终点分别是a2a30和a2a31。按照这种方法，该有向图共有16条边，从结点a1a2a3到结点a2a3a4的有向边标记为a1a2a3a4，而结点a2a3a4到结点a3a4a5的有向边标记为a2a3a4a5。所以两条邻接边中的第一条边的后3位与第二条边的前三位相同。如图所示由于16条边被标记成不同的四位二进制，因此转动鼓轮得到16个不同位置触点上的二进制数，即对应图的一条欧拉回路。因为图中每个结点的入度和出度都等于2，所以必然存在一条欧拉回路,如e0e1e2e4e9e3e6e13e10e5e11e7e15e14e12e8e0e1e2e4e9e3e6e13e10e5e11e7e15e14e12e80000100110101111000所以于此欧拉对应的二进制序列为0000100110101111Hamilton图的提出问题1：在一个十二面体中能否找到一条回路，使它含有这个图的所有结点？问题2：把每个结点看成一个城市，联结两个结点的边看成是交通线，能否找到旅行路线，沿着交通线经过每个城市恰好一次，再回到原来的出发地？汉密尔顿图的定义定义7-4.3给定图G，哈密顿路:经过图中所有顶点一次且仅一次的路.哈密顿回路:经过图中所有顶点一次且仅一次的回路.哈密顿图:具有汉密尔顿回路的图.半哈密顿图:具有汉密尔顿路而无汉密尔顿回路的图.几点说明：1.平凡图是汉密尔顿图.2.汉密尔顿路是通路，汉密尔顿回路是圈.3.环与平行边不影响图的哈密顿性.实例例下图中，哪些是汉密尔顿图，哪些是半汉密尔顿图。解(1),(2)是哈密顿图;(3)是半哈密顿图.(4)既不是哈密顿图,也不是半哈密顿图哈密顿图的必要条件定理7-4.3若图G=V,E是哈密顿图,则对于任意SV且S,均有W(GS)|S|成立.其中W(GS)是G-S的连通分支个数。证设C为G中一条哈密顿回路,有W(CS)|S|.又因为CG,而且C-S是G-S的一个生成子图，故W(GS)W(CS)|S|.如右图，S={v2,v6}，则W(GS)=4|S|，所以不是哈密顿图v1v2v3v4v5v6定理7-4.3的推论推论设图G=V,E是半哈密顿图,则对于任意SV且V1,均有W(GS)|S|+1成立.几点说明：1.定理7-4.3中的条件是哈密顿图的必要条件,但不是充分条件.2.可利用该定理判断某些图不是哈密顿图.3.由定理可知,Kr,s当sr+1时不是哈密顿图.当r2时,Kr,r是哈密顿图,而Kr,r+1是半哈密顿图.实例例下面的图是哈密顿图吗？为什么？不是哈密顿图。取S={v1,v4}，则W(G-S)=3|S|实例例设G为n阶无向连通简单图,若G中有割点或桥,则G不是哈密顿图.证(1)设v为割点,则W(Gv)2|{v}|=1.根据定理,G不是哈密顿图.(2)若G是K2(K2有桥),它显然不是哈密顿图.除K2外,其他的有桥连通图均有割点.由(1),得证G不是哈密顿图.半哈密顿图的充分条件定理7-4.4设G是n阶简单图,如果G中每一对结点度数之和大于等于n1,则G中存在哈密顿路.证明(1)先证G是连通的。设W(G)=r，r≥2，在r个分图中任取2个，分别记为G1=V1,E1,G2=V2,E2，则有|V1|+|V2|≤n，在V1中任取一结点v1，在V2中任取一结点v2，则d(v1)≤|V1|-1，d(v2)≤|V2|-1，所以d(v1)+d(v2)=|V1|+|V2|-2n-1，与题设矛盾。定理7-4.4的证明(2)构造一条通路，证明它是哈密顿路。在G中构造一条极长通路，假设长度为p-1，结点序列为v1,v2,v3,…,vp，则v1和vp的所有邻接点都只在这条通路上。1)若p=n，则这条通路就是哈密顿路。2)若pn，下面证明存在一条包含结点v1,v2,v3,…,vp的回路C。a)若v1邻接于vp，则v1,v2,v3,…,vp,v1即为回路。定理7-4.4的证明b)若v1不邻接于vp，设d(v1)=k，v1的邻接集(v1)={vl,vm,…,vj,…,vt}，2≤l,m,…,j,t≤p-1，|(v1)|=k那么vp必邻接于vl-1,vm-1,…,vj-1,…,vt-1中之一，因为如果vp不邻接于vl-1,vm-1,…,vj-1,…,vt-1中任何一个，则d(vp)≤p-1-k，所以d(v1)+d(vp)≤p-1n-1，与已知矛盾，所以这种情况不存在。不妨设vp邻接于vj-1，则v1v2v3…vj-1vpvp-1…vjv1是包含v1,v2,v3,…,vp的回路。定理7-4.4的证明因为G是连通的，所以G中必有一个不属于回路C的结点vx与v1v2v3,…vp中的某一结点vk邻接，从而得到一条长度为p的路。重复此过程，直到路的长度为n-1。v2vj-1vjvk-1v1vkvxvpv2vj-1vjvk-1vkvxv1vp定理7-4.4的说明定理中的条件是存在哈密顿路的充分条件,但不是必要条件.如六边形G，任何两个结点度之和是46-1，但在G中有一条哈密顿路。实例例题1考虑在七天内安排七门课程的考试，使得同一位教师所任的两门课程考试不排在接连的两天中，试证如果没有教师担任多于四门课程，则符合上述要求的考试安排总是可能的。证设G是含有7个结点的简单图，每个结点对应一门课程考试；结点间的连线表示两个结点表示的课程由不同的教师担任。由于每个教师担任不多于四门课程，则图G中每个结点的度至少为3，因此任意两结点度之和大于等于6，故G中存在哈密顿路，它对应一个7门课程的考试安排。哈密顿图的充分条件定理7-4.5设G是具有n个结点的简单图，如果G中每一对结点度数之和大于等于n，则在G中存在一条哈密顿回路。证明G中必存在哈密顿路，设为v1,v2,v3,…,vn。设d(v1)=k，v1的邻接集(v1)={vl,vm,…,vj,…,vt}，则vn必邻接于vl-1,vm-1,…,vj-1,…,vt-1中之一，设为vj-1。则v1v2v3…vj-1vnvn-1…vjv1是哈密顿回路。v2vj-1vjv1vn实例例某次国际会议8人参加，已知每人至少与其余7人中的4人有共同语言，问服务员能否将他们安排在同一张圆桌就座，使得每个人都能与两边的人交谈？解作无向图G=V,E,其中V={v|v为与会者}，E={(u,v)|u,vV,u与v有共同语言,且uv}.所以G为简单图.根据条件,vV,d(v)4，则u,vV,有d(u)+d(v)8.由定理可知G为哈密顿图.在G中找一条哈密顿回路C，它对应一种满足要求的安排座位方案.图G的闭包定义7-4.4给定图G=V,E有n个结点，若vi和vj是G的不相邻结点，且满足d(vi)+d(vj)n，则令G’=G+(vi,vj)，对G’再重复上述过程，直至不再有这样的结点对为止，最终得到的图称为G的闭合图，记为C(G)。实例哈密顿图的充要条件定理7-4.6当且仅当一个简单图的闭包是哈密顿图时这个简单图是哈密顿图。注意：判断某图是否为哈密顿图至今还是一个难题。判断是否是哈密顿图的可行方法(1)观察出一条哈密顿回路。例如右图(周游世界问题)中红边给出一条哈密顿回路,故它是哈密顿图.注意,此图不满足定理的条件.(2)满足充分条件。例如当n3时,Kn中任何两个不同的顶点u,v,均有d(u)+d(v)=2(n1)