资源描述
第16讲 连通度1.点(边)割集,点连通度,边连通度2.Whitney定理,简单连通图,之间的关系3.2-连通,2-边连通的充要条件4.割点,桥,块的充要条件2024/7/81集合论与图论第16讲如何定义连通度问题:如何定量比较无向图连通性的强与弱?2024/7/82集合论与图论第16讲如何定义连通度点连通度:为了破坏连通性,至少需要删除多少个顶点?边连通度:为了破坏连通性,至少需要删除多少条边?说明:“破坏连通性”指 p(G-V)p(G),或p(G-E)p(G),即“变得更加不连通”2024/7/83集合论与图论第16讲割集(cutset)点割集(vertex cut)边割集(edge cut)割点(cut vertex)割边(cut edge)(桥)(bridge)2024/7/84集合论与图论第16讲点割集(vertex cutset)点割集:无向图G=,VV,满足 (1)p(G-V)p(G);(2)极小性:VV,p(G-V)=p(G),则称V为点割集.说明:“极小性”是为了保证点割集概念的非平凡性2024/7/85集合论与图论第16讲点割集(举例)G1:f,a,e,c,g,k,j,b,e,f,k,hG2:f,a,e,c,g,k,j,b,e,f,k,habcdfeghkjiabcefdjighkG1G22024/7/86集合论与图论第16讲割点(cut-point/cut-vertex)割点:v是割点 v是割集例:G1中f是割点,G2中无割点 abcdfeghkjiabcefdjighkG1G22024/7/87集合论与图论第16讲边割集(edge cutset)边割集:无向图G=,EE,满足 (1)p(G-E)p(G);(2)极小性:EE,p(G-E)=p(G),则称E为边割集.说明:“极小性”是为了保证边割集概念的非平凡性2024/7/88集合论与图论第16讲边割集(举例)G1:(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)G2:(b,a),(b,e),(b,c)abcdfeghkjiabcefdjighkG1G22024/7/89集合论与图论第16讲割边(cut-edge)(桥)割边:(u,v)是割边 (u,v)是边割集例:G1中(f,g)是桥,G2中无桥 abcdfelhkjiabcefdjighkG1G2g2024/7/810集合论与图论第16讲扇形割集(fan cutset)IG(v)不一定是边割集(不一定极小)IG(v)不是边割集 v是割点扇形割集:E是边割集EIG(v)例:(a,g),(a,b),(g,a),(g,b),(g,c),(c,d),(d,e),(d,f),(a,b),(g,b),(g,c)abcgdfe2024/7/811集合论与图论第16讲点连通度(vertex-connectivity)点连通度:G是无向连通非完全图,(G)=min|V|V是G的点割集 规定:(Kn)=n-1,G非连通:(G)=0例:(G)=1,(H)=2,(F)=3,(K5)=4 GHF2024/7/812集合论与图论第16讲边连通度(edge-connectivity)边连通度:G是无向连通图,(G)=min|E|E是G的边割集 规定:G非连通:(G)=0例:(G)=1,(H)=2,(F)=3,(K5)=4GHF2024/7/813集合论与图论第16讲k-连通图,k-边连通图k-连通图(k-connected):(G)kk-边连通图(k-edge-connected):(G)k 例:彼得森图=3,=3;它是1-连通图,2-连通图,3-连通图,但不是4-连通图;它是1-边连通图,2-边连通图,3-边连通图,但不是4-边连通图2024/7/814集合论与图论第16讲Whitney定理定理10:.证明:不妨设G是3阶以上连通简单非完全图.()设d(v)=,则|IG(v)|=,IG(v)中一定有边割集E,所以|E|IG(v)|=.()设E是边割集,|E|=,从V(E)中找出点割集V,使得|V|,所以|V|.2024/7/815集合论与图论第16讲引理1引理1:设E是边割集,则p(G-E)=p(G)+1.证明:如果p(G-E)p(G)+1,则E不是边割集,因为不满足定义中的极小性.#说明:点割集无此性质2024/7/816集合论与图论第16讲引理2引理2:设E是非完全图G的边割集,(G)=|E|,G-E的2个连通分支是G1,G2,则存在uV(G1),vV(G2),使得(u,v)E(G)证明:(反证)否则(G)=|E|=|V(G1)|V(G2)|V(G1)|+|V(G2)|-1=n-1,与G非完全图相矛盾!#说明:a1b1(a-1)(b-1)=ab-a-b+10 aba+b-1.2024/7/817集合论与图论第16讲Whitney定理(续)证明(续):()设G-E的2个连通分支是G1,G2.设uV(G1),vV(G2),使得(u,v)E(G).如下构造V:eE,选择e的异于u,v的一个端点放入V.|V|E|.G-VG-E=G1G2,u和v在G-V中不连通,所以V中含有点割集V.所以|V|V|E|=.#uv2024/7/818集合论与图论第16讲推论推论:k-连通图一定是k-边连通图.#2024/7/819集合论与图论第16讲Hassler Whitney(19071989)美国数学家,曾获得Wolf奖 主要研究拓扑学.20世纪30年代发表了十几篇图论论文,定义了“对偶图”概念,推动了四色定理的研究.一生的最后20年致力于数学教育,提倡应当让年轻人用自己的直觉(intuition)来解决问题,而不是教一些与他们的经验无关的技巧和结果.2024/7/820集合论与图论第16讲Whitney的看法应当让年轻人用自己的直觉(intuition)来解决问题,而不是教一些与他们的经验无关的技巧和结果.什么是直觉?-习惯成自然,熟能生巧骑自行车:“平衡感”游泳:“水感”学外语:“语感”如何取得经验?-自己动手练习!不能只听不做.2024/7/821集合论与图论第16讲简单连通图的,定理14:n阶简单连通图的,之间关系有且仅有3种可能:(1)=n-1 (2)1 2-n+2 =n-2 (3)0 n/2证明:(有):构造出满足上述关系的图(仅有):任意简单连通图G可以归入以上3类2024/7/822集合论与图论第16讲定理14(有)(1)证明:(有):(1)=n-1.令 G=Kn即可.注意:(K1)=(K1)=(K1)=0,但是K1连通,所以,非连通 =0,反之不然2024/7/823集合论与图论第16讲定理14(有)(2)证明:(有)(2)12-n+2=n-2令 r=(n-)/2,s=(n-1)/2,则r+s=n-1.令 G=K+(KrKs).给G增加顶点v,使得 v与K中所有顶点相邻,与Ks中-个顶点相邻,就得到G.K Kr Ks K-v2024/7/824集合论与图论第16讲定理14(有)(2)(续)证明:(有)(2)(分析)(G)=:K:d(u)=-1+r+s+1=n-1,Kr:d(u)=r-1+,Ks:d(u)=s-1+,v:d(v)=.K Kr Ks K-v2024/7/825集合论与图论第16讲定理14(有)(2)(续)证明:(有)(2)(分析)(G)=:删除K.(G)=:删除IG(v).K Kr Ks K-v2024/7/826集合论与图论第16讲定理14(有)(3)证明:(有)(3)0 n/2令G=K+1Kn-1,设V(K+1)=u1,u2,u+1,V(Kn-1)=v1,v2,vn-1,给G增加边(ui,vi),i=1,2,以及(u1,vi),i=2,3,-+1,就得到G.Kn-1 K+1122-+1 2024/7/827集合论与图论第16讲定理14(有)(3)(续)证明:(有)(3)(分析):(G)=:K+1:d(u),Kn-1:d(u)n-2.(G)=:删除 ui|i=1,2,(G)=:删除(ui,vi)|i=1,2,(u1,vi)|i=2,3,-+1 Kn-1 K+1u1u2uv2v-+1 2024/7/828集合论与图论第16讲定理14(仅有)(1)证明:(仅有):(1)如果G是完全图,则 G=Kn,所以 =n-1.2024/7/829集合论与图论第16讲定理11定理11:G是n阶简单无向连通图,(G)(G),则存在G*以G为生成子图,G*由完全图Kn1和Kn2,以及它们之间的(G)条边组成,(G)+2n1n/2.Kn1Kn22024/7/830集合论与图论第16讲定理11(证明)证明:设E1是G的边割集,|E1|=(G).设G-E1的2个连通分支是G1与G2,|V(G1)|=n1,|V(G2)|=n2,不妨设n1n2,显然n1+n2=n,n1n/2.给G1加新边使它成为Kn1,给G2加新边使它成为Kn2,令G*=Kn1E1Kn2.G1G2E1Kn1Kn22024/7/831集合论与图论第16讲定理11(证明)证明(续):(G)(G)(G*)n1-1+(G)/n1(G)0(G)n1 (G)n1-1.(G)=n1-1 (G)=n1-1+(G)/n1(G)(G)(G*)(G)(矛盾!)(G)n1-1 (G)n1-2 (G)+2n1.#2024/7/832集合论与图论第16讲推论推论:(1)(G)(G*)n1-1n/2-1 (2)G*中有不相邻顶点u,v,使得dG*(u)+dG*(v)n-2 (3)d(G)d(G*)3证明:(2)uG1,vG2,在G中不相邻,则在G*中仍然不相邻.(3)d(G)=max d(u,v)(G)n1-2#2024/7/833集合论与图论第16讲定理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).#2024/7/834集合论与图论第16讲定理13定理13:G是n阶简单连通无向非完全图,则 2(G)-n+2 (G).证明:设V1是G的点割集,|V1|=(G),设G-V1的连通分支是G1,G2,Gs(s2),设|V(G1)|=n1,|V(G2)|+|V(Gs)|=n2,则n1+n2+(G)=n.G1G2Gs2024/7/835集合论与图论第16讲定理13(续)证明(续):(G)n1-1+(G)=n1+(G)-1,同理 (G)n2+(G)-1,所以 2(G)n1+(G)+n2+(G)-2=n+(G)-2,即(G)2(G)-n+2.#G1G2Gs2024/7/836集合论与图论第16讲定理14(仅有)(2)(3)证明:(仅有):(2)n/2时,定理12,13.(3)n/2时,定理10.#2024/7/837集合论与图论第16讲2-连通的充分必要条件定理15:3阶以上无向简单连通图G是2-连通图 G中任意两个顶点共圈独立(independent)路径:两条除起点和终点外无其他公共顶点的路径定理15:3阶以上无向简单连通图G是2-连通图 G中任意两个顶点之间有两条以上独立路径2024/7/838集合论与图论第16讲定理15(证明)定理15:3阶以上无向简单连通图G是2-连通图 G中任意两个顶点之间有两条以上独立路径证明:()显然G是连通的,并且删除任何一个顶点不破坏连通性,所以2.()分情况讨论:在两个顶点之间有 (1)1条路径(2)2条路径(3)3条路径 (4)4以上条路径2024/7/839集合论与图论第16讲定理15(证明)证明(续):()(1)一条路径:不可能 (2)两条路径 (2a)独立:OK (2b)非独立:不可能 (3)3条路径:假设两两非独立,否则同(2a)2024/7/840集合论与图论第16讲定理15(证明)证明(续):()3条路径(3a)3路径有1个公共交点:不可能(3b)有2个交点:同(2a)有2条独立路径(3c)有3个以上交点:产生2条独立路径(4)4条以上路径:同(3).#2024/7/841集合论与图论第16讲2-边连通的充分必要条件定理16:3阶以上无向图G是2-边连通图 G中任意两个顶点共简单回路边不交(edge-disjoint)路径:两条无公共边(但可能有公共顶点)的路径定理16:3阶以上无向图G是2-边连通图 G中任意两个顶点之间有两条以上边不交路径2024/7/842集合论与图论第16讲定理16(证明)定理16:3阶以上无向简单连通图G是2-边连通图 G中任意两个顶点之间有2条以上边不交路径证明:()显然G是连通的,并且删除任何一条边不破坏连通性,所以2.()分情况讨论:在两个顶点之间有 (1)1条路径(2)2条路径(3)3条路径 (4)4以上条路径2024/7/843集合论与图论第16讲定理16(证明)证明(续):()(1)一条路径:不可能(2)两条路径 (2a)边不交:OK (2b)有公共边:不可能(3)3条路径:假设两两有公共边,否则同(2a)2024/7/844集合论与图论第16讲定理16(证明)证明(续):()3条路径(3a)有1条公共边:不可能(3b)有2条公共边:同(2a)(3c)有3条以上公共边:产生2条边不交路径(4)4条以上路径:同(3).#2024/7/845集合论与图论第16讲定理16(其他证明)证明:()利用定理15和“块”.#块(block):极大无割点连通子图2024/7/846集合论与图论第16讲k-(边)连通的充分必要条件定理:3阶以上无向图G是k-连通图 G中任意两个顶点之间有k条以上独立路径定理:3阶以上无向图G是k-边连通图 G中任意两个顶点之间有k条以上边不交路径2024/7/847集合论与图论第16讲割点的充分必要条件定理17:无向连通图G中顶点v是割点 可以把V(G)-v划分成V1与V2,使得从V1中任意顶点u到V2中任意顶点w的路径都要经过v.#vuwV1V22024/7/848集合论与图论第16讲割点的充分必要条件推论:无向连通图G中顶点v是割点 存在与v不同的顶点u和w,使得从顶点u到w的路径都要经过v.#vuw2024/7/849集合论与图论第16讲桥的充分必要条件定理18:无向连通图G中边e是桥 G的任何圈都不经过e.#定理19:无向连通图G中边e是桥 可以把V(G)划分成V1与V2,使得从V1中任意顶点u到V2中任意顶点v的路径都要经过e.#euvV1V22024/7/850集合论与图论第16讲块的充分必要条件定理20:G是3阶以上无向简单连通图.则 G是块 G中任意2顶点共圈 G中任意1顶点与任意1边共圈 G中任意2边共圈 G中任意2顶点与任意1边,有路径连接这2顶点并经过这1边 G中任意3顶点,有路径连接其中2顶点并经过第3点 G中任意3顶点,有路径连接其中2顶点并不经过第3点.#2024/7/851集合论与图论第16讲比较块:极大无割点连通子图2-连通图:2,或连通无割点2-边连通图:2,或连通无桥K2是块,但不是2-(边)连通图2-连通图 2-边连通图 块2024/7/852集合论与图论第16讲总结点割集,边割集,割点,桥,块点连通度,边连通度,Whitney定理连通简单图,之间的关系2-连通,2-边连通的充要条件割点,桥,块的充要条件2024/7/853集合论与图论第16讲作业(#12)p214,习题七,17,18,22(n2,连通),23(图族)2024/7/854集合论与图论第16讲
展开阅读全文