G2通路 离散数学.ppt

《G2通路 离散数学.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图的连通性1LuChaojun,SJTULuChaojun,SJTU2通道定义:无向图G中,若点边交替序列W=v0e1v1e2v2…ekvk满足:vi1和vi是ei的两个端点,则称W是一条从v0到vk的通道.v0称起点,vk称终点.k是通道长度.若v0vk,则称开通道;否则称为闭通道.简便表示法:边序列对简单图可用顶点序列LuChaojun,SJTU3迹和路迹/简单通道:没有重复边的通道.闭迹/简单回路路/初级通道:没有重复顶点的通道.圈/初级回路:起点和终点重合的路.奇圈vs偶圈:长度为奇数vs偶数含圈简单图G的周长c(G):G中最长圈的长度.含圈

2、简单图G的围长g(G):G中最短圈的长度.例:c(Kn),g(Kn),c(Kn,n),g(Kn,n)LuChaojun,SJTU4连通性若图G的顶点u和v之间存在通道,则称u和v是连通的(connected).u和v之间的短程线:u和v之间的最短通道.u和v之间的距离d(u,v):u和v之间的短程线的长度.若图G的任意两个顶点都是连通的,则称G是连通的.若G的连通子图H不是G的任何连通子图的真子图,则称H是G的极大连通子图,或称连通支(connectedcomponent).显然G的每个连通支都是它的导出子图.任何非连通图都是2个以上连通支的并.LuCh

3、aojun,SJTU5例题:连通性简单图G:若m(n1)(n2)2,则G是连通图.证明:用反证法.设G有k1个连通支.各连通支顶点数分别为n1,...,nk,边数分别为m1,...,mk.因为是简单图,故mini(ni1)2又因为nin(k1)n1,故mmini(ni1)2(n1)(ni1)2(n1)(nk)2(n1)(n2)2.与已知条件矛盾.LuChaojun,SJTU6常用证法:归纳定理:若图G(V,E)是连通图,则mn1.证明思想:先设G是简单图.对顶点数n归纳.奠基:n1,

4、平凡.归纳:nk(k1)时成立nk1时成立.对k1阶连通图G,作G'Gv,设G'有s个连通支.由归纳假设,mini1.又显然从G到G'至少删掉了s条边,故mmi+snis+sn1.对非简单图,连通显然需要更多的边.图论中常对顶点数或边数归纳证明.LuChaojun,SJTU7常用证法:删圈法定理:图G(V,E)中若存在u-v通道,则存在长度小于n的u-v通道.证明思想:长度n的u-v通道W中必含重复顶点s,即存在s-s闭通道C,删去C后(仅保留s)仍为u-v通道,但长度减小.重复此过程即可.usvLuChaojun,

5、SJTU8常用证法:删圈法(续)推论:图G(V,E)中若存在u-v通道,则存在长度小于n的u-v路.定理:图G(V,E)中若存在u-u闭通道,则存在长度小于等于n的u-u闭通道.推论:图G(V,E)中若存在u-u闭迹,则存在长度小于等于n的u-u闭迹.LuChaojun,SJTU9常用证法:极限对象路的延长:对一条路,若其起点/终点还与路外顶点相邻,则将相邻顶点加入,即得一更长的路.重复此过程,直至无法扩大,最后所得路称为极大路.最长路:是极大路之一.极大路的性质:起点/终点的相邻点都在路上.图论证明中常利用这种极限对象.LuChaojun,SJT

6、U10例题若简单图G(n4)的顶点度数都3,则G中存在长度4的圈.证明:任取一极大路,设u为一个端点.则u的邻点都在路上,至少有u1,u2,u3.连接u与u3即得长度4的圈.uu1u3u2二部图的一个充要条件定理:图G是二部图G中无奇圈.证明思想:容易.不妨设G连通.取V1{与u距离为偶数的顶点},V2{与u距离为奇数的顶点}.只要证明任意边e的端点分别在V1和V2中.否则必有奇圈.割点与割边定义:若G'Gv的连通支数比G多,则v称为G的割点.删除连通图中的割点必导致不连通.定义:若G'Ge的连通支数比G多,则e称为G的割边或桥

7、.删去euv,则u,v分属于不同的连通支.定理:euv是割边e不属于任何圈.:若e属于某圈,则GGe中仍有从u到v的通道.:若e不是割边,则GGe中与的连通支数一样,故u,v属于同一连通支,有从u到v的通道,可与e构成圈.邻接矩阵应用:两点间通道数定理:设G的邻接矩阵为A,则从vi到vj的长度为r(正整数)的不同通道的数目等于Ar的(i,j)元素.证明思想:对r归纳.需了解矩阵乘法.此法可扩充为允许环和重边.此法还可用于求两顶点距离,判定连通性.欧拉图与哈密顿图哥尼斯堡七桥问题1736年,Euler发表论文“哥尼斯堡的七座桥”,解决

8、了下图中是否存在经过每条边一次且仅一次的回路的问题.15LuChaojun,SJ