第二章 道路与回路2.1道路与回路.ppt
《第二章 道路与回路2.1道路与回路.ppt》由会员分享,可在线阅读,更多相关《第二章 道路与回路2.1道路与回路.ppt(55页珍藏版)》请在麦多课文档分享上搜索。
1、第二章 道路与回路 2.1道路与回路,定义2.1.1有向图G=(V,E)中,若边序列P=(ei1, ei2, , eiq),其中eik=(vl, vj) 满足vl是eik-1的终点, vj 是eik+1的始点,就称P是G的一条有向道路.如果eiq的终点也是ei1的始点,则称P是G的一条有向回路,道路与回路,如果P中的边没有重复出现,则分别称为简单有向道路和简单有向回路 进而, 如果P中结点也不重复出现, 又分别称它们是初级有向道路和初级有向回路, 简称为路和回路 显然,初级有向道路(回路)一定是简单有向道路(回路),有向道路,(e1, e2, e5, e1) 有向道路,不是简单有向道路 (e1
2、, e2, e5, e4) 简单有向道路,不是初级有向道路(A) (e1, e2, e3) 初级有向道路 (e1, e2, e5) 初级有向回路,道路与回路,定义2.1.2无向图G=(V, E)中,若点边交替序列P=(vi1, ei1, vi2, ei2, , eiq-1, viq)满足vik, vik+1是eik的两个端点, 则称P是G中的一条链或道路. 如果viq=vi1, 则称P是G中的一个圈或回路 如果P中没有重复出现的边, 称之为简单道路或简单回路, 若其中结点也不重复, 又称之为初级道路或初级回路,例,V1到v4的初级道路,v1,e1,v2,e6,v5,e4,v4,e7,v2,V1
3、到v2的简单道路,道路与回路,定义2.1.31. 设G是无向图, 若G的任意两结点之间都存在道路, 就称G是连通图, 否则称为非连通图2. 如果G是有向图, 不考虑其边的方向, 即视为无向图, 若它是连通的, 则称G是连通图3. 若连通子图H不是G的任何连通子图的真子图, 则称H是G的极大连通子图或称连通支显然G的每个连通支都是它的导出子图,连通图,连通图,A,B,C,D,非连通图 两个连通分支B, A, C, D,道路与回路,定义2.1.4设C是简单图G中含结点数大于3的一个初级回路,如果结点vi和vj在C中不相邻,而边(vi,vj)E(G),则称(vi,vj)是C的一条弦。,道路与回路,证
4、明:若对简单图G中每一个vkV(G),都有d(vk)3,则G中必含带弦的回路。 证明:在G中构造一条极长的初级道路P=(v0, ei1, v1, ei2, , vl-1, eil, vl)。由于P是极长的初级道路,所以v0和vl的邻接点都在该道路P上。由已知条件,d(vk)3,不妨设(v0)=v1, vij, vik, , 其中1jk,这时(v0, v1, , vik, v0)是一条初级回路,而(v0, vij)就是该回路中的一条弦。,带弦回路,1. 构造极长初级道路 (v0, v1), (v0, v1, v2), (v0, v1, v2, v3), (v0, v1, v2, v3, v4)
5、2. (v0)=v1,v2,v3,v4 3. (v0,v1,v2,v3,v0)即为所求的初级回路,而(v0,v2)就是该回路的一条弦,极长初级道路,极长初级道路: 在无向简单图G=中, E,设1=v0v1vl为G中一条初级道路,若路径的两个端点v0和vl不与初级道路本身以外的任何结点相邻, 这样的初级道路称为极长初级道路(有向图中, 初级道路起点的前驱, 终点的后继, 都在初级道路本身上),扩大初级道路法,扩大初级道路法: 任何一条初级道路, 如果不是极长初级道路, 则至少有一个端点与初级道路本身以外的结点相邻, 则将该结点及其相关联的边扩到新的初级道路中来, 得到更新的初级道路。继续上述过程
6、, 直到变成极长初级道路为止,道路与回路,定义2.1.5设G=(V,E)是无向图,如果V(G)可以划分为子集X和Y,使得对所有的e=(u,v)E(G), 都有u和v分属于X和Y,则称G是二分图(偶图)。完全二分图 完全二分图K3,3,道路与回路,证明:如果二分图G中存在回路,则它们都是由偶数条边组成的。证明:设C是二分图G的任一条回路,不妨设v0X 是C的始点,由于G是二分图,所以沿回路C必须经过偶数条边才能达到某结点viX,因而只有经过偶数条边才能回到v0。,道路与回路,证明:设G是简单图,当m(n-1)(n-2)/2时,G是连通图。 证明:假定G是非连通图,则它至少含有2个连通分支。设分别
7、是G1=(V1,E1), G2=(V2,E2)。其中|V1(G1)|=n1, |V2(G2)|=n2, n1+n2=n, |E1(G1)|+|E2(G2)|=m。由于G是简单图,因此,道路与回路,由于1n1n-1, 1n2n-1 所以 与已知条件矛盾,故G是连通图。,2.3 欧拉道路与回路,1736年瑞士著名数学家欧拉(Leonhard Euler)发表了图论的第一篇论文“哥尼斯堡七桥问题”成功地回答了,图中是否存在经过每条边一次且仅一次的回路 人们普遍认为欧拉是图论的创始人 1936年,匈牙利数学家寇尼格(Konig)出版了图论的第一部专著有限图与无限图理论,这是图论发展史上的重要的里程碑,
8、它标志着图论将进入突飞猛进发展的新阶段,哥尼斯堡七桥问题,哥尼斯堡城(现在俄罗斯)在18世纪属东普鲁士,它位于普雷格尔(Pregel)河畔,河中有两个岛,通过七座桥彼此相联,如下图:,当时城中居民热衷于这样一个问题:游人从四块陆地中任一块出发,按什么样的线路方能做到每座桥通过一次且仅一次而最后返回原地。,1736年,瑞士数学家列昂哈德. 欧拉(Leonhard Euler) 仔细研究了这个问题,他将上述四块陆地与七座桥间的关系用一个抽象的图形来描述,其中的四块陆地分别用四个点表示,而陆地之间有桥相连者则用连结两个点的边表示。,欧拉得出结论:哥尼斯堡桥问题是 无解的,即一个人不可能一次走遍 两岛
9、、两旁陆地和七座桥。,一笔画,欧拉道路与回路,定义2.3.1无向连通图G=(V, E)中的一条经过所有边的简单回路(道路)称为G的欧拉回路(道路) 定理2.3.1无向连通图G存在欧拉回路的充要条件是G中各结点的度都是偶数,欧拉道路与回路,定理2.3.1的证明: 必要性:若G中有欧拉回路C,则C过每条边一次且仅一次对任一结点v来说,如果C经过ei进入v,则一定通过另一条边ej从v离开. 因此结点v的度是偶数 充分性:由于G是有穷图,因此可以断定,从G的任一结点v0出发一定存在G的一条简单回路C. 这是因为各结点的度都是偶数,所以这条简单道路不可能停留在v0以外的某个点,而不能再向前延伸以致构成回
10、路C,定理2.3.1充分性证明,如果E(G)=C, 则C就是欧拉回路,充分性得证。 否则在G中删去C的各边,得到G1=G-C。 G1可能是非连通图,但是每个结点的度保持为偶数。这时,G1中一定存在某个度非零的结点vi, 同时vi也是C中的结点。否则C的结点与G1的结点之间无边相连,与G是连通图矛盾。 同理,从vi出发,G1中vi所在连通分支内存在一条简单回路C1。显然,CC1仍然是G的一条简单回路,但它包括的边数比C多。 继续以上构造方法,最终有简单回路C= CC1Ck ,它包含了G的全部边,即C是G的一条欧拉回路,构造欧拉回路,C=(e1,e6,e8,e7,e2) C=(e3,e5,e4)C
11、C=(e1,e3,e5,e4,e6,e8,e7,e2)=E(G),v2,v4,v5,v3,v1,v2,v4,v5,e2,v1,e1,e6,e5,e7,e8,e4,e3,e5,e4,e3,v3,欧拉道路与回路,推论2.3.1若无向连通图G中只有2个度为奇的结点,则G存在欧拉道路.证明:设vi和vj是两个度为奇数的结点. 作G=G+(vi, vj), 则G中各点的度都是偶数. 由定理2.3.1, G有欧拉回路, 它含边(vi, vj), 删去该边, 得到一条从vi到vj的简单道路, 它恰好经过了G的所有边, 亦即是一条欧拉道路,欧拉道路与回路,结论:七桥问题既不存在欧拉回路也不存在欧拉道路。 推论
12、2.3.2若有向连通图G中各结点的正、负度相等, 则G存在有向欧拉道路.其证明与定理2.3.1的证明相仿,欧拉道路与回路,例2.3.3 设连通图G=(V,E)有k个度为奇数的结点,那么E(G)可以划分成k/2条简单道路。 证明:由性质1.1.2,k是偶数。在这k个结点间增添k/2条边,使每个结点都与其中一条边关联,得到G,那么G中各结点的度都为偶数。由定理2.3.1,G包含一个欧拉回路C。而新添的k/2条边在C上都不相邻。所以删去这些边后,我们就得到由E(G)划分成的k/2条简单道路。,举例,欧拉回路(1,2,3,4,5,6,7,8,9) 2(=4/2)条简单道路(3,4)和(6,7,8,9,
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
本资源只提供5页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
2000 积分 0人已下载
下载 | 加入VIP,交流精品资源 |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第二 道路 回路 21 PPT
![提示](http://www.mydoc123.com/images/bang_tan.gif)