我的竞赛1.题目a连通性

连通性四川师范大学数学与软件科学学院周思波本章内容简介图的连通性是一个图所具有的基本属性之一，目前已有多种函数用来度量图的连通性，诸如点连通度数κ(G)，边连通度函数λ(G)，局部点、边连通度函数κ(x,y)及λ(x,y)等等．图的连通性理论的主要目的之一是研究点连通度和边连通度的各种性质及相互联系，我们在本章的§3.l中主要介绍这方面最基本的内容．块是图连通性方面最基本的概念，我们在本章§3.2中给出块的概念及其基本特征．在§3.3中，我们介绍连通性的最基本、最重要的定理——Menger定理，它是有关连通性问题的理论基础．§3.4中对极小k-连通图的概念及性质给予简单介绍．点连通度和边连通度G1是树，它是最小连通图，舍弃任何一条边都使它不连通，G2中舍弃任何一边仍然连通，但存在这样一点，舍弃它后却会使图不连通；G3中舍弃任何一边或任何一点都不能使它不连通，而G4是连通性最强的图。由此可见，这四个5阶图的连通程度存在差异．现在我们定义图的两个参数：图的(点)连通度和边连通度，用来衡量一个图的连通程度．G1G2G3G4点连通度的定义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的圈，都有κ(G)=λ(G)=δ(G)=2完全图Kn中，有κ(G)=λ(G)=δ(G)=n-1引理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)证明：显然G是连通的。设S是G的割集，|S|=λ(G)。G1和G2是G-S的两个分支，不妨设|V(G1)|=p1≤[n/2]故G1中每个顶点至少有δ-(p1-1)条边伸向G2，故λ(G)≥p1(δ-(p1-1))又1≤p1≤δ,所以(p1-1)(δ-p1)≥0变形得p1(δ-(p1-1))≥δ，所以λ(G)≥δ(G)由定理3.1得λ(G)=δ(G)定理3.4对任何(p,q)图G，有证明：由得左端为p个顶点的算术平均值，故由定理3.1得证。练习1.(a)证明：若G是k-边连通的，且k>0，又若E’是G的k条边的一个集合，则ω(G-E’)≤2证设e∈E’，则由定义知ω((G-E’)∪e)=1(1)若e是(G-E’)∪e的割边，则ω(G-E’)=2；(2)若e不是(G-E’)∪e的割边，则ω(G-E’)=1(b)对k>0，找出一个k-连通图G以及G的k个顶点的集合V’，使ω(G-V’)>2解：构造一个Kk，再任取三个点分别与Kk的每一点相连，这就是所要求的图G，取V’=

Kk

。练习2.(a)证明：若G是简单图且δ≥p-2，则κ=δ证当δ=p-1时，G=Kp，故κ(G)=p-1=δ当δ=p-2时，若v1,v2∈V(G)不相邻，则对任意第三点v3∈V(G)有v1v3,v2v3∈E(G)。这时，对任意p-3的顶点的子集V’均有G-V’仍连通。故κ(G)≥p-2=δ，所以κ=δ(b)找出一个简单图G，使δ=p-3，且κ<δGG练习3.若G为3-正则简单图,则κ=λ证(1)若κ=0，则G不连通，故λ=0，结论成立。(2)若κ=1，则存在v∈V(G)使G-v不连通，由于dG(v)=3，从而至少存在一个分支仅一条边与v相关联。显然这条边为G的割边，故λ=1，结论成立。(3)若κ=2，设v1,v2∈V(G)，G-{v1,v2}不连通，G1=G-{v1}连通。则v2是G1的割点，且dG1(v2)≤3，类似(2)知在G1中存在一割边e2(关联于v2)使G1-e2不连通。另一方面，由定理3.1知λ≥2，故G-e2连通。由于G1-e2=(G-e2)-v1

，故v1是的割点，且dG-e2

(v1)≤3，于是由(2)知，在中存在一割边e1，即(G-e2)-e1不连通，即G-{e1,e2}不连通，所以λ=1，结论成立。(4)若κ=3，由定理3.1知λ=3，结论成立。综上得证。块没有割点的非平凡连通图称为不可分图，一个图的极大不可分子图称为块。显然，至少有三个顶点的块是2-连通的。相关定理定理3.5设G是p≥3的一个图。G是2-连通图的充要条件是：G的任意两个顶点至少由两条内部不相交的通路所连通。证充分性：若G的任意两个顶点至少由两条内部不相交的通路所连通，则显然G是连通的，并且没有割点，因此，是2-连通的。必要性：设G是2-连通的，u,v是G的任意两个顶点，我们用d(u,v)记最短(u,v)-通路中所含边数，即u,v的距离。以下对d(u,v)用数学归纳法。当d(u,v)=1时，由于G是2-连通的，所以e=uv不是割边，因此G-e仍连通，于是u,v由通路P连通，而在G中u,v除此通路外，还有一条边e所成的通路，此时结论成立。假设对距离小于k的任意两个顶点，定理成立，并设d(u,v)=k≥2，考察一条长为k的(u,v)通路。设w是这条通路上v之前的那个顶点，因为d(u,w)=k-1，由归纳假设，在G中至少有两条内部不相交的(u,w)-通路P和Q。因为G是2-连通的，所以G-w是连通的，因而有(u,v)-通路P’。P’与P、Q的关系不外三种情况。(1)P’与P∪Q不相交，P’及P+(w,v)即为所求。(2)P’与P∪Q相交，x是距v点最近的P’与P∪Q的交点，x在P上。于是连接u,v有两条不相交通路，一条是P上的(u,x)一节及P’上的(x,v)一节组成，一条是Q+(w,v)两个推论推论3.6若G是2-连通的，则G的任何两个顶点都位于同一条回路上。推论3.7若G是p≥3的块，则G的任意两条边都在同一条回路上。定理3.5可以推广到k-连通图，这样就得到一个k-连通图的判定准则：设G是p≥k十1的一个图，G是k-连通图当且仅当G的任意两个相异顶点至少由k条内部不相交的通路所连通．对于边也有类似的结果，当且仅当G的任意两个相异顶点由至少k条边不重的通路所连通时，G才是k-边连通的．练习举例说明：若在2-连通图G中，P是一条(u,v)-通路，则G不一定包含一条与P内部不相交的(u,v)-通路Q。P=uu1v1v练习证明：当且仅当图G的任意两个顶点由至少两条边不重通路所连通时，G才是2-边连通的。证(1)若G中任意两顶点都至少由两条边不重道路连接，显然对任意e∈E(G)，G-e是连通的，故G为2-边连通的。(2)反之，若G是2-边连通的，则G无割边。把G分解成块，块与块之间以G中的割点互相连接。设u,v是G中任意两顶点。分两种情况：①若u,v同属于G的某一块，则由定理3.5知，结论成立。②若u,v属于G的不同块，设B1,B2,…,Bn是G的块，其中块Bi与块Bi+1以割点Vi相互连接且|v(Bi)|≥3。不妨设u∈B1，v∈Bn

。由定理3.2知，在B1中存在两条由u到v1的不相交的路P11,P12；在Bi中存在两条由vi-1到vi的不相交的路Pi1,Pi2；在Bn中存在两条由vn-1由v的不相交的路Pn1,Pn2

。于是我们找到两条u到v的边不相交的路：P11∪P21∪…∪Pn1和P12∪P22∪…∪Pn2练习设G是一个2-连通图，又设X和Y是V(G)的不相交子集，而且每个子集至少含有两个顶点。证明：G含有不相交的通路P和Q使得：(1)P和Q起点均属于X；(2)P和Q的终点均属于Y；(3)P和Q的内部顶点不属于X∪Y。证：由G加上一点x，仅和X中一切点相连，再加上一点y，仅和Y和一切点相连，所得之图记为G*。由假设|X|≥2，|Y|≥2，故易直接验证G*仍为2-连通图。对x,y在G*中应用定理3.5，我们得到两条起点为x、终点为y、内部不相交的路P*、Q*。由x出发沿P*走向y的过程中，P*中最后一个属于X的顶点记为x1，然后再由x1继续沿P*前进，到达第一个属于Y的顶点记为y1，令P*中一段(x1,y1)-路记为P。类似地在Q*中可以找到一条(x2,y2)-路Q，其中x2∈X，y2∈Y。由P*、Q*的内部不相交，推知P、Q不相交。故P、Q路即为所求。Menger定理Menger定理是描述图的连通性与连接图中不同点的不相交路的数目之间关系的定理。设u和v是连通图G的两个不同的点，我们用S表示G的一个点集或者一个边集，如果u和v不在G-S的一个分支上，则称S分离u和v。定理3.8在一个图G中，分离两个不相邻点的顶点的最小数目等于联结这两个点的不相交的通路的最大数目。证设u,v是G中两个不相邻的点，用k表示分离u和v的顶点的最小数目。显然，至多存在k条不相交的(u,v)-通路。1)若k=0，u与v不连通；若k=1，存在一条(u,v)-通路。2)假设定理不成立，取最小的k≥2，使对这个k，结论不成立。令G是具有最小边数的这种反例，则至多有k-1条不相交的(u,v)-通路，且无点x同时连接u和v，因为不然的话，G-x是对k-1的反例。3)令W是分离u和v的k个顶点的一个集。下面证明u或v与W的每个顶点相邻。假定u和v都不与W中的每个顶点相邻，令Gu是从G用下述方法得到的图：把包含u的G-W的分支用单个点u’代替，并连接u’与W中的每个点。在Gu中我们还需要用k个顶点来分离u’和v，而且因为用u’取代的分支中至少有一条边，故|E(Gu)|＜|E(G)|，注意到G是边数最小的反例，因此，在Gu中存在k条不相交的u’-v通路，这k条通路的从v到W的部分记作v-W，具有下列性质：其中任意两个部分有一个公共顶点v，特别是，对于w∈W，这些通路有一条(v,w)-通路。如果把u换成v实行类似的程序，则得到k条从u到w的通路。这两个通路集合结合起来可以给出k条从u到w的通路。这两个通路集合结合起来可以给出k条独立的(u,v)-通路，导出矛盾。因此，对于分离u和v的任何k个顶点的集合W，u或v与W的每个顶点相邻。4)令ux1x2…xlv是一条最短的(u,v)-通路，则有l≥2，且由G的最小性，在图G-(x1,x2)中，可以找到一个分开u和v的k-1顶点集W0，则W1={x1}∪W0和W2={x2}∪W0，都是分离u和v的k顶点集。由于v与x1不相邻，故u与W1中每个顶点相邻。同理，u与x2不相邻，故u与W2中每个点相邻。这个事实导出下列矛盾：u和v至少有一个公共邻接顶点，因为W0中的每个顶点都是u和v的公共邻接顶点，而|W0|=k-1((2)中已证u,v无公共邻接点）由上述证明可以断言，u与v之间存在