《集合论与图论》第16讲1 第16讲连通度 ?1. 点(边)割集,点连通度κ,边连通度λ ?2. Whitney定理, 简单连通图κ,λ,δ之间的 关系 ?3. 2-连通, 2-边连通的充要条件 ?4. 割点, 桥, 块的充要条件 《集合论与图论》第16讲2 如何定义连通度 ?问题: 如何定量比较无向图连通性的强与 弱? 《集合论与图论》第16讲3 如何定义连通度 ?点连通度: 为了破坏连通性,至少需要删 除多少个顶点? ?边连通度: 为了破坏连通性,至少需要删 除多少条边? ?说明: “破坏连通性”指p(G-V’)>p(G), 或 p(G-E’)>p(G),即“变得更加不连通” 《集合论与图论》第16讲4 割集(cutset) ?点割集(vertex cut) ?边割集(edge cut) ?割点(cut vertex) ?割边(cut edge)(桥)(bridge) 《集合论与图论》第16讲5 点割集(vertex cutset) ?点割集: 无向图G=<V,E>, ?≠V’?V, 满足 (1) p(G-V’)>p(G); (2) 极小性: ? V’’?V’, p(G-V’’)=p(G), 则称V’为点割集. ?说明: “极小性”是为了保证点割集概念的 非平凡性 《集合论与图论》第16讲6 点割集(举例) ?G 1 : {f},{a,e,c},{g,k,j},{b,e,f,k,h} ?G 2 : {f},{a,e,c},{g,k,j},{b,e,f,k,h} a b cd f e g h k ji a b c ef dj i g h k G 1 G 2 《集合论与图论》第16讲7 割点(cut-point / cut-vertex) ?割点: v是割点? {v}是割集 ?例: G 1 中f是割点, G 2 中无割点 a b cd f e g h k ji a b c ef dj i g h k G 1 G 2 《集合论与图论》第16讲8 边割集(edge cutset) ?边割集: 无向图G=<V,E>, ?≠E’?E, 满足 (1) p(G-E’)>p(G); (2) 极小性: ?E’’?E’, p(G-E’’)=p(G), 则称E’为边割集. ?说明: “极小性”是为了保证边割集概念的 非平凡性 《集合论与图论》第16讲9 边割集(举例) ?G 1 : {(a,f),(e,f),(d,f)}, {(f,g),(f,k),(j,k),(j,i)} {(a,f),(e,f),(d,f),(f,g),(f,k),(f,j)}, {(c,d)} ?G 2 : {(b,a),(b,e),(b,c)} a b cd f e g h k ji a b c ef dj i g h k G 1 G 2 《集合论与图论》第16讲10 割边(cut-edge)(桥) ?割边: (u,v)是割边? {(u,v)}是边割集 ?例: G 1 中(f,g)是桥, G 2 中无桥 a b cd f e l h k ji a b c ef dj i g h k G 1 G 2 g 《集合论与图论》第16讲11 扇形割集(fan cutset) ?I G (v)不一定是边割集(不一定极小) ?I G (v)不是边割集? v是割点 ?扇形割集: E’是边割集∧E’?I G (v) ?例: {(a,g),(a,b)},{(g,a),(g,b),(g,c)},{(c,d)}, {(d,e),(d,f)}, {(a,b),(g,b),(g,c)} a b c gd f e 《集合论与图论》第16讲12 点连通度(vertex-connectivity) ?点连通度: G是无向连通非完全图, κ(G) = min{ |V’| | V’是G的点割集} ?规定: κ(K n ) = n-1, G非连通: κ(G)=0 ?例: κ(G)=1, κ(H)=2, κ(F)=3, κ(K 5 )=4 GHF 《集合论与图论》第16讲13 边连通度(edge-connectivity) ?边连通度: G是无向连通图, λ(G) = min{ |E’| | E’是G的边割集} ?规定: G非连通: λ(G)=0 ?例: λ(G)=1, λ(H)=2, λ(F)=3, λ(K 5 )=4 GHF 《集合论与图论》第16讲14 k-连通图, k-边连通图 ?k-连通图(k-connected): κ(G)≥k ?k-边连通图(k-edge-connected): λ(G)≥k ?例: 彼得森图κ=3, λ=3; 它是1-连通图, 2-连通图,3-连通图, 但不是4-连通图; 它 是1-边连通图, 2-边连通图,3-边连通图,但 不是4-边连通图 《集合论与图论》第16讲15 Whitney定理 ?定理10: κ≤λ≤δ. ?证明: 不妨设G是3阶以上连通简单非完 全图. (λ≤δ) 设d(v)=δ, 则|I G (v)|=δ, I G (v)中一定 有边割集E’, 所以λ≤|E’|≤|I G (v)|=δ. (κ≤λ) 设E’是边割集,|E’|=λ,从V(E’)中找出 点割集V’,使得|V’|≤λ, 所以κ≤|V’|≤λ. 《集合论与图论》第16讲16 引理1 ?引理1: 设E’是边割集,则p(G-E’)=p(G)+1. ?证明: 如果p(G-E’)>p(G)+1, 则E’不是边 割集, 因为不满足定义中的极小性. # ?说明: 点割集无此性质 《集合论与图论》第16讲17 引理2 ?引理2:设E’是非完全图G的边割集, λ(G)=|E’|,G-E’的2个连通分支是G 1 ,G 2 ,则 存在u∈V(G 1 ),v∈V(G 2 ),使得(u,v)?E(G) ?证明: (反证)否则λ(G)=|E’| =|V(G 1 )|×|V(G 2 )|≥|V(G 1 )|+|V(G 2 )|-1=n-1, 与G非完全图相矛盾! # ?说明: a≥1∧b≥1?(a-1)(b-1)=ab-a-b+1≥0 ? ab≥a+b-1. 《集合论与图论》第16讲18 Whitney定理(续) ?证明(续): (κ≤λ) 设G-E’的2个连通分支是 G 1 ,G 2 . 设u∈V(G 1 ),v∈V(G 2 ),使得 (u,v)?E(G). 如下构造V’’:?e∈E’, 选择e的 异于u,v的一个端点放入V’’. |V’’|≤|E’|. G-V’’?G-E’=G 1 ∪G 2 , u和v在G-V’’中不连 通, 所以V’’中含有点割集V’. 所以κ≤|V’|≤|V’’|≤|E’|=λ. # u v 《集合论与图论》第16讲19 推论 ?推论: k-连通图一定是k-边连通图. # 《集合论与图论》第16讲20 Hassler Whitney(1907~1989) ?美国数学家,曾获得Wolf奖 ?主要研究拓扑学. 20世纪30年代发表了 十几篇图论论文,定义了“对偶图”概念,推 动了四色定理的研究. ?一生的最后20年致力于数学教育,提倡应 当让年轻人用自己的直觉(intuition)来解 决问题,而不是教一些与他们的经验无关 的技巧和结果. 《集合论与图论》第16讲21 Whitney的看法 ?应当让年轻人用自己的直觉(intuition)来 解决问题,而不是教一些与他们的经验无 关的技巧和结果. ?什么是直觉?------习惯成自然,熟能生巧 ?骑自行车: “平衡感” ?游泳: “水感” ?学外语: “语感” ?如何取得经验?------自己动手 ?练习! 不能只听不做. 《集合论与图论》第16讲22 简单连通图的κ,λ,δ ?定理14: n阶简单连通图的κ,λ,δ之间关系 有且仅有3种可能: (1) κ = λ = δ = n-1 (2) 1 ≤ 2δ-n+2 ≤κ≤λ = δ ≤ n-2 (3) 0 ≤κ≤λ≤δ< ?n/2? ?证明: (有):构造出满足上述关系的图 (仅有):任意简单连通图G可以归入以上3类 《集合论与图论》第16讲23 定理14((有)(1)) ?证明: (有): (1) κ = λ = δ = n-1. 令G = K n 即可. ?注意: κ(K 1 )=λ(K 1 )=δ(K 1 )=0, 但是K 1 连通, 所以, 非连通?κ=λ=0, 反之不然 《集合论与图论》第16讲24 定理14((有)(2)) ?证明: (有)(2)1≤2δ-n+2≤κ≤λ=δ≤n-2 令r=?(n-κ)/2?, s= ?(n-κ-1)/2?, 则r+s=n-κ-1. 令G’=K κ +(K r ∪K s ). 给G’增加顶点v, 使得 v与K κ 中所有顶点相邻, 与K s 中δ-κ个顶点 相邻, 就得到G. K κ K r K s K δ-κ v 《集合论与图论》第16讲25 定理14((有)(2)(续)) ?证明: (有)(2) (分析) δ(G)=δ: K κ : d(u)=κ-1+r+s+1=n-1≥δ, K r : d(u)=r-1+κ≥δ, K s : d(u)=s-1+κ≥δ, v: d(v)=δ. K κ K r K s K δ-κ v 《集合论与图论》第16讲26 定理14((有)(2)(续)) ?证明: (有)(2) (分析) κ(G)=κ: 删除K κ . λ(G)=λ=δ: 删除I G (v). K κ K r K s K δ-κ v 《集合论与图论》第16讲27 定理14((有)(3)) ?证明: (有)(3) 0 ≤κ≤λ≤δ< ?n/2? 令G’=K δ+1 ∪K n-δ-1 ,设V(K δ+1 )={u 1 ,u 2 ,…,u δ+1 }, V(K n-δ-1 )={v 1 ,v 2 ,…,v n-δ-1 }, 给G’增加边(u i ,v i ), i=1,2,…,κ, 以及(u 1 ,v i ), i=2,3,…,λ-κ+1, 就得到G. K n-δ-1 K δ+1 1 2 κ 2 λ-κ+1 《集合论与图论》第16讲28 定理14((有)(3)(续)) ?证明: (有)(3) (分析): δ(G)=δ: K δ+1 : d(u)≥δ, K n-δ-1 : d(u)≥n-δ-2≥δ. κ(G)=κ: 删除{ u i | i=1,2,…,κ }, λ(G)=λ: 删除{(u i ,v i )|i=1,2,…,κ}∪{(u 1 ,v i )| i=2,3,…,λ-κ+1} K n-δ-1 K δ+1 u 1 u 2 u κ v 2 v λ-κ+1 《集合论与图论》第16讲29 定理14((仅有)(1)) ?证明: (仅有): (1)如果G是完全图,则 G=K n , 所以κ = λ = δ = n-1. 《集合论与图论》第16讲30 定理11 ?定理11: G是n阶简单无向连通图, λ(G)<δ(G),则存在G*以G为生成子图,G* 由完全图K n1 和K n2 ,以及它们之间的λ(G) 条边组成, λ(G)+2≤n 1 ≤?n/2?. K n1 K n2 《集合论与图论》第16讲31 定理11(证明) ?证明: 设E 1 是G的边割集,|E 1 |=λ(G). 设G-E 1 的2个连通分支是G 1 与G 2 , |V(G 1 )|=n 1 , |V(G 2 )|=n 2 , 不妨设n 1 ≤n 2 , 显 然n 1 +n 2 =n, n 1 ≤?n/2?. 给G 1 加新边使它成为K n1 ,给G 2 加新 边使它成为K n2 , 令G*=K n1 ∪E 1 ∪K n2 . G 1 G 2 E 1 K n1 K n2 《集合论与图论》第16讲32 定理11(证明) ?证明(续): λ(G)<δ(G)≤δ(G*)≤n 1 -1+?λ(G)/n 1 ? ?λ(G)<n 1 -1+λ(G)/n 1 ? (n 1 -1)(n 1 -λ(G))>0 ?λ(G)<n 1 ?λ(G) ≤ n 1 -1. λ(G)=n 1 -1 ?λ(G)=n 1 -1+ ?λ(G)/n 1 ? ?λ(G)<δ(G)≤δ(G*)≤λ(G) (矛盾!) λ(G)<n 1 -1 ?λ(G) ≤ n 1 -2 ?λ(G)+2≤n 1 . # 《集合论与图论》第16讲33 推论 ?推论: (1) δ(G)≤δ(G*)≤n 1 -1≤?n/2?-1 (2) G*中有不相邻顶点u,v,使得 d G* (u)+d G* (v)≤n-2 (3) d(G)≥d(G*)≥3 ?证明: (2)u∈G 1 ,v∈G 2 ,在G中不相邻,则在 G*中仍然不相邻. (3) d(G)=max d(u,v) λ(G)≤n 1 -2 # 《集合论与图论》第16讲34 定理12(λ=δ的充分条件) ?定理12: G是6阶以上连通简单无向图. (1) δ(G)≥?n/2??λ(G)=δ(G) (2) 若任意一对不相邻顶点u,v都有 d(u)+d(v)≥n-1, 则λ(G)=δ(G). (3) d(G)≤2 ?λ(G)=δ(G). # 《集合论与图论》第16讲35 定理13 ?定理13: G是n阶简单连通无向非完全图, 则2δ(G)-n+2 ≤κ(G). ?证明: 设V 1 是G的点割集, |V 1 |=κ(G), 设G- V 1 的连通分支是G 1 ,G 2 ,…,G s (s≥2), 设 |V(G 1 )|=n 1 , |V(G 2 )|+…+|V(G s )|=n 2 , 则n 1 + n 2 +κ(G)=n. G 1 G 2 G s 《集合论与图论》第16讲36 定理13(续) ?证明(续): δ(G)≤n 1 -1+κ(G)=n 1 +κ(G)-1, 同理δ(G)≤n 2 +κ(G)-1, 所以 2δ(G) ≤ n 1 +κ(G)+n 2 +κ(G)-2 = n+κ(G)-2, 即κ(G) ≥ 2δ(G)-n+2. # G 1 G 2 G s 《集合论与图论》第16讲37 定理14((仅有)(2)(3)) ?证明: (仅有): (2) δ≥?n/2?时, 定理12,13. (3) δ<?n/2?时, 定理10. # 《集合论与图论》第16讲38 2-连通的充分必要条件 ?定理15: 3阶以上无向简单连通图G是2- 连通图? G中任意两个顶点共圈 ?独立(independent)路径: 两条除起点和终 点外无其他公共顶点的路径 ?定理15’: 3阶以上无向简单连通图G是2- 连通图? G中任意两个顶点之间有两条 以上独立路径 《集合论与图论》第16讲39 定理15’(证明) ?定理15’: 3阶以上无向简单连通图G是2- 连通图? G中任意两个顶点之间有两条 以上独立路径 ?证明: (?) 显然G是连通的,并且删除任何 一个顶点不破坏连通性, 所以κ≥2. (?) 分情况讨论: 在两个顶点之间有 (1)1条路径(2)2条路径(3)3条路径 (4)4以上条路径 《集合论与图论》第16讲40 定理15’(证明) ?证明(续):(?) (1)一条路径: 不可能 (2)两条路径 (2a)独立: OK (2b)非独立: 不可能 (3)3条路径: 假设两两非独立,否则同(2a) 《集合论与图论》第16讲41 定理15’(证明) ?证明(续):(?) 3条路径 (3a) 3路径有1个公共交点: 不可能 (3b) 有2个交点: 同(2a) 有2条独立路径 (3c) 有3个以上交点: 产生2条独立路径 (4) 4条以上路径: 同(3). # 《集合论与图论》第16讲42 2-边连通的充分必要条件 ?定理16: 3阶以上无向图G是2-边连通图 ? G中任意两个顶点共简单回路 ?边不交(edge-disjoint)路径: 两条无公共 边(但可能有公共顶点)的路径 ?定理16’: 3阶以上无向图G是2-边连通图 ? G中任意两个顶点之间有两条以上边 不交路径 《集合论与图论》第16讲43 定理16’(证明) ?定理16’: 3阶以上无向简单连通图G是2- 边连通图? G中任意两个顶点之间有2 条以上边不交路径 ?证明: (?) 显然G是连通的,并且删除任何 一条边不破坏连通性, 所以λ≥2. (?) 分情况讨论: 在两个顶点之间有 (1)1条路径(2)2条路径(3)3条路径 (4)4以上条路径 《集合论与图论》第16讲44 定理16’(证明) ?证明(续):(?) (1)一条路径: 不可能 (2)两条路径 (2a)边不交: OK (2b)有公共边: 不可能 (3)3条路径: 假设两两有公共边,否则同(2a) 《集合论与图论》第16讲45 定理16’(证明) ?证明(续):(?) 3条路径 (3a) 有1条公共边: 不可能 (3b) 有2条公共边: 同(2a) (3c) 有3条以上公共边: 产生2条边不交路 径 (4) 4条以上路径: 同(3). # 《集合论与图论》第16讲46 定理16’(其他证明) ?证明: (?) 利用定理15’和“块”. # ?块(block): 极大无割点连通子图 《集合论与图论》第16讲47 k-(边)连通的充分必要条件 ?定理: 3阶以上无向图G是k-连通图? G 中任意两个顶点之间有k条以上独立路径 ?定理: 3阶以上无向图G是k-边连通图? G中任意两个顶点之间有k条以上边不交 路径 《集合论与图论》第16讲48 割点的充分必要条件 ?定理17: 无向连通图G中顶点v是割点? 可以把V(G)-{v}划分成V 1 与V 2 ,使得从V 1 中任意顶点u到V 2 中任意顶点w的路径都 要经过v. # v uw V 1 V 2 《集合论与图论》第16讲49 割点的充分必要条件 ?推论: 无向连通图G中顶点v是割点?存 在与v不同的顶点u和w,使得从顶点u到w 的路径都要经过v. # v uw 《集合论与图论》第16讲50 桥的充分必要条件 ?定理18:无向连通图G中边e是桥? G的 任何圈都不经过e. # ?定理19: 无向连通图G中边e是桥?可以 把V(G)划分成V 1 与V 2 ,使得从V 1 中任意顶 点u到V 2 中任意顶点v的路径都要经过e. # e uv V 1 V 2 《集合论与图论》第16讲51 块的充分必要条件 ?定理20: G是3阶以上无向简单连通图.则 G是块? G中任意2顶点共圈? G中任 意1顶点与任意1边共圈? G中任意2边 共圈? G中任意2顶点与任意1边,有路径 连接这2顶点并经过这1边? G中任意3 顶点,有路径连接其中2顶点并经过第3点 ? G中任意3顶点,有路径连接其中2顶点 并不经过第3点. # 《集合论与图论》第16讲52 比较 ?块: 极大无割点连通子图 ?2-连通图: κ≥2, 或连通无割点 ?2-边连通图: λ≥2, 或连通无桥 ?K 2 是块, 但不是2-(边)连通图 ?2-连通图? 2-边连通图?块 《集合论与图论》第16讲53 总结 ?点割集,边割集,割点,桥, 块 ?点连通度,边连通度,Whitney定理 ?连通简单图κ,λ,δ之间的关系 ?2-连通, 2-边连通的充要条件 ?割点, 桥, 块的充要条件 《集合论与图论》第16讲54 作业(#12) ?p214, 习题七, 17,18,22(n≥2,连通),23(图 族)