第3章 连通度问题

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,下一页,上一页,目录,第三章 连通度问题,3.1,连通度,3.2,块,3.3,可靠通信网的建设,链接,链接,链接,3.1,连通度,B,E(G),为图,G,的,k-,边割,B,=k,。,图,G,的,边连通度,（,edge connectivity,）,=,使,G,变成不连通或平凡图所需去,掉的最少边数。,(,易见，当,G,为非平凡连通图时，,=G,的最小键的边数。,),例,:,=0,G,平凡或不连通。,=1,G,连通且含割边。,(,K,n,)=n-1 (n 0),。,当,G,为简单图时，,=,-1,G,K,。,k,=,k,=2,k,=1,k,=2,k,=1,k,=2,k,=,k,=0,k,=,k,=0,k,=2,k,=3,称 图,G,为,k-,边连通的,（,k-edge connected,）,(G),k,至少去掉,k,条边才能使,G,变成不连通或平凡图。,例如，所有非平凡连通图都是,1-,边连通的。,称 顶点子集,V,为,G,的,顶点割,(vertex cut),G-V,不连通。,称 顶点子集,V,为,G,的,k-(,顶,),点割,(vertex cut),V,为,G,的顶点割，且,V,=k,。,显然，当,G,为无环连通图时，,v,为,G,的,1-,点割,v,为,G,的,割点,。完全图无点割。,图,G,的,连通度,(connectivity),（,=,使,G,变成不连通或平凡图所需去掉的最少的顶点数。）,例,:,当,3,时，,=1,G,连通且有,1-,点割。,(K,)=,-1,。,(G)=,-1,G,的基础简单图为完全图。,称 图,G,为,k-,连通的,（,k-connected,）,(G),k,至少去掉,k,个顶点才能使,G,变成不连通或平凡图。,例如，所有非平凡连通图都是,1-,连通的。,定理,3.1,。,证明：先证,：当,G,为平凡图时，,0,，结论成立；当,G,为非平凡图时，选取,v,使,d(v,)=,则,E=,是,G,的一个边割，因此,结论成立。再来证,：,不妨设,G,为简单、连通、非完全图，于是,-2,。任取一,-,边割,B,，及,B,中任一边,e=,xy,。今，在,B-e,的每边上各取,一个,端点使之不等于,x,及,y,。令这些端点的集合为,S,。易见，,S,-1,。,记,H=G-S,。,(i),若,H,不连通，则,S,为,G,的点割，从而,S,-1,。,(ii),若,H,连通，则,e=,xy,为,H,的割边。但，,(H)=,(G)-,S,-(,-1),3,，,因此，,x,与,y,中至少有一个为,H,的割点，设为,x,。于是,S,x,为,G,的点割，故,S,+1,。,习题,3.1.1,(a),证明：若,G,是,k-,边连通的，且,k 0,，又,E,为,G,的任,k,条边的集合，则,（,G-E),2,。,(b),对,k 0,，找出一个,k-,连通图,G,以及,G,的,k,个顶点的集合,S,，使,(G-S)2,。,3.1.2,证明：若,G,是,k-,边连通的，则,k,/2,。,3.1.3,(a),证明：若,G,是简单图且,-2,，则,=,。,(b),找出一个简单图,G,，使得,=,-3,且,。,3.1.4,(a),证明：若,G,是简单图且,/2,，则,=,。,(b),找出一个简单图,G,，使得,=,（,/2,）,-1,且,。,3.1.5,证明：若,G,是简单图且,(,+k-2)/2(k,),，则,G,是,k,连通的。,3.1.6,证明：若,G,是,3-,正则简单图，则,=,。,3.1.7,证明：若,l,，,m,和,n,是适合,0l,m,n,的整数，则存在一个简单图,G,，使得,=l,，,=m,和,=n,。,3.2,块,块（,block,）,无割点连通图。,显然，当,v,3,时，,G,为块,G,为无环、,2-,连通图。,例。,v,3,的块中无割边。,定理,3.2 (Whiteney,1932),当,v,3,时，,G,为,2-,连通图,G,中任二顶点间则至少被两条内部不相 交（,internally disjoint,）的路所连接。（称两条路,P,与,Q,内部不相交,P,与,Q,无公共 内部顶点）,证明：,：显然，,G,连通，且无,1-,点割，因此,G,为,2-,连通。,：对,G,中二顶点间的距离,d(,),进行归纳。当,d(u,v,)=1,时（即,uv,为,G,的边），因,G,为,2-,连通，边,uv,是,G,的非割边,(,2),。因此，由定理,2.3,，边,uv,在,G,的某一 圈内，成立。,假设定理对,d(,)1,：,NP-hard prob.,。,当每边权,1,且,G,为任意图时：问题变成求边数最少的,k-,连通生成子图。,(,仍然是,NP-hard prob.),当每边权,1,且,G,K,时：,Harary,(1962),作出边数最少的,G,的,k-,连通（,k-,边连通）生成子图,Hk,（边数,=k,/2),（有好算法。）,