(49)--5.5 无向图的连通性.ppt

《(49)--5.5 无向图的连通性.ppt》由会员分享，可在线阅读，更多相关《(49)--5.5 无向图的连通性.ppt（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、无向图的连通性n给定图G=，一条通路是一个点与边的有限非空交替序列=v0e1v1e2ekvk其中viV,i=1,2,k;ej=（vj-1,vj）E,j=1,2,knv0是 的起点，vk是 的终点，k称为 的长度，简单图中，一条通路也可以用结点的序列=v0v1v2vk来表示。1、通路与回路n在通路 中，若v0=vk时，称 为回路或环。n在通路/回路 中，若eiej(i j)，称 是简单通路/回路。n在通路/回路 中，若vivj(i j)，称 是初级通路/回路，初级回路也称作圈。1、通路与回路v4v3v2e1e2e3e4e5e6v1例例：列举下图的各种通路和回路。：列举下图的各种通路和回路。1：v

2、3e5v2e4v3e5v2e1v1通路，长度4 2：v3e4v2e5v3e6v4e2v1简单通路，长度4 3：v3e5v2e1v1初级通路，简单通路，长度2 4：v2e4v3e5v2e1v1e3v2简单回路，长度4 5：v2e4v3e5v2初级回路，简单回路，长度2n一条通路如果是初级的，则必是简单的。n两个结点之间若有通路存在，则必有初级通路存在。1、通路与回路n在一个n阶图中，如果从结点vi到vj(vi vj)存在通路，则从vi到vj存在长度不超过n1的通路。n在一个n阶图中，如果从结点vi到vi存在回路，则从vi到vi存在长度不超过n的回路。n在一个n阶图G中任何初级通路的长度均不大于n

3、1；任何初级回路的长度均不大于n。2、通路与回路的性质在一个n阶图中，如果从结点vi到vj(vi vj)存在通路，则从vi到vj存在长度不超过n1的通路。证明：设vi vk vj为vi到vj的长度为L的一条通路，则序列中必有L+1个结点。如果Ln1，则此通路的结点数L+1n，从而必有结点vs，它在序列中不止出现一次，即有序列vi vs vs vj。在上述通路中，vs vs是一条回路，去掉回路中的这些边后仍是vi到vj的一条通路。此通路比原来通路长度至少减少1。如此重复下去，必可得到一条从vi到vj的不多于n1条边的通路。2、通路与回路的性质n无向图G=,u,v V，u到v存在一条通路，则u和v

4、是连通的。n无向图G中，若vi与vj连通，则称vi与vj间长度最短的通路的长度为vi与vj之间的距离。记作d(vi,vj)。如果vi到vj不可达，则通常记为d(vi,vj)=。n图G中任何两个结点是连通的，称G为连通图；否则是分离图。3、无向图的连通性无向图中，若规定任何结点到其自身是连通的，则结点之间的连通关系是结点集V上的等价关系。n假设无向图G的结点集V在连通关系下的等价类为V1,V2,Vk，则图G关于Vi的导出子图称作图G的一个连通分支，其中i=1,2,k。p(G)表示连通分支的个数。n连通图是只有一个连通分支的无向图。P(G1)=1P(G2)=43、无向图的连通性对于图的连通性而言，

5、不同结点或边的“重要性”是不同的，比如在计算机网络中，有的结点或边出现中断，会对整个网络的连通性有至关重要的影响。点割集：无向图G=，1)若存在非空结点集V V，P(G-V)P(G)，2)而对于任意的VV，P(G-V)=P(G)，则V是G的点割集。特别地，若点割集中只有一个结点v，则称v为割点。4、无向图的割集边割集：无向图G=，1)若存在非空边集E E，P(G-E)P(G)，2)而对于任意的EE，P(G-E)=P(G)，则E是G的边割集。特别地，若边割集中只有一条边e，则称e为割边或桥。4、无向图的割集例：例：v4v3v2e1e2e3e4e5e6v1v5v6v7e7e8e9v2，v6，v3,

6、v5是是点割集点割集。v2，v6是割点。是割点。v2,v5，v6,v1都不是点割集。都不是点割集。e9,e7,e8,e6,e8,e1,e2,e5是是边割集边割集。e9是割边。是割边。e9,e8,e6,e7,e8都不是边割集。都不是边割集。4、无向图的割集设无向连通图G=，n称(G)=min|V|V为 G 的点割集为G点连通度，若(G)k,则称G为k-连通图。n称(G)=min|E|E为 G 的边割集为G边连通度，若(G)k,则称G为k边-连通图。v4v3v2e1e2e3e4e5e6v1v5v6e7e8点连通度点连通度1,是是1-连通图连通图;边连通度边连通度2,是是1边边-连通图连通图，2边边-连通连通图图。5、点连通度和边连通度THANK YOU