chap9 图的连通性

1、第九章第九章 图的连通性图的连通性观察下面四个连通图观察下面四个连通图G1G2vG3G4uG1是树，对任意边是树，对任意边eE(G1)有，有， G1-e不连通不连通u对任意对任意eE(G2)有，有， G2-e连通，但连通，但G2-v不连通不连通u对任意对任意eE(G3)、任意、任意uV(G3)有，有， G3-e 、G3-u均连通均连通uG4是完全图，连通程度比是完全图，连通程度比G3更高。更高。弱弱强强如何度量图的连通程度？如何度量图的连通程度？点连通度点连通度 边连通度边连通度9.1 点连通度和边连通度点连通度和边连通度设设G是个连通图，是个连通图，V V(G) 。如果如果G V 不连通，则

2、称不连通，则称V 为为G的一个的一个顶点割顶点割。特别，当。特别，当V = v时，称时，称v为为G的的割点割点。u实际上，实际上，顶点割顶点割是若删去它们就会使图不连通的顶点的集是若删去它们就会使图不连通的顶点的集合合，而，而割点割点是若删去此一顶点就会使图不连通的是若删去此一顶点就会使图不连通的顶点顶点。u顶点割中的顶点都是战略要地，而割点就更是兵家必争的顶点割中的顶点都是战略要地，而割点就更是兵家必争的咽喉要塞。咽喉要塞。2v1v2v3v4v5顶点割：顶点割：v3,v4,v2,v3,v1,v4,v4割点：割点：v4 点连通度点连通度定义定义9.1.1：设设G为连通的非完全图，令为连通的非完

3、全图，令 (G)=min|V | V 是是 G的顶点割的顶点割， 称称 (G)为为G的的点连通度点连通度，简称为，简称为G的连通度。的连通度。（即让（即让G不连通所需删去的最少顶点数）不连通所需删去的最少顶点数）u为统一起见，规定为统一起见，规定 (Kn)=n1，当，当G为平凡图或非为平凡图或非连通图时，连通图时， (G)=0 .uk-连通图连通图：对图：对图G，若，若 (G) k 0，则称图，则称图G为为k连通图连通图。u显然，显然，k连通图必是一个连通图必是一个(k1)连通图连通图,所有非平所有非平凡的连通图都是凡的连通图都是1连通图。连通图。3边割、割集边割、割集4边割边割割集割集边割同

4、时是割集边割同时是割集G 设设G是个连通图，是个连通图，E E(G) 。如果如果G E 不连通，不连通，则称则称E 为为G的一个的一个边割边割。特别，当。特别，当E = e时，称时，称e为为G的的割边割边。u割集割集E：若：若G的边割的边割E的任何真子集均不是的任何真子集均不是G的边割，则的边割，则称称E是是G的割集，即是的割集，即是G的极小边割。（因割集不唯一）的极小边割。（因割集不唯一）u实际上，实际上，边割边割是若删去它们就会使图不连通的边的是若删去它们就会使图不连通的边的集合集合，而而割边割边是若删去此一边就会使图不连通的是若删去此一边就会使图不连通的边边。u边割中的边都是战略要道，而

5、割边就更是要命的瓶颈。边割中的边都是战略要道，而割边就更是要命的瓶颈。边连通度边连通度定义定义9.1.2：设设G为非平凡连通图，令为非平凡连通图，令 (G)=min|E | E 是是 G的割集的割集， 称称 (G)为为G的的边连通度边连通度。（即让（即让G不连通所需删去的不连通所需删去的最少最少边边数数）u当当G为非连通图或平凡图时，规定为非连通图或平凡图时，规定 (G)=0。uk边边连通图连通图：如果如果 (G) k，则称图，则称图G为为k边边连通连通图。图。5注意：若注意：若G 连通，连通，E为割集，为割集，V为顶点割，则为顶点割，则 (G-E)=2，(G-V)2 连通度的例子连通度的例子

6、6(G4)=4 ; (G4)=4(G2)=1 ; (G2)=2(G1)=1 ; (G1)=1(G3)=3 ; (G3)=3G1G2G3G4图的连通性图的连通性思考：如何快速求出图思考：如何快速求出图G的点连通度和边连通度呢？的点连通度和边连通度呢？u图的连通性与其顶点的度数有何关系？图的连通性与其顶点的度数有何关系？u图的点连通度与边连通度有何关系？图的点连通度与边连通度有何关系？最小度最小度(G)？ (G) (G) ？ (G) = (G) ？ (G) 0,则存在断集则存在断集V1,V2,使得使得| V1,V2| = (G) .12u1u2v1v2V1GV2断集断集V1,V2=u1v1,u2v

7、2边连通度最大的充分条件边连通度最大的充分条件定理定理9.1.4 ：若简单图若简单图G(p,q)满足满足 (G) p/2 ,则则 (G) = (G)13证明思路：由定理9.1.1知(G) (G)，因此只需证明当(G) p/2时，(G) (G)不成立。（反证法）反设当(G) p/2时，(G)0。构造一个断集使得 |V1, V2|=(G) (G)（反证法，利用顶点度数之和等于2倍边数）；同理可证p2 (G)。p=p1+p2 2 ( (G) +1) 2 (G) + 1 2 p/2 + 1 p ,矛盾。 因为边连通度不大于最小度，所以此定理可因为边连通度不大于最小度，所以此定理可以看作是边连通度取最大

8、值的充分条件。以看作是边连通度取最大值的充分条件。* 9.2 块（自学）块（自学） 不可分图与块不可分图与块u定义定义9.2.1：没有割点的连通图称为不可分图。图：没有割点的连通图称为不可分图。图G的极大不可分子图称为的极大不可分子图称为G的一个块。的一个块。u例如，下图中的例如，下图中的G3和和G4是不可分图，当然也是块。是不可分图，当然也是块。 G1和和G2的块如的块如(a)、(b)所示：所示：14G1G2G3G4(a)(b)不可分图是不可分图是2连通图连通图u若图若图G是不可分的，则是不可分的，则G中无割点，所以中无割点，所以 (G) 2，G是是2连通图。反之依然。连通图。反之依然。u注

9、意注意2边连通图不一定是不可分的。如图边连通图不一定是不可分的。如图G2是是2边连通边连通图，但却存在割点，因而是可分的。图，但却存在割点，因而是可分的。15G2内不交的通路内不交的通路u定义定义9.2.2：设通路：设通路P、Q是图是图G中的两条中的两条(u,v) 通通路，如果除端点路，如果除端点u，v外，外，P和和Q没有其他公共顶点，没有其他公共顶点，则称则称P和和Q内部不相交，简称内不交。内部不相交，简称内不交。u所谓内不交的两条通路是两条相互独立的通路，所谓内不交的两条通路是两条相互独立的通路，当其中一条通路上的顶点发生故障时，另一条通当其中一条通路上的顶点发生故障时，另一条通路不会受到

10、任何的影响，从而保障了两点之间的路不会受到任何的影响，从而保障了两点之间的连续。而两条内部相交的通路就不一定能保证这连续。而两条内部相交的通路就不一定能保证这一点。一点。16不可分图的充分条件不可分图的充分条件u引理引理9.2.1：设：设G(p,q)是一个是一个p 3的图。若的图。若G的任意的任意两个顶点至少由两条内不交的通路所连通，则两个顶点至少由两条内不交的通路所连通，则G是不可分图是不可分图(2连通图连通图)。u证明：设证明：设G的任意两个顶点至少由两条内不交的的任意两个顶点至少由两条内不交的通路所连通，则通路所连通，则G显然是连通的，并且显然是连通的，并且G 的任意的任意一个顶点都不是

11、割点，故一个顶点都不是割点，故G是不可分图。是不可分图。17 注意：通路的内不交内不交很重要。如果有两条通路，但不是内不交，则不能保证G是不可分图。见右图：不可分图的必要条件不可分图的必要条件u引理引理9.2.2：设：设G(p,q)是是p 3的图，若的图，若G是不可分图，是不可分图，则则G的任意两个顶点间至少有两条内不交的通路。的任意两个顶点间至少有两条内不交的通路。u证明：若证明：若G是不可分图，任取是不可分图，任取u、vV(G)。以下。以下对顶点对顶点u与与v的距离的距离d(u,v)作归纳证明：作归纳证明：G中至少存中至少存在两条内不交的在两条内不交的(u,v) 通路。通路。u归纳基础：当

12、归纳基础：当d(u,v)=1时，即时，即e=uvE(G)，由，由G的的假设知，假设知，e不是割边不是割边(否则否则G有割点有割点)，于是，于是G e仍仍连通，从而，连通，从而， G e中中(当然也是当然也是G中中)的的(u,v)通路通路与通路与通路e=uv构成构成G中两条内不交的中两条内不交的(u,v) 通路。通路。18不可分图的必要条件不可分图的必要条件u引理引理9.2.2：设：设G(p,q)是是p 3的图，若的图，若G是不可分图，是不可分图，则则G的任意两个顶点间至少有两条内不交的通路。的任意两个顶点间至少有两条内不交的通路。u证明：证明： 19 归纳步骤：假设对d(u,v)1，求最优的，

13、求最优的k-连通生成子图的通用连通生成子图的通用算法算法目前还没有目前还没有。26Kp的最小的最小k-连通生成子图连通生成子图u将问题简化为将问题简化为G是一个各边权均为是一个各边权均为1的完全图的完全图(实实际是不考虑权际是不考虑权)，即，简化为求，即，简化为求Kp的最小权的最小权k-连通连通生成子图。生成子图。u对各边对各边权值相等的赋权完全图权值相等的赋权完全图G(p,q) , G的具有最的具有最小权的小权的k-连通生成子图显然是一个连通生成子图显然是一个边最少边最少的的k-连连通图通图G1(p, q1)。27求边最少的求边最少的k-连通图连通图G1(p, q1)设图设图G (p, q)

14、的的k 连通生成子图为连通生成子图为G1(p, q1)。 28回顾：回顾：定理定理9.1.2 任何图任何图G(p,q)，有，有 (G) (G) 2q/p 思考：思考：q1的最小值是多少呢？的最小值是多少呢？ Kp的最小的最小k 连通生成子图连通生成子图Hk,pu29Hk,p的结构与的结构与k和和p的奇偶性有关。的奇偶性有关。下面我们分别进行构造，并设下面我们分别进行构造，并设V(Hk,p)=0,1, , p-1。 问题：已知问题：已知k、p，如何构造，如何构造Hk,p呢？呢？ 构造构造H2r,pu当当k是偶数时，设是偶数时，设k=2r。构造。构造H2r,p如下：如下：对任意对任意i, jV(H

15、2r,p)，i与与j邻接当且仅当邻接当且仅当|ij| r ,或者或者 |ij| r，其中其中i i (mod p) , j j (mod p) （即即i i和和j j均被均被p整除整除）。30n H(2r, p) ； for(i=0;i=p-2;i+) for(j=i+1;j21-5=22, 15i = 2:3-2=12, 234-2=22, 24i = 3:4-3=12, 345-3=22, 35i = 4:5-4=12, 45r = 2|E(H4,6)|=12=46/2= kp/23-0=323-1=22, 135-2=32构造构造H2r+1,2su当当k是奇数，是奇数，p为偶数时，设为偶

16、数时，设k=2r+1，p=2s。构造。构造H2r+1,2s如下：如下：构造构造H2r, 2s；连接连接i与与i+p/2(mod p) (即对面的顶点即对面的顶点) ，1is 。32n H(2r+1, 2s) ： H(2r, 2s) ； /构造构造H2r,p for (i=1;i=s;i+)/连接对面的顶点连接对面的顶点 j=i+s(mod p)； 连接连接i和和j； 从算法中可以清楚地看到每个顶点的度为从算法中可以清楚地看到每个顶点的度为2r+1。2q1=p(2r+1)=pk，q1=kp/2构造构造H5,633051234H4,6：i=1：连接1与4（1+3(mod 6)）i=2：连接2与5（

17、2+3(mod 6)）i=3：连接3与0（3+3(mod 6)）H5,6：r=2，s=3|E(H5,6)| =15=56/2=kp/2构造构造H2r+1, 2s+1u当当k与与p均为奇数时，设均为奇数时，设k=2r+1，p=2s+1。构造。构造H2r+1, 2s+1如下：如下：构造图H2r,p；连接i与i+s+1(mod p)(右斜对面的顶点)，1 is；连接0与s和s+1 (0的斜对面的两个顶点) 。34n H(2r+1, 2s+1) ： H(2r, 2s+1) ；/构造构造H2r, p for (i=1;is;i+) /连接右斜对面的顶点连接右斜对面的顶点 j= i+s+1(mod p)；

18、连接；连接i和和j； 连接连接0和和s；连接；连接0和和s+1; /连接连接0与斜对面顶点与斜对面顶点 显然，除显然，除0的度为的度为2r+2外，其它顶点度均为外，其它顶点度均为2r+1。2q1=(p-1)(2r+1)+2r+2=pk+1，q1=(kp+1)/2构造构造H5,7350123456H4,7:i=1, 连接1和5 /1+3+1(mod 7)i=2, 连接2和6 /2+3+1(mod 7)连接0和3 /(0+3)连接0和4 /(0+3+1)H5,7:|E(H5,7)|=18=(57+1)/2=(kp+1)/2图图Hk,p是是 k 连通的连通的(1)定理定理9.3.1(Harary,1

19、962) 图图Hk,p是是 k 连通的。连通的。证明：证明：(先证先证k=2r时时 (H k,p ) k，反证法，反证法)u假设假设V*是顶点割且是顶点割且| V* |2r ，则则H 2r,p V*至少有至少有两个连通分支两个连通分支HV1和和 HV2。设。设i V1, j V2 (于于是是i与与j不连通），不连通），令令 S=i,i+1, ,j1, j ；T=j,j+1, ,i1, i ， 其中加法取模其中加法取模p。 36例如：取例如：取i=2，j=5，p=7，则，则 S=2, 3, 4, 5， T=5, 6, 7, 1, 2注意：注意：S和和T除除i和和j外没有其他共同的顶点。外没有其他

20、共同的顶点。图图Hk,p是是 k 连通的连通的(2)37若若|V*S| r，则考虑，则考虑T，必有，必有|V*T| r) 。 于是在于是在SV*中有一个顶点不重复的序列：中有一个顶点不重复的序列：i1= i , i2 , im= j ,使得使得|ihih+1| r ,其中其中1 h m 1。但由但由H 2r,p 的构造，这样的序列是的构造，这样的序列是 H2r,p V*中的中的一条一条(i,j) 通路。即通路。即i , j仍连通，这与假设相矛盾，仍连通，这与假设相矛盾，因此，因此，H 2r,p 是是 k 连通的。连通的。 对于对于k=2r+1的情形，也可用类似的方法来证明的情形，也可用类似的方

21、法来证明H 2r+1,p 是是 k 连通的。连通的。证明：证明：(续前续前)由于由于|V*| 2r ，所以不妨设所以不妨设|V*S| r。即在即在S中去掉属于中去掉属于V*的顶的顶点，去掉的顶点数少于点，去掉的顶点数少于r。|V*S|r，使得S-V*中各相邻顶点的编号的差的绝对值仍能小于或等于r。例如：S=1,2, , ,5,6,7,8,9,10，r=3，则在S中去掉2个顶点后仍能保持|ij-ij+1|r。Hk,p是是边最少的边最少的 k 连通图连通图38根据根据Hk,p的构造方法，我们有：的构造方法，我们有： 对于对于H2r,p ，q(H2r,p) =2rp/2 对于对于H2r+1,2s ，

22、q(H2r+1,p) =2rp/2 + s 对于对于H2r+1,2s+1 ，q(H2r+1,p) =2rp/2 + s + 1 即即q(Hk,p)= kp/2 ，由于，由于f(k,p)定义为边数最少定义为边数最少的的k连通图的边数连通图的边数,f(k,p)q(Hk,p)= kp/2 ， 又由又由(9.1)式式 f(k,p) kp/2 知，知， f(k,p)= kp/2 ，所以所以 Hk,p是是p个顶点的边最少的个顶点的边最少的 k 连通图，连通图，附录附录u定理定理9.1.1的详细证明的详细证明证明：证明：（首先将（首先将G按连通性和平凡性进行分类）按连通性和平凡性进行分类）n如果图如果图G是

23、不连通图或者是平凡图，则是不连通图或者是平凡图，则 (G)= (G)=0 (G)；n不妨设不妨设G是非平凡连通图。是非平凡连通图。先证先证 (G) (G)。取取uV(G),使使d(u)= (G)。设：设：E=eE(G)|e与与u关联关联，显然显然G-E不连通，故不连通，故E是是G的边割，由的边割，由 (G)的定义知：的定义知： (G) |E| (G)，所以，所以 (G) (G)定理定理9.1.1：对任何图对任何图G，恒有，恒有 (G) (G) (G)。（点连通度（点连通度 边连通度边连通度 顶点最小度）顶点最小度）点连通度不大于边连通度点连通度不大于边连通度(1)40边割边割E割集是割集是G的极小边割的极小边割G (G)是是 |最小割集最小割集| 点连通度不大于边连通度点连通度不大于边连通度(2) 再再证证 (G) (G) (2)。当当 (G)=1时，