《连通度问题优秀PPT.ppt》由会员分享，可在线阅读，更多相关《连通度问题优秀PPT.ppt（27页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、连通度问题第一页，本课件共有27页v3.1 连通度v3.2 块v3.3 可靠通信网的建设链接链接链接第二页，本课件共有27页3.1 连通度第三页，本课件共有27页B E(G)为图G的k-边割边割 B=k。图G的边连通度边连通度（edge connectivity）=使G变成不连通或平凡图所需去 掉的最少边数。(易见，当G为非平凡连通图时，=G的最小键的边数。)第四页，本课件共有27页例:=0 G平凡或不连通。=1 G连通且含割边。(Kn)=n-1 (n 0)。当G为简单图时，=-1 G K 。=2=1,=2 =1,=2=0=0=2,=3 第五页，本课件共有27页v称 图G为 k-边连通的边连通
2、的（k-edge connected）(G)k 至少去掉k条边才能使G变成不连通或平凡图。v例如，所有非平凡连通图都是 1-边连通的。第六页，本课件共有27页v称 顶点子集V为G的顶点割顶点割(vertex cut)G-V 不连通。v称 顶点子集V为G的k-(顶顶)点割点割(vertex cut)V为G的顶点割，且 V=k。显然，当G为无环连通图时，v 为G的1-点割点割 v为G的 割点割点。完全图无点割。第七页，本课件共有27页v图G的连通度连通度(connectivity)（=使G变成不连通或平凡图所需去掉的最少的顶点数。）v例:当 3时，=1G连通且有1-点割。(K)=-1。(G)=-1
3、 G的基础简单图为完全图。第八页，本课件共有27页v称 图G为k-连通的连通的（k-connected）(G)k 至少去掉k个顶点才能使G变成不连通或平凡图。v例如，所有非平凡连通图都是 1-连通的。第九页，本课件共有27页定理定理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为
4、G的点割，从而 S -1。(ii)若H 连通，则e=xy 为H的割边。但，(H)=(G)-S -(-1)3，因此，x与y中至少有一个为H的割点，设为 x。于是S x 为G的点割，故 S +1 。第十页，本课件共有27页习题习题v3.1.1(a)证明：若G是k-边连通的，且k 0，又E为G的任k条边的集合，则 （G-E)2。(b)对 k 0，找出一个k-连通图G以及G的k个顶点的集合S，使(G-S)2。v3.1.2 证明：若G是k-边连通的，则 k/2 。v3.1.3(a)证明：若G是简单图且 -2，则 =。(b)找出一个简单图G，使得=-3且 。第十一页，本课件共有27页v3.1.4(a)证明
5、：若G是简单图且 /2，则=。(b)找出一个简单图G，使得 =（/2）-1 且 。v3.1.5 证明：若G是简单图且 (+k-2)/2(k )，则G是k连通的。v3.1.6 证明：若G是3-正则简单图，则 =。v3.1.7 证明：若l，m和n是适合0l m n的整数，则存在一个简单图G，使得 =l，=m和 =n。第十二页，本课件共有27页3.2 块 第十三页，本课件共有27页v块（块（block）无割点连通图。显然，当 v 3时，G为块 G为无环、2-连通图。v例。v 3的块中无割边。第十四页，本课件共有27页定理定理3.2 (Whiteney,1932)当当 v 3时，时，G为为2-连通图连
6、通图 G中任二顶点间则至少被两条内部不相中任二顶点间则至少被两条内部不相 交（交（internally disjoint）的路所连接。）的路所连接。（称两条路（称两条路P与与Q内部不相交内部不相交 P与与Q无公共无公共 内部顶点）内部顶点）第十五页，本课件共有27页证明：显然，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)（有好算法。）第二十七页，本课件共有27页