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)

1 / 47
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功