第3章 连通度问题

第三章连通度问题3.1连通度3.2块3.3可靠通信网的建设3.1连通度BE(G)为图G的k-边割B=k。图G的边连通度（edgeconnectivity）=使G变成不连通或平凡图所需去掉的最少边数。(易见，当G为非平凡连通图时，=G的最小键的边数。)为平凡图当为非平凡图当边割有GGkGkG0}min{)('例:=0G平凡或不连通。=1G连通且含割边。(Kn)=n-1(n0)。当G为简单图时，=-1GK。==2=1,=2=1,=2==0==0=2,=3称图G为k-边连通的（k-edgeconnected）(G)k至少去掉k条边才能使G变成不连通或平凡图。例如，所有非平凡连通图都是1-边连通的。称顶点子集V’为G的顶点割(vertexcut)G-V’不连通。称顶点子集V’为G的k-(顶)点割(vertexcut)V’为G的顶点割，且V’=k。显然，当G为无环连通图时，v为G的1-点割v为G的割点。完全图无点割。图G的连通度(connectivity)（=使G变成不连通或平凡图所需去掉的最少的顶点数。）例:当3时，=1G连通且有1-点割。(K)=-1。(G)=-1G的基础简单图为完全图。其它有二不相邻接顶点时当点割有1-G-kGkmin)(G称图G为k-连通的（k-connected）(G)k至少去掉k个顶点才能使G变成不连通或平凡图。例如，所有非平凡连通图都是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。v,v习题3.1.1(a)证明：若G是k-边连通的，且k0，又E’为G的任k条边的集合，则（G-E’)2。(b)对k0，找出一个k-连通图G以及G的k个顶点的集合S，使(G-S)2。3.1.2证明：若G是k-边连通的，则k/2。3.1.3(a)证明：若G是简单图且-2，则=。(b)找出一个简单图G，使得=-3且。3.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是适合0lmn的整数，则存在一个简单图G，使得=l，=m和=n。3.2块块（block）无割点连通图。显然，当v3时，G为块G为无环、2-连通图。例。v3的块中无割边。定理3.2(Whiteney,1932)当v3时，G为2-连通图G中任二顶点间则至少被两条内部不相交（internallydisjoint）的路所连接。（称两条路P与Q内部不相交P与Q无公共内部顶点）证明：：显然，G连通，且无1-点割，因此G为2-连通。：对G中二顶点间的距离d(,)进行归纳。当d(u,v)=1时（即uv为G的边），因G为2-连通，边uv是G的非割边(∵2)。因此，由定理2.3，边uv在G的某一圈内，成立。假设定理对d(,)k的任二顶点成立，而d(u,v)=k（2）。令w为长为k的一(u,v)-路中v的前一个顶点。显然，d(u,w)=k-1。因此，由归纳假设，存在二内部不相交的（u,w）-路P及Q。又因G为2-连通，G-w中一定存在一(u,v)-路P’。令x为P’在PQ中的最后一个顶点。不失一般性。不妨设x在P上。这时G中有二内部不相交的(u,v)-路：(P的(u,x)-节)(P’的(x,v)-节)及Qwv。PQP’uvwx推论3.2.1当3时，图G为2-连通的G的任二顶点共圈。证明：由定理3.2，显然。称边e被剖分用连接e的两端点的长2为的新路去替换e。容易验证，当3时，块的一些边被剖分后仍然保持是块。推论3.2.2设3，则G为块G连通且其任二边共圈。证明：：当2时，显然成立。当3时，将G的任二边e1和e2分别用新顶点v1和v2加以剖分，得新图G’。它仍是块，因此为2-连通的。由推论3.2.1知，v1与v2共圈。从而e1与e2共圈。：由条件，易见G无环、连通。只要再证G也不会有割点即可：假设G中有割点u。由割点定义知，存在E(G)的一个2-划分（E1,E2）使边导出子图G[E1]与G[E2]恰只有一公共顶点u。由边导出子图定义知，E1和E2中一定各存在一边e1=ux和e2=uy，它们都以u为其端点。但G-u中无(x,y)路，从而，易见，e1和e2不能共圈，矛盾。称G中极大不含割点的连通子图为G的块。当一个图G有割点时，我们可沿G的割点将G逐步划分为一些G的块。因此一个图是它的块的边不重并。例如图G划分G的块性质(1)G的两个块之间至多有一公共顶点，它一定是G的割点。(2)G的任一割点至少是G的两个块的公共顶点。(3)含割点的连通图G中，至少有两个G的块每个恰含G的一个割点，称之为endblock。(4)G是它的块的边不重并。(5)*任一图G中，易证，边之间的共圈关系是边集合上的一个等价关系。它将E(G)划分为一些等价类(E1,E2,...,Eq)，而每个G[Ei]都是G的块（其中q为G的块数）。附录Menger定理若k+1，则G为k-连通的G中任二不同顶点至少被k-条内部不相交的路所连接。G为k-边连通的G中任二不同顶点至少被k-条边不重的路所连接。习题3.2.1证明：一图是2-边连通的当且仅当任二顶点至少被两条边不重的路所连接。3.2.2举例说明：若P为2-连通图G中一给定的(u,v)-路，则G不一定有一条与P内部不相交的（u,v)-路。3.2.3证明：若G没有偶圈及孤立点，则G的每个块为K2或奇圈。3.2.4证明：不是块的连通图G中，至少有两个G的块每个恰含G的一个割点。3.2.5证明：G的块的数目=，其中b(v)是G中含顶点v的块的个数。3.2.6设G为2-连通图，而X和Y是V的不相交子集，它们各至少包含二顶点。证明：G包含二不相交的路P和Q使得(i)P和Q的起点在X中；(ii)P和Q的终点在Y中；(iii)P和Q的内部顶点都不在XY中。3.2.7叙述求图的块的好算法。(())bvvV13.2.8设边a与边b共圈，边b与边c共圈，则边a与边c共圈。3.2.9连通图G中，若顶点u不在任一奇圈上，而C为G的一奇圈，则u与C一定不在G的同一块在中。3.2.10设G为的块，则对G中任二顶点u与v，及任一边e，G中必有一(u,v)-路包含e。（提示：连u与v。）3.2.11设G为的块，x,y,z为其任三顶点，则G中必有一(x,y)-路通过z。333.3可靠通信网的建设一个通信网中，及越大越可靠，但造价越贵（）问题已给赋权图G及正整数k，求G的最小权k-连通（k-边连通）生成子图。解当k=1：optimaltree(connectorprob.)，有好算法。当k1：NP-hardprob.。当每边权1且G为任意图时：问题变成求边数最少的k-连通生成子图。(仍然是NP-hardprob.)当每边权1且GK时：Harary(1962)作出边数最少的G的k-连通（∴k-边连通）生成子图Hk,（边数={k/2})（∴有好算法。）