null第三章 连通度问题第三章 连通度问题null3.1 连通度
3.2 块
3.3 可靠通信网的建设3.1 连通度3.1 连通度nullB E(G)为图G的k-边割 B = k 。
图G的边连通度（edge connectivity）
= 使G变成不连通或平凡图所需去
掉的最少边数。
(易见，当G为非平凡连通图时， = G的最小键的边数。) null例: = 0 G平凡或不连通。
= 1 G连通且含割边。
(Kn)= n-1 ( n > 0 )。
当G为简单图时，
= -1 G K 。 null称 图G为 k-边连通的（k-edge connected）
(G) k
至少去掉k条边才能使G变成不连通或平凡图。
例如，所有非平凡连通图都是 1-边连通的。 null称 顶点子集V’为G的顶点割 (vertex cut)
G - V’ 不连通。
称 顶点子集V’为G的k-(顶)点割(vertex cut)
V’为G的顶点割，且 V’ = k 。
显然，当G为无环连通图时，
v 为G的1-点割 v为G的 割点。 完全图无点割。 null图G的连通度(connectivity)
（ = 使G变成不连通或平凡图所需去掉的最少的顶点数。）
例:当 3时， = 1G连通且有1-点割。
(K) =-1 。
(G)= -1 G的基础简单图为完全图。 null称 图G为k-连通的（k-connected）
(G) k
至少去掉k个顶点才能使G变成不连通或平凡图。
例如，所有非平凡连通图都是 1-连通的。 定理3.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且 < 。null3.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是适合0 1 ： NP-hard prob. 。
当每边权 1且G为任意图时：问题变成求边数最少的k-连通生成子图。( 仍然是NP-hard prob.)
当每边权 1 且G K时：Harary (1962)作出边数最少的G的k-连通（∴k-边连通）生成子图Hk,（边数={k/2}) （∴有好算法。）
本文档为【第3章 连通度问题】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483