[理学]连通性.ppt

连通性 四川师范大学数学与软件科学学院 周思波 本章内容简介 图的连通性是一个图所具有的基本属性之一， 目前已有多种函数用来度量图的连通性，诸如点连通度数 κ(G)，边连通度函数λ(G)，局部点、边连通度函数κ(x,y)及λ(x,y)等等． 图的连通性理论的主要目的之一是研究点连通度和边连通度的各种性质及相互联系，我们在本章的§3.l中主要介绍这方面最基本的内容． 块是图连通性方面最基本的概念，我们在本章§3.2中给出块的概念及其基本特征． 在§3.3中，我们介绍连通性的最基本、最重要的定理——Menger定理，它是有关连通性问题的理论基础． §3.4中对极小k-连通图的概念及性质给予简单介绍． 点连通度和边连通度 G1是树，它是最小连通图，舍弃任何一条边都使它不连通，G2中舍弃任何一边仍然连通，但存在这样一点，舍弃它后却会使图不连通；G3中舍弃任何一边或任何一点都不能使它不连通，而G4是连通性最强的图。由此可见，这四个5阶图的连通程度存在差异．现在我们定义图的两个参数：图的(点)连通度和边连通度，用来衡量一个图的连通程度． 点连通度的定义 G是连通图,若V(G)的子集V’使G-V’是不连通图,则V’称为G的一个顶点割(亦称点截集),若|V’|=k，则V’称为k-顶点割。当V’={v}时，v点称为G的割点。 当G≠Kn时，定义图G的(点)连通度κ(G)为：κ(G)=min{|V’||V’是G的顶点割}。 当G=Kn时，定义κ(G)=n-1 当G为平凡图或非连通图，定义κ(G)=0 对于非负整数k，如果κ(G) ≥k，那么把G称为k-连通图。显然，一个k-连通图必为(k-1)-连通图，所有非平凡的连通图都是1-连通图。 边连通度的定义 G是连通图,若E(G)的子集E’使G-E’是不连通图,则E’称为G的一个边割(亦称边截集),若|E’|=k，则E’称为k-边割。当E’={e}时，e点称为G的割边。 当G为非平凡图时，定义图G的边连通度λ(G)为：λ(G)=min{|E’||E’是G的边割}。 当G为平凡图或非连通图，定义λ(G)=0 对于非负整数k，如果λ(G) ≥k，那么把G称为k-边连通图。所有非平凡的连通图都是1-边连通图。 练习 对下列二图各作出两个点截集，并确定点连通度κ(G)和边连通度λ(G) 。 定理3.1 对任何一个图G，κ(G) ≤λ(G) ≤δ(G) 证 若G不连通，则κ(G) =λ(G) =0，结论成立。下面设G为连通图。 首先证明λ(G) ≤δ(G)。若G是平凡图，则λ(G)=0 ≤δ(G)，若G非平凡，则因每一顶点的所有关联边构成一个边割，故λ(G) ≤δ(G)。 其次证明κ(G) ≤λ(G) 。当λ(G) =1时，G有一个割边，显然这时κ(G) =1； 当G=Kn时，λ(G) =n-1，此时，按定义κ(G) =n-1； 当λ(G)＞1而G非完全图时，不妨设n≥3．注意到若E1是含λ(G)条边的割集，则G-E1必定恰有两个连通分支．可以断言，在两个连通分支中各有一点vi ,vj，使得边(vi ,vj)不属于E(G)(不然地话，设一个连通分支含m个顶点，另一个含n-m个顶点，则λ(G)＝m(n-m)，由于(m-1)(n-m-1)≥0， 即m(n-m)-m-(n-m)+1≥0，于是λ(G)≥ m+(n-m)-1＝n-1，这与G不是完全图矛盾)． 对E1中λ(G)条边的每一条边，取一个异于vi ,vj的端点，从而得到至多含λ(G)个点的集合V1(vi ,vj )不属于V1)，把V1从G中舍弃也就是把E1从G中舍弃，于是G不连通，故κ(G) ≤λ(G) 。 证法二：用数学归纳法证明κ(G) ≤λ(G) 当δ(G)=0或1时，显然κ(G) =λ(G) 若对所有λ(G) =λ0≥2的图G，有κ(G) ≤λ(G) 。今设λ(H) =λ0 +1，T是H的一个割集，且|T|=λ0 +1。若边e=(u,v) ∈T，易知H-e有一个顶点割S，|S|≤λ0但此时S∪{u}就是H的一个顶点割，即 κ(H)≤|S∪{u}|≤λ0 +1=λ(H) 由归纳法原理知，对任何λ，κ(G) ≤λ(G) κ(G) ≤λ(G) ≤δ(G)常严格成立，例如下图 练习 试作出一个连通图G，使之满足等式κ(G) =λ(G) =δ(G) 引理3.2 若δ(G)≥[n/2]，则G连通。 证 若G不连通，因为δ(G)≥[n/2]，所以每个连通分支至少有[n/2]+1个顶点，即[(n+2)/2]个顶点，但[(n+2)/2]≥(n+1)/2，于是G至少有(n+1)个顶点，矛盾。 定理3.3 若δ(G)≥[n/2]，则λ(G)=δ(G) 定理3.4 对任何(p,q)图G，有 练习 1.(a)证明：若G是k-边连通的，且k0，又若E’