离散数学-第6章-图论.ppt
《离散数学-第6章-图论.ppt》由会员分享,可在线阅读,更多相关《离散数学-第6章-图论.ppt(143页珍藏版)》请在三一办公上搜索。
1、1,离散数学,西安交通大学电子与信息工程学院计算机系,2,离散数学,6.Euler图Euler图的定义 Euler图的理论,3,离散数学,6 Euler图Euler图产生的背景就是前面介绍的Konigsberg七桥问题,有了前面几节的知识后,我们可以讨论Euler图的解决方法了。定义1.Euler路 Euler 圈 Euler图 设 G(V,E)是连通的、无孤立点的图。(1)Euler路是一条简单路P,路P穿过图G中每条边一次且仅一次;(2)Euler圈是一条简单圈C,圈C穿过图G中每条边一次且仅一次;(3)含有Euler 圈的图G称为Euler图(简称为E-图)。,4,离散数学,注:这类通过
2、各边恰好一次的问题就是通常所说的一笔画问题(即笔不离纸,线不重复)。定理1.(Euler定理)设 G(V,E)是无孤立点的无向图。那么,G是Euler图 G是连通的且G中无奇结点。注:G中无奇结点即是G中每个结点都是偶结点。证.先证必要性):(采用蹦圈法)设C是G的一条Euler圈。则(1)图G是连通的:首先,由于图G中无孤立点,所以图G中的每个结点都有一些边与之关联,而Euler圈C包含了图G中的每一条边,于是圈C在通过各边的同时必通过图G中每个结点。因而图G中每个结点都在Euler圈C上。,5,离散数学,因此,图G中任何两结点,沿着Euler圈C可相互到达,故图G是连通的。(2)图G中无奇
3、结点:其次,当圈C穿过某结点时,必从一边进,从另一边出,因此给该结点度数的贡献是2;尽管圈C可能会多次穿过某些结点,但由上述原因和Euler圈C仅穿过每条边一次(C是Euler圈)及每个结点都在圈C上可知:圈C穿过某结点k次,就给该结点的度数贡献2 k;因此,图G中每个结点的度数必全为偶数,即图G中无奇结点。再证充分性):(算法)No1.从任一结点出发,走成一个简单圈C;由于图G中每个结点都是偶结点(无奇结点),且图G连通,故图G中至少存在一个简单圈C。,6,离散数学,No2.若此简单圈C已是Euler圈,则此图G就是Euler图,算法结束(出口)。No3.(插圈)否则,图G中必还有若干条边不
4、属于圈C。由图G的连通性可知:必有圈C外的边ej与圈C上的结点vi相关联(vi称为接触点)。由于在图G中除去圈C(只删边,不删结点)后所得的子图G中,每个结点仍都是偶结点(因为在圈C上的结点,都是一边进,另一,7,离散数学,边出。因此圈C每穿过某结点一次,该结点的度数就被消耗掉2。故这些结点在删除圈C的边时,它们的度数都减少一个偶数)。由于图G中每个结点都仍是偶结点,于是从此结点vi出发,经过边ej 及子图G中的其它边,必可走出一个简单圈C,回到出发点vi。故圈C与圈C必由结点vi相连(如图1所示)。将圈C插入圈C中,形成一条新的更长的简单圈C:=CC,goto No2。由于图G中的边数是有限
5、的,故算法不可能无穷的进行下去,所以算法必定在有限步结束。最后一定能得到一个包括图G中所有边在其上的简单圈C,此圈C即是Euler圈。所以图G即为Euler图。注:美籍华人。著有离散数学基础(刘振宏译);条件:全是偶结点保证可走出简单圈;条件:连通性保证边(从而结点)可走完。,8,离散数学,例1.图G如图2所示。问图G是否为一Euler图?若是,试求出其Euler圈。解.由于图G中的六个结点全都是偶结点,并且图G显然是连通的,故根据上述Euler定理可知,图G为Euler图。按照算法,可求得图G中的Euler圈。具体步骤如下:在图中任意找一简单圈C(1,2,3,1)。发现还有7条边不在此圈,9
6、,离散数学,中,边(3,4)不在圈中且与圈中的结点3相关联。由结点3出发经过边(3,4)可得一简单圈C(3,4,5,3),将C插入C得到一个新的更长的简单圈 C(1,2,3,4,5,3,1)。此时仍有4条边不在圈C中,边(2,5)不在圈中且与圈中的结点2关联。由结点2出发经过边(2,5)又可得到一简单圈C(2,5,6,4,2),将C插入C又得到一条新的更长的简单圈C(1,2,5,6,4,2,3,4,5,3,1)。由于图G中所有的边都已在圈C中,故知此圈C为图G的一个Euler圈。例2哥尼斯堡七桥问题无解。解.在七桥图中(图3),由于每个结点均为奇结点,故由Euler定理的充要条件知,该图中不存
7、在经过每条边一次且仅一次的Euler圈。即七桥图不是Euler图。该问题无解。,10,离散数学,11,离散数学,推论.(Euler定理二)设 G(V,E)是无孤立点的无向图。那么,G中有Euler路 G是连通的且G中恰有两个奇结点。证.(采用增边删边法及抻路法)G中有Euler路P=(v1,v2,vk)G=G(v1,vk)中有Euler圈C=(v1,v2,vk,v1)G是连通的且G中全是偶结点(Euler定理)G是连通的且G中恰有两个奇结点v1,vk(删掉边e=(v1,vk)。,12,离散数学,定义2.割边(cut edge)设G(V,E)是无向图,eE。若W(Ge)W(G),则称边e为图G的
8、割边。这里W(G)表示图G中的连通支数。例3.图G如图5所示。G中的边e是割边。因为W(Ge)=21=W(G)。如何在恰有两个奇结点的连通图中寻找Euler路,可采用下面的算法。Fleury算法:寻找在两个奇结点间的一条Euler路的算法(1)从一个奇结点出发,每走一边标记一边;下次不走标记过的边;(2)在走边的过程中,除非没有其它选择时才走割边。,13,离散数学,例4.如图6所示的图G中有一条Euler路。解.在右图G中,恰有两个奇结点4和9,且图G是连通的,故按Euler定理二可知其存在着Euler路。利用Fleury算法,可求得其一条Euler路为P=(4,5,6,4,3,2,1,3,1
9、0,12,11,10,9,8,7,9)。,14,离散数学,定理2.设G(V,E)是无孤立点的有向图。那么,G是Euler图 G是(弱)连通的且G中每个结点的出度都等于进度。证.仿定理1的证明可证。只不过这里的Euler圈应是有向圈。定理3 设 G(V,E)是无孤立点的有向图。那么,G中有Euler路G是(弱)连通的且G中除两个结点外,其余每个结点的出度都等于进度。而这两个结点:一个结点的进度比出度大1(终点),另一个结点的出度比进度大1(起点)。证.仿定理1推论的证明可证。只不过这里的Euler路应是有向路。,15,离散数学,应用一:高效率计算机磁鼓的设计 计算机旋转磁鼓的表面被等分成2n个部
10、分,与n个电刷相接触。绝缘体(空白部分)不通电表示信号0;导体(阴影部分)通电表示信号1。从而n个电刷上就产生一n位二进制信号。我们的问题是:如何合理的按排磁鼓表面上的空白与阴影部分,使的磁鼓转动n个位置,就可读出2n个不同的二进制数。图7表示有三个电刷a,b,c的磁鼓,磁鼓表面被分成了八个部分。它旋转一周只能读出六个不同的二进制数:110,101,011,100,000,001。因此按排不合理。如何设计?我们考虑四个两位二进制数:00,01,10,11,16,离散数学,将其作为一图G的结点。对于图G的任二结点p1p2和q1q2,若p2=q1,则在它们之间连一条有向边(p1p2,q1q2),并
11、用三位二进制数p1p2q2标记该边。图G如图8所示。图8所示的图G是一有向图,它显然是(弱)连通的,并且每个结点的进度=出度=2,满足定理2中的条件,因此存在着Euler圈。其Euler圈为:(000,001,011,111,110,101,010,100,000)。两位重复此八个三位二进制数,上述Euler圈可用一个八位二进制序列:00011101 来表示。,17,离散数学,注:此序列称为De Bruijn序列。这一应用是由Good(1946)提出的。按此序列来设计磁鼓绝缘体及导体的位置最为合理(如图9所示),可以读出全部(八个)三位二进制数:000,001,011,111,110,101,
12、010,100。应用二:一笔画问题对于一个给定的图,究竟需要多少笔才能画成?这里只讨论连通图的一笔画问题。因为假若一个图是不连通的,则此图的笔画问题就可以归结成对各连通支笔画的讨论。,18,离散数学,连通图的笔画是由图中奇结点的个数决定的。本章2定理2已经证明过:图中奇结点的个数是偶数。所以奇结点是成对出现的,即为2k个。(1)当k=0,1时,此连通图是一笔画的;(2)当k1时,此连通图是k笔画的(更进一步地,存在着k 条边不重的路)。应用三:中国邮路问题一个邮递员,每次送信,领取邮件,由邮局出发,要走遍他所负责的投递范围内的每一条街道,完成投递任务后,再返回邮局。问题是:他应该沿着怎样的路线
13、走,使所走的总路程最短?,19,离散数学,这个问题抽象成图论语言就是:在给定的一个连通的带权图G=(V,E,w)(每条边上一个非负的权w(e)中,要求一个圈C,过每条边至少一次,并使圈C上的总权和w(C)达到最小。我们设图G的奇结点个数是2k(参见应用二)。这个问题的存在性是不容质疑的。我国山东师院的管梅谷教授于1962年首次研究并解决了上述问题。因此国际上将其称为中国邮路问题。(1)当k=0时(即无奇结点),这时G是Euler图,有Euler圈,设其为C。显然,若按Euler圈C走,每条边走且仅走一次,总权和w(C)显然是最小的;(2)当k1时(即有奇结点),我们解决问题的思路是给图G增加一
14、些重复边,使其变成无奇结点的多重图G。由于图G是连通的,故图G也是连通的。因而根据Euler定理可知,图G必有Euler圈,设其为C。,20,离散数学,设这些需重复的边的集合是E1(E1E),所增加的那些平行边的集合是E1=e e/eeE1,所获得新的带权多重图G=(V,E,w),其中E=EE1,并且eE1,w(e)=w(e)(这里e/e,eE1)(参见图10)。,21,离散数学,现在由于圈C穿过图G中的每条边一次且仅一次,因而C必定穿过图G中的每条边一次。而图G中各边的总权和w(E)是固定不变的,所以要使 Euler圈C取得最小权值w(C)平行边集E1取得最小权值w(E1)边集E1取得最小权
15、值w(E1)因而,中国邮路问题就转化为:在一给定的带权图G=(V,E,w)中,寻求这样一个边集E1E,其对应的平行边集为E1,使带权多重图G=GE1无奇结点,并使w(E1)=达到最小。我们称这样的边集E1是最优的。管梅谷教授解决此问题的思想方法我们总结为如下的定理。,22,离散数学,定理4.(管氏定理(1962)E1是最优的在图G的每个初级圈Ci上,都有E1的边(要重复的边)的长度之和不超过圈长的一半在图G的每个初级圈Ci上证.定理的证明主要基于以下两点:(1)当某条边重复k(k2)次后得到的图为Euler图时,则此边重复k-2次得到的图也一定为Euler图。(2)在图G的一个初级圈上,如果将
16、原来的重复边都删去,而在原来没有重复边的边上都加上一条重复边,那么图中各结点的度数改变0或2,所以,这种做法不会改变图G是Euler图的性质。由此可知:当Euler圈中重复边的长度之和超过此圈总长的一半时,如作上述改变,则,23,离散数学,重复边长度之和减少,而Euler圈的性质不变。例5.在图11所示的图G中寻求最优边集E1。解.在右图G中,恰有四个奇结点,可以验证:边集E1(v1,v2),(v3,v4)是最优的。图G中共有七个初级圈:C1(v1,v2,v3,v1),w(C1)=2+3+8=13,w(E1C1)=w(v1,v2)=26.5=1/213=1/2 w(C1);C2(v1,v2,v
17、4,v1),w(C2)=2+10+7=19,,24,离散数学,w(E1C2)=w(v1,v2)=29.5=1/219=1/2 w(C2);C3(v1,v3,v4,v1),w(C3)=8+4+7=19,w(E1C3)=w(v3,v4)=49.5=1/219=1/2 w(C3);C4(v2,v3,v4,v2),w(C4)=3+4+10=17,w(E1C4)=w(v3,v4)=48.5=1/217=1/2 w(C4);C5(v1,v2,v3,v4,v1),w(C5)=2+3+4+7=16,w(E1C5)=w(v1,v2)+w(v3,v4)=2+4=6 8=1/216=1/2 w(C5);C6(v1,
18、v2,v4,v3,v1),w(C6)=2+10+4+8=24,w(E1C6)=w(v1,v2)+w(v3,v4)=2+4=6 12=1/224=1/2 w(C6);C7(v1,v3,v2,v4,v1),w(C7)=8+3+10+7=28,,25,离散数学,w(E1C7)=w()=014=1/228=1/2 w(C7);但是,边集E2(v1,v4),(v2,v3)不是最优的。因为 w(E2C5)=7+3=108=1/216=1/2 w(C5);边集E3(v1,v3),(v2,v4)不是最优的。因为 w(E3C6)=8+10=1812=1/224=1/2 w(C6);w(E3C7)=8+10=18
19、14=1/228=1/2 w(C7)。注:在实际中应用管氏定理是很麻烦的。因为管氏定理要检查许多的初级圈,而且没有办法去系统的、逐个的检查,容易遗漏,因此一般不太实用。我们应另辟蹊径。(a)如果k=1,即带权图G中只有两个奇结点,(例如图12(a),则可先求出这两个奇结点间的最短路径,然后将最短路径中的每条边重复一次(如图12(b)所示),得到,26,离散数学,一个新的带权图G,它是一个Euler图(连通,无奇结点),G中的Euler圈必定是取得最小值的圈。最短路径中的边必定构成最优边集E1。这里:E1(v1,v2),(v2,v3);w(E1)=w(v1,v2)+w(v2,v3)=2+3=5。
20、,27,离散数学,(b)如果k2,即带权图G中有2k个奇结点,匈牙利的J.Edmods和Johnson提出了如下算法,比较有效。J.Edmods和Johnson算法(匈牙利算法(1973):No1.找出所有奇结点O=vi1,vi2,vi2k;No2.求出任一奇结点vit到另任一奇结点vis的最短路Pitis及其权w(Pitis);(采用Dijkstra算法)No3.以O为结点集作完全图K2k,并令其边(vit,vis)上的权w(vit,vis)=w(Pitis);No4.在带权图K2k中求出总权和最小的最大对集M*(图中不相邻边的集合的最大者,参见9偶图);(采用J.Edmods算法(1965
21、)No5.与M*中的每一杆(vit,vis)对应,图G中都有一条从,28,离散数学,奇结点vit到奇结点vis的最短路Pitis,我们令 E1=eePitis(vit,vis)M*于是,E1即是最优的。,29,离散数学,7.Hamilton 图 Hamilton图的定义 Hamilton图的理论,30,离散数学,7.Hamilton 图Hamilton 图的引出及其定义 Hamilton 图是由威廉哈密顿(Sir Willian Hamilton)爵士于1856年在解决关于正十二面体的一个数学游戏时首次提出的。1856年Hamilton爵士发明了一种数学游戏:一个人在(实心的)正十二面体的任意
22、五个相继的顶点(正十二面体是由12个相同的正五边形组成,有二十个顶点,三十条棱)上插上五个大头针,形成一条路,要求另一个人扩展这条路,以形成一条过每个顶点一次且仅一次的圈。有趣的是Hamilton爵士后来将他的发明及解决方案卖给了一个玩具商,所获是25个金币。Hamilton爵士在1859年给他的朋友Graves的信中,将他的正十二面体数学游戏重新叙述为:能否在全球选定,31,离散数学,的二十个都会城市(据说有我们中国三个城市:北京、上海、西安)中,从任一城市出发,作全球航行,经过这二十个城市一次且仅一次(不能去其它城市),然后回到出发点?这就是著名的环球航行问题或周游世界问题。Hamilto
23、n给出了这个问题的肯定的答案(参见图1及图2)。,32,离散数学,注:威廉哈密顿(Sir Willian Hamilton(1805-1865)爵士是(英国)爱尔兰最伟大的学者之一。他是都柏林大学的天文学教授,在那里他出版了许多关于物理和数学的论文。在数学方面,他提出了著名的四元组理论和对复数系统的归纳。四元组理论奠定了抽象代数的发展基础。还据此提出了矢量概念。在理论物理学里,有著名的哈密顿动力学系统。定义1.Hamilton路 圈 图 设G(V,E)是简单图。则(1)H-路是一条初级路,它穿过图中每个结点一次且仅一次;(2)H-圈是一条初级圈,它穿过图中每个结点一次且仅一次;(3)H-图是含
24、有H-圈的图。,33,离散数学,注:需要指出的是,尽管从表面上看Hamilton问题和Euler问题似乎很相似,但它们之间并无必然的联系。E-圈(E-图)未必是H-圈(H-图);H-圈(H-图)也未必是E-圈(E-图)。因为,H-圈是初级圈,强调的是穿过每个结点一次且仅一次;而E-圈是简单圈,强调的是穿过每条边一次且仅一次。下面的图3和图4可以说明这点。,34,离散数学,判定E-圈(E-图)的充要条件(等价性条件)已经得到,它就是Euler定理。所以Euler 问题在理论上已经彻底解决;而判定H-圈(H-图)的充要条件(等价性条件)迄今为止人们还未提出,人们只是得到一些是必要性条件或者是充分性
25、条件的单边(单方向)判定方法。所以Hamilton问题在理论上远未得到彻底解决。判定H-圈(H-图)的充分性条件只能用来肯定,不能用来否定。即只能在满足条件时用来证明有H-圈(是H-图);而不能在不满足条件时用来证明没有H-圈(不是H-图)。判定H-圈(H-图)的必要性条件只能用来否定,不能用来肯定。即在不满足条件时用来证明没有H-圈(不是H-图);而不能在满足条件时用来证明有H-圈(是H-图)。近年来,人们对Hamilton问题的研究一直没有停止,不断的有新成果面世。判定H-图(H-圈)的必要性定理(必要性条件),35,离散数学,定理1.(必要性定理)设G(V,E)是简单无向图。则 G是H图
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 图论
链接地址:https://www.31ppt.com/p-6326497.html