离散数学通路回路与图的连通性.ppt

《离散数学通路回路与图的连通性.ppt》由会员分享，可在线阅读，更多相关《离散数学通路回路与图的连通性.ppt（43页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、1,7.2 通路、回路与图的连通性,简单通(回)路, 初级通(回)路, 复杂通(回)路 连通图, 连通分支 弱连通图, 单向连通图, 强连通图 点割集与割点 边割集与割边(桥),2,在图中，一条通路是顶点和边的交替序列，以顶点 开始，以顶点结束。其中，第一条边的终点与第二 条边的始点重合.。第一条边的始点称为通路的 始点，最后一条边的终点称为通路的终点。,当通路的终点和始点重合时，称为回路。 通路或回路中所含边数称为该通路或回路的长度。,一、通路和回路,3,1、简单通路：如果通路中各边都不相同。,如简单通路：v1v2 v5 v6 v2 v3 v4长度为6,如简单回路：v1v2 v3 v5 v2

2、 v6 v1长度为6,2、简单回路：如果回路中各边都不相同。,4,3、基本通路：如果通路中各个顶点都不相同。,4、基本回路：如果回路中各个顶点都不相同。,如基本通路：v1v6 v3 v4长度为3,如基本回路：v1v6 v3 v2 v1,显然，基本通路（回路）一定是简单通路（回路）。 反之不然。,5,若通路(回路)中有边重复出现, 则称为复杂通路(回路).,6,关于通路与回路的几点说明,表示方法 用顶点和边的交替序列(定义), 如=v0e1v1e2elvl 用边的序列, 如=e1e2el 简单图中, 用顶点的序列, 如=v0v1vl 非简单图中,可用混合表示法,如=v0v1e2v2e5v3v4v

3、5 环是长度为1的圈, 两条平行边构成长度为2的圈. 在无向简单图中, 所有圈的长度3; 在有向简单图中, 所有圈的长度2.,7,在两种意义下计算的圈个数 定义意义下 在无向图中, 一个长度为l(l3)的圈看作2l个不同的圈. 如v0v1v2v0 , v1v2v0v1 , v2v0v1v2看作3个不同的圈. 在有向图中, 一个长度为l(l3)的圈看作l个不同的圈. 同构意义下 所有长度相同的圈都是同构的, 因而是1个圈.,8,定理 在n阶图G中，若从顶点vi到vj（vivj）存在通路，则从vi到vj存在长度小于等于n1的通路.,推论 在n阶图G中，若从顶点vi到vj（vivj）存在通 路，则从

4、vi到vj存在长度小于等于n1的初级通路.,定理 在一个n阶图G中，若存在vi到自身的回路，则一定存在vi到自身长度小于等于n的回路.,推论 在一个n阶图G中，若存在vi到自身的简单回路，则一定存在长度小于等于n的初级回路.,9,在图G中，如果A到B存在一条通路，则称A到B是可达的。 1、无向图的连通性 如果无向图中，任意两点是可达的，图为连通图。否则为 不连通图。 当图是不连通时，定是由几个连通子图构成。称这样的连 通图是连通分支。,二、图的连通性：,10,无向图的连通性,设无向图G=, u与v连通: 若u与v之间有通路. 规定u与自身总连通. 连通关系 R=| u,v V且uv是V上的等价

5、关系 连通图: 平凡图, 任意两点都连通的图 连通分支: V关于R的等价类的导出子图 设V/R=V1,V2,Vk, GV1, GV2, ,GVk是G的连通分支, 其个数记作p(G)=k. G是连通图 p(G)=1,11,设 A=1,2,8, R= | x,yAxy(mod 3) 即:A上模3等价关系的关系图为:,12,【例】 求证：若图中只有两个奇度数顶点，则二顶点必连通。 证明 用反证法来证明。 设二顶点不连通，则它们必分属两个不同的连通分支，而对于每个连通分支，作为G的子图只有一个奇度数顶点，余者均为偶度数顶点，与握手定理推论矛盾，因此，若图中只有两个奇度数顶点，则二顶点必连通。,13,【

6、例】 在一次国际会议中，由七人组成的小组a,b,c,d,e,f,g中，a会英语、阿拉伯语；b会英语、西班牙语；c会汉语、俄语；d会日语、西班牙语；e会德语、汉语和法语；f会日语、俄语；g会英语、法语和德语。问：他们中间任何二人是否均可对话（必要时可通过别人翻译）？,14,解 用顶点代表人，如果二人会同一种语言，则在代表二人的顶点间连边，于是得到下图。问题归结为：在这个图中，任何两个顶点间是否都存在着通路？由于下图是一个连通图，因此，必要时通过别人翻译，他们中间任何二人均可对话。,15,定理 在n阶简单图G, 如果对G的每对顶点u和v, deg(u) + deg(v) n1, 则G是连通图。 证

7、明 假设G不连通, 则G至少有两个分图。 设其中一个分图含有q个顶点, 而其余各分图共含有n q个顶点。 在这两部分中各取一个顶点u和v, 则 0deg(u)q 1, 0deg(v)n q 1, 因此deg(u) + deg(v)n 2, 这与题设deg(u ) + deg(v)n 1矛盾。,16,短程线与距离,u与v之间的短程线: u与v之间长度最短的通路 (u与v连通) u与v之间的距离d(u,v): u与v之间短程线的长度 若u与v不连通, 规定d(u,v)=. 性质： d(u,v)0, 且d(u,v)=0 u=v d(u,v)=d(v,u) d(u,v)+d(v,w)d(u,w),17

8、,在实际问题中, 除了考察一个图是否连通外, 往往还要研究一个图连通的程度, 作为某些系统的可靠性度量。 图的连通性在计算机网、通信网和电力网等方面有着重要的应用。,图的连通性的应用,18,点割集,在连通图中，如果删去一些顶点或边，则可能会影响图的连通性。所谓从图中删去某个顶点v，就是将顶点v和与v关联的所有的边均删去；删除边只需将该边删除,19,例如”国际会议对话”任何一人请假，图G-v还连通，小组对话仍可继续进行，但如果f、g二人同时不在，G-f，g是分离图，则小组中的对话无法再继续进行。,20,点割集,记 Gv: 从G中删除v及关联的边 GV: 从G中删除V中所有的顶点及关联的边 Ge

9、: 从G中删除e GE: 从G中删除E中所有边 定义 设无向图G=, VV, 若p(GV)p(G)且VV, p(GV)=p(G), 则称V为G的点割集. 若v为点割集, 则称v为割点.,21,点割集(续),例 v1,v4, v6是点割集, v6是割点.,22,例 v2, v7, v3, v4为点割集, v3, v4均为割点 例 在下图中的那些是割点 v3和v2都是割点, v2, v3,v4,v1, v2, v4,v5都不是点割集。,23,边割集,定义 设无向图G=, EE, 若p(GE)p(G)且EE, p(GE)=p(G), 则称E为G的边割集. 若e为边割集, 则称e 为割边或桥. 在下图

10、中，e1,e2，e1,e3,e5,e6，e8等是边割集， e8是桥，e7,e9,e5,e6是边割集吗？,24,图中 e1, e2, e1, e3, e4, e6, e7, e8, e2, e3, e4, e2, e3, e5, e4, e5, e7, e9, e8, e9,等都是割集, 其中e6为桥。 割点或割边都是图连通的关键部位, 并不是所有的图都有割点或割边。 没有割点和割边的连通图, 需要去掉几条边或几个点, 图才会变得不连通。,25,几点说明： Kn无点割集 n阶零图既无点割集，也无边割集. 若G连通，E为边割集，则p(GE)=2 若G连通，V为点割集，则p(GV)2,一个连通图G，

11、若存在点割集和边割集，一般并不唯一，且各个点（边）割集中所含的点（边）的个数也不尽相同。我们用含元素个数最少的点割集和边割集来刻画它的连通度,26,下面从数量观点来描述图的连通性。 定义 设G = (V, E)是连通图, k(G) = min| V | | V是G的点割集称为G的点连通度; (G) = min| E | | E是G的边割集称为G的边连通度。 图G的点连通度是为了使G成为一个非连通图,需要删除的点的最少数目。 若图G中存在割点, k(G) = 1。 图G的边连通度是为了使G成为一个非连通图, 需要删除的边的最少数目。 若图G中存在割边, (G) = 1。,27,【例】 下图中的两

12、个连通图都是n=8，e=16，其中,（G1）=4,(G1）=4,（G2）=1， （G2）=3。,28,假设n个顶点代表n个站，e条边表示铁路或者桥梁或者电话线，en-1。为了使n个站之间的连接不容易被破坏，必须构造一个具有n个顶点e条边的连通图，并使其具有最大的点连通度和边连通度。按图中G1的连接法，如果3个站被破坏，或者3条铁路被破坏，余下的站仍能继续相互联系，也就是仍具有连通性。但按图中G2的连接法，如果v站被破坏，余下的站就不能保持连通。,29,定理 对任意的图G = (V, E), 有 k(G) (G) (G)(*) 证明 若G是平凡图或非连通图, 则 k(G) = (G) = 0,

13、上式显然成立。 若G是连通图, 则因每一顶点的所有关联边构成一个边割集, 所以 (G)(G)。 下面证明k (G) (G)。 若 (G) = 1, 则G有一割边, 此时 k(G) = (G) = 1, (*) 式成立。,30,若 (G)2, 则必可删去某 (G)边, 使G不连通,而删去其中(G) 1条边, G仍然连通, 且有一条桥e = u, v。 对 (G) 1条边中的每一条边都选取一个不同于u, v的顶点, 把这些 (G) 1个顶点删去则必至少删去 (G) 1边。 若剩下的图是不连通的, 则k(G)(G)1 (G); 若剩下的图是连通的, 则e仍是桥, 此时再删去u和v, 就必产生一个非连

14、通图, 也有k (G) (G)。 综上所述, 对任意的图G, 有k (G) (G) (G)。,31,例 在下图中, k(G) = 1, (G) = 2, (G) = 3,定义 设有图G = (V, E), 若k(G)h, 则称G是h-连通的; 若(G)h, 则称G是h-边连通的。 例 上图所示的图是1-连通的, 是2-边连通的。,32,简单图都是1-连通的和1-边连通的。 n阶完全图是(n1)-连通的和(n1)-边连通的。 对于任何n阶连通图, 当且仅当没有割点时, 它是2-连通的; 当且仅当没有割边时, 它是2-边连通的。 若图G是h-连通的, 则G也是h-边连通的。(k(G) (G) 由定

15、义可知, 若h1h2, 图G是h1-连通的, 则G也是h2-连通的。 若h1h2, 图G是h1-边连通的, 则G也是h2-边连通。 一个图的连通度越大, 它的连通性能就越好。,33,例如:下图的边连通度是3，所以它是3边连通的，也是2边连通的和1-边连通的，但不是4边连通的。,34,2、有向图的连通性,对于有向图，“图中任意两点都有通路相连”，这个要求 很高，因为有向图虽然是连在一起的，但受到边的方向 的限制，任意两点不一定有通路。以下分三种情况讨论：,35,1）强连通图：有向图中，任意A、B是互为可达的。如图(a) 2）单向连通图：在有向图中，任意两点A、B存在着A到B的通路 或存在着B到A

16、的通路。如图(b) 3）弱连通图：在有向图中，如果其底图是无向连通图。如图(c),显然：在有向图中，如果有一条通过图中所有点的回路， 则此图是强连通的。 如果有一条通过图中所有点的通路， 则此图是单向连通图。,(a) (b) (c),36,单向连通图都是弱连通图，但弱连通图 却不一定是单向连通图。 在弱连通图中，存在这样的顶点A、B， 从A到B不可达，且从B 到A也不可达。 强连通图既是单向连通图，又是弱连通图。 即强连通单向连通弱连通,37,有向图的连通性(续),定理(强连通判别法) D强连通当且仅当D中存在经过每个顶点至少一次的回路 定理(单向连通判别法) D单向连通当且仅当D中存在经过每

17、个顶点至少一次的通路,38,思考：判断下列图中哪些是强连通图，哪些是单向连通图，哪些 是弱连通图。,(a),(b),(d),(c),答案: (a), (d)是强连通图, (b)是单向连通图, (c)是弱连通图.,39,有向图的短程线与距离,u到v的短程线: u到v长度最短的通路 (u可达v) u与v之间的距离d: u到v的短程线的长度 若u不可达v, 规定d=. 性质： d0, 且d=0 u=v d+d d 注意: 没有对称性,40,定义：设G是有向图， G是其子图， 若G是强连通的（单向连通的，弱连通的） 且没有包含 G的更大的子图是强连通的 （单向连通的，弱连通的），则称G是G的 极大强连通子图（极大单向连通子图，极大 弱连通子图）， 也称为强分支（单向分支，弱分支）。,41,【例】 求下图中G的所有强分图、单向分图和弱分图。,42,解 V1=v1，v4 ，v5、V2=v2，v6、V3=v3的导出子图GV1、GV2、GV3均是G的强分图见图（a）G1、G2、G3；V4=v1，v2，v3，v4，v6、V5=v2，v3，v6的导出子图 GV4、GV5均是G的单向分图（见图（b）G4、G5）；G是弱连通的，故G的弱分图就是G自身。,43,