【教学课件】第五章图论(第二部分).ppt

《【教学课件】第五章图论(第二部分).ppt》由会员分享，可在线阅读，更多相关《【教学课件】第五章图论(第二部分).ppt（29页珍藏版）》请在三一办公上搜索。

1、1,第 五 章 图 论(第二部分),1.通路2.图的连通性,2,1.通路,定义通路 pseudo path 设G(V，E)是图，v0，vn是G中两点。若G中结点序列v0v1 vn满足：vi与vi+1相邻(0 in),则该序列称为从v0到vn的通路。两个端点相同的通路称为回路（环或圈）。通路中包含的边数称为该通路的长度。注意：(1)通路中允许有重复的结点和边。,3,通路举例,通路：ADEBDEA,回路：ACDBCEA,回路：ABCDEA,4,A,B,C,D,E,简单通路：ADEBD,简单回路：ACDBCEA,定义简单通(回)路 各边均不相同的通路称为简单通路。各边均不相同的回路称为简单回路,简单

2、通(回)路,5,基本通(回)路,定义基本通(回)路 结点各不相同的通路称为基本通路。中间结点各不相同的回路称为基本回路。,A,B,C,D,E,基本通路：ACEBD,基本回路：ABCDEA,6,有向通(回)路,定义有向通(回)路 若通路v0v1 vn各边是有向边，且vi-1和vi分别是有向边的始点与终点，则称该通路为有向通(回)路。,7,通路定理,定理通路定理 在n阶图G中，如果有顶点u到v（u v）的通路，那么u到v必有一条长度小于等于n1的基本通路。,8,通路定理证明,定理：在有n个顶点的图G中，如果有顶点u到v的通路，必有长度不大于n-1的基本通路。证明：(1)先证明u和v之间存在基本通路

3、 若uv之间的通路P中有相同的顶点，则从P中删除相同顶点之间路径，直到P中没有相同顶点，这样得到的路径为u和v之间的基本通路。(2)再证基本通路长度不大于n-1（反证法）设u和v之间的基本通路的长度。一条边关联两个顶点，长度的基本通路上至少有个顶点。至少有两个相同顶点在u和v之间的基本通路上，这与基本通路的性质“任意两个顶点不同”相矛盾。基本通路的长度=n-1,9,路径：回路定理,定理回路定理 在有n个顶点的图G中，如果有顶点v到自身的通路，那么必定有一条从v到v的长度不大于n的基本回路。,10,连通性定义,定义两结点连通(可达)若u与v之间有通路相连，则称u与v连通（可达）。规定：任意顶点与

4、自身连通。定义连通无向图任意两个顶点都连通的无向图,11,有向图的连通性,强连通的有向图任意两个顶点都是互相连通的。单向连通的有向图任意两个顶点，至少从一个顶点到另一个是连通的弱连通的有向图底图连通的,12,强连通图性质（补充）,定理：一个有向图G是强连通的当且仅当中有一条包含所有顶点至少一次的回路。证明：中有一条包含所有顶点的回路，显然强连通。/*连通图的定义*/：如果 G强连通，G中的顶点为v1，v2，.vn,设v1到v2路径为P1，v2到v3的路径为P2，vn到v1 的路为Pn，将P1，P2，.Pn连起来，此路是一条包含G中所有顶点的回路。,13,有向图连通性举例,判断下面给出的图是强连

5、通图、单向连通图还是弱连通图。,强连通图,弱连通图,强连通图,单向连通图,14,无向图的连通分支,定义连通分支（connected component）设图G 是无向图G的子图的，如果：(1)G 是连通的，(2)G 不是任何其它连通子图的真子图（极大性）则称G 是G的连通分支。,G,定义连通图：只有一个连通分支的图。,15,无向图连通分支举例,例 请指出下图G的连通分支数。,v3,v4,v5,v6,v7,v1,v2,G,16,有向图的连通分支,定义强（单向、弱）连通分支 设图G 是有向图G的子图的，如果：(1)G 是强连通（单向连通、弱连通）的，(2)G 不是任何其它强连通（单向连通、弱连通）

6、子图的真子图（极大性）则称G 是G的强连通分支/强分支（单向连通分支/单向分支、弱连通分支/弱分支）。,17,有向图的连通分支举例,强分支:、,单向分支:、，,弱分支:、,例 请指出下图G的所有强分支、单向分支和弱分支。,18,有向图连通分支举例,请给出下图的所有强分支、单向分支和弱分支,强分支：GA、GE、GF、GB、GC、GD、GP,Q,S,T,单向分支：GA,E,F、GB,C,D、GA,B,C,D、GA,C,D,E、GP,Q,S,T,弱分支：GA,B,C,D,E,F，GP,Q,S,T,19,若n阶图G的邻接矩阵为A=(aij)nn，V(G)=v1,v2,vn,则：（1）若ij 1，表明v

7、i到vj有一条边，即vi到vj连通；（2）若ij，表明vi到vj没有长度为1的通路。ij的值表示G中i到j长度为的通路条数。,图的连通性：连通性质讨论,20,定理若G的邻接矩阵为A，则矩阵m的元素bij表示vi到vj长度为的通路条数。,连通性质讨论(续),21,可达矩阵,定义可达矩阵 若阶有向图的邻接矩阵为A，令B=A+A2+An-1+An 将B中不为0的元素改为1，为0的元素不变，修改后所得到的矩阵(bij)nn称为G的可达矩阵。图G从vi点到vj点有通路当且仅当？,bij=1,22,图的连通性与可达矩阵,有向图的连通性（n1）：设有向图G的可达矩阵为B(1)强连通(2)是单向连通的无向图的

8、连通性（n1）：设无向图G的可达矩阵为B 连通,B中元素全为,B中所有关于主对角线对称的两个元素中至少一个值为,B中元素全为,23,连通性证明题举例1,试证：若个顶点的无向图G=(V,E)连通，则|E|（）。证明：(归纳法)(1)，由G连通可知:|E|1=,定理成立。(2)假设时,结论成立,即|E|1.(3)证法一:当时，由递归假设可知:|E|1.任选G中一个结点v 若G-v连通,则|V(G-v)|=k,故由递归假设|E(G-v)|1;而由v与G-v至少有一条边相连可知:|E|E(G-v)|+1;若G-v不连通,不妨设G-v中有m个连通分支G1,G2,Gm,设|V(Gi)|=xi;显然,对所有

9、i=1,2,3,m,都有:xik.由归纳假设可知E(Gi)xi-1,而v与每个连通分支至少有一条边相连,故 E(Gi)m+i=1m(xi-1)=m+i=1mxi-m=i=1mxi=k.,24,连通性证明题举例1(续),(3)证法二:显然,在个顶点中，不存在孤立顶点，否则，G不连通。即G中所有顶点度数至少为1。1)若G中无度为的顶点，则 G中所有顶点的度数和2k。进而，由握手定理可知：|E|k+。命题得证。2)若G中至少存在一个度数为1的顶点，设为v。令G=G-v,则G有k个顶点且G连通。根据递归假设E(G)1，故|E|=E(G)+v与G相连的边数k-1+1=k.命题得证.,25,连通性证明举例

10、2,证明：若G是简单图，设为G的顶点的最小度，若|V(G)|/2-1，则G是连通图。,证明：（反证法）假设G不是连通图。则G中至少存在两个连通分支，不妨设G中的两个连通分支分别为G1和G2，且|V(G1)|V(G2)|。则有：|V(G1)|V(G)|/2。而由G是简单图可知：G1中任意顶点v的度数满足：d(v)|V(G1)|-1|V(G)|/2-1 进而，d(v)|V(G)|/2-1，这与前提条件|V(G)|/2-1矛盾。因此，G是连通图。,26,连通性证明举例3,设G是n阶无向简单图，若G中任意不同的两个顶点的度数 之和大于等于n 1，请证明G是连通图。证明：反证法。假设G不连通。不妨设G有

11、k个连通分支G1，G2，Gk，n1，n2，nk是各分支的顶点数。则有：n1+n2+nk=n 任取u G1,v G2。由G是简单图可知：deg(u)=n1 1 且 deg(v)=n2 1。因此，deg(u)+deg(v)=n1 1+n2 1=n 2 这与题设“任意不同的两个顶点的度数之和大于等于n 1”矛盾。G是连通图,27,设图G是无向简单图。请证明图G和补图G中至少有一个连通图。证明：(1)如果G是连通图，问题得证。(2)如果G不是连通图。任取u,v G，设G的连通分支有G1，G2，Gk 如果u和v是属于G中不同的连通分支Gi和Gj，则(u,v)G 如果u和v是属于G中相同的连通分支Gi，则

12、可在G的另一个连通分支中取一个结点x，则(u,x)G,(v,x)G。u和v之间在G中有通路uxv相连。由u和v的任意性，可知G是连通的。综上所述，G和补图G中至少有一个是连通图。,连通性证明举例4,28,课堂练习,证明：若G是简单图，设为G的顶点的最小度，若k，则G中有长为k的基本通路。,29,课堂练习解答,2.证明：（反证法）假设G中不存在长度为k的基本通路。设P=v1v2vm为G中最长基本通路。则mk。假设vm与V(G)-V(P)中的一个结点相连，不妨设为w，则v1v2vmw为比P更长的一条基本通路。这与P是G中最长的基本通路相矛盾。因此，vm结点只能与P上的结点v1,v2,vm-1相连，故d(vm)m-1k-1，进而 d(vm)k-1，这与k矛盾。,