图的连通性.doc

第二章 图的连通性连通图：任二顶点间有路相连。例可见在连通图中，连通的程度也是有高有低。本章的目的就是定义一种参数来度量连通图连通程度的高低。2.1 割边、割点与连通度一、割点：定义2.1.1 设，如果，则称v为G的一个割点。（该定义与某些著作有所不同，主要是在有环边的顶点是否算作割点上有区别）。例定理2.1.1 如果点v是图G的一个割点，则边集E(G)可划分为两个非空子集和，使得和恰好有一个公共顶点v。推论2.1.1 对连通图G，顶点v是G的割点当且仅当不连通。以上两个结论的证明留作习题。定理2.1.2 设v是树T的顶点，则v是T的割点当且仅当。证明：必要性：设v是T的割点，下面用反证法证明。若，则，显然不是割点。若，则是有条边的无圈图，故是树。从而。因此不是割点。以上均与条件矛盾。充分性：设，则v至少有两个邻点u,w。路uvw是T中一条路。因T是树，uvw是T中唯一的路，从而。故是割点。证毕。推论2.1.2 每个非平凡无环连通图至少有两个顶点不是割点。证明：设T是G的生成树，则T至少有两个叶子u,v，由上一定理知，u,v都不是T的割点，即。由于是图的生成树，故，因此u不是G的割点。同理v也不是G的割点。证毕。二、顶点割集：定义2.1.2 对图G，若V(G)的子集使得，则称为图G的一个顶点割集。含有k个顶点的顶点割集称为k-顶点割集。注：（1）割点是1顶点割集。（2）完全图没有顶点割集。三、连通度：是G的顶点割集。完全图的连通度定义为，空图的连通度定义为0。注：(1) 使得的顶点割集称为G的最小顶点割集。（2）若，则称G为k连通的。（3）若G不连通，则。（4）若G是平凡图，则。（4）所有非平凡连通图都是1连通的。例：四、割边定义2.1.3 设，如果，则称e为G的一条割边。定理2.1.3 边e是G的割边当且仅当e不在G的任何圈中。证明：证其逆否命题：e不是割边当且仅当e含在G的某个圈中。必要性：设e = xy不是割边。假定e位于G的某个连通分支中，则仍连通。故在中有路P，P + e便构成中一个含有e的圈。充分性：设e含在G的某个圈C中，而C含于某连通分支中，则仍连通。故，这说明e不是割边。证毕。定理2.1.4 一个连通图是树当且仅当它的每条边都是割边。证明：连通图G是树G无圈任何边e不含在圈中任何边e是G的割边。证毕。五、边割集定义2.1.4对图G，若E(G)的子集使得，则称为图G的一个边割集。含有k条边的边割集称为k-边割集。注：(1) 对非平凡图G，若是一个边割集，则不连通。(2) 一条割边构成一个1边割集。(3) 设，记号表示一端在S中另一端在中的所有边的集合。对图G的每个边割集，必存在非空的，使得是G的一个边割集，其中。六、边连通度：。完全图的边连通度定义为。空图的边连通度定义为0。注：(1)对平凡图或不连通图G，。（2）若图G是含有割边的连通图，则。（3）若，则称G为k边连通的。（5）所有非平凡连通图都是1边连通的。（6）使得的边割集称为G的最小边割集。定理2.1.5 。证明：先证。若G不连通，则。若G是完全图，则。下设G连通但不是完全图。则G有边割集含有（）条边。设这个边割集为。对中每条边，选取一个端点，去掉这些端点（至多个）后，G便成为不连通图，故这些端点构成一个点割集，。因此。再证。设。删去与v关联的条边后，G变成不连通图，故这条边构成G的一个边割集。因此。证毕。2.2连通图的性质whitney定理1 块（block）：无割点的连通图。2 图的块：若满足下列三条：（1） H是图G的子图；（2）H本身是一个块；（3）H是具有此性质的极大子图。则称H是图G的一个块。例： 块 含4个块的图注：至少有三个顶点的图是块当且仅当它是2连通图。（若只有两个顶点，则有反例，例如是个块，但不是2连通的。）3Whitney定理定理2.2.1 (Whitney,1932) 的图G是2连通图（块）当且仅当G中任二顶点共圈。证明：充分性：设G中任二顶点在同一圈上，欲证G是2连通的。对，任取。由条件，u,v在G中共处于某个圈C上。若，则在中u,v仍在圈C上；若，则中u,v在路上。总之u,v在中有路相连。由u,v的任意性，是连通图，故w不是G的割点。再由w的任意性知，G无割点，即G是2连通的。必要性：设G是2连通图，欲证任二顶点u,v都在同一圈上。对距离作归纳法。时，因，故边uv不是割边，仍连通。因此中存在一条路。这表明在G中u, v都在圈上。假定时，结论成立。下证时结论也成立。当时，设是长为k的一条路，则。由归纳法假设，u,w在同一圈上，故在u,w间有两条无公共内部顶点的路P和Q。因G是2连通图，故仍连通。在中存在路。令x是上最后一个与的公共顶点（因，这样的x存在）。不妨设，则P上段上段与是两条内部无公共点的路。故u,v在同一圈上。归纳法完成。证毕。PP0uPvQxw推论2.2.1 的图G是2连通图（块）当且仅当G中任二顶点被至少两条内部无公共顶点的路所连。推论2.2.2 若的图G是2连通图（块），则G的任二边都位于同一圈上。证明：设G是的2连通图，且，在和上各添加一个新的顶点和，构成一个新图。仍是2连通的。由Whitney定理，和在中位于同一个圈上。故和在G中位于同一个圈上。证毕。注：Whitney定理可推广到k连通图，得到Menger型定理：Menger定理1 的图G是k连通图当且仅当G中任二顶点至少被k条内部无公共顶点的路所连。Menger定理2 图G是k边连通图当且仅当G中任二顶点至少被k条无公共边的路所连。2.3 关于割点、割边和块的其它结论定理2.3.1 设v是连通图G的一个顶点，则下列命题等价：（1） v是G的割点；（2） 存在，使得且v在每条路上；（3） 存在的一个划分：，使得对和，v在每条路上。证明：（1）（3）因v是割点，故至少有两个连通分支、。令而，则对和，u、w分别属于的不同的连通分支。可见G中所有的路必经过v（否则中仍有路，这与u、w分别属于的不同的连通分支矛盾）。（3）（2）显然。（2）（1）若v在每条路上，则中不存在路，即不连通，故v是G的割点。证毕。定理2.3.2 设e是连通图G的一条边，则下列命题等价：（1） 是G的割边；（2） e不在G的任何圈上；（3） 存在，使得e在每条路上；（4） 存在的一个划分：，使得对和，e在每条路上。证明：（1）（2）定理2.1.1已证。（1）（4）（3）（1）的证明与上一定理的证明类似。定理2.3.3 设G是的连通图，则下列命题等价：（1） G是2连通的（块）；（2） G的任二顶点共圈；（3） G的任一顶点与任一边共圈；（4） G的任二边共圈；（5） 对及，存在路含有边e；（6） 对，存在路含有顶点w;（7） 对，存在路不含有顶点w。证明：（1）（2）见Whitney定理。（2）（3）设G中任二顶点共圈。对及，若或，则结论显然。以下假定。设C是含u与x的圈。若，则C上含有u的路与边xy形成一个圈，它含有u及边e；xuy下设。由推论2.2.1, x不是割点。按定理2.3.1，存在不含x的路P，令w是P上从y出发第一个与C公共的顶点，则C上x-u-w段P上段xy构成一个含u和e = xy的圈。wxxuy（3）（4）：与（2）（3）类似可证。（4）（5）：设G中任二边共圈。对及，如果，结论显然成立；如果u或v之一是e的端点，比如u是e的端点而v的一个邻点是w，则e与边wv共圈，故显然有路含有边e。uvwe下面假定u和v都不是e的端点。因任二边共圈显然任二点共圈，故由（2）（3）知u与e共圈，v也与e共圈。设这二圈分别是和。若或，则结论成立；若且，则如下构作含e的路：从u出发沿到达与的第一个公共顶点w，再从w出发沿含e的部分到达v，即可。wC1evuC2（5）（6）：对，设与w相关联的一条边为e。由（5），存在路含有边e，于是含有w。（6）（7）：对，存在路P含有顶点v，则P的从u到v的一段不含有w。（7）（1）：因为对及，存在路不含有顶点w，故w不是割点。由w的任意性，G无割点。从而G是块。证毕。2.4 可靠通信网络的设计可靠网络设计问题：给定赋权图G和正整数m，求G的具有最小权的m连通生成子图。当时，就是求最小生成树问题。当时，问题尚未解决。当且每边权皆为1时，问题成为：求中边数最少的m-连通生成子图。这一问题于1962年由Harary所解决。令表示有n个顶点的m连通图所能具有的最少边数（）。设G是一个具有这种性质且有条边的图。因，而。故。Harary找到了具有n个顶点、条边的m连通图。这种图记为，构造如下：记的顶点集为。（1） 若m为偶数，设。当且仅当时，顶点i与j连边；（2） 若m为奇数（设），而n是偶数，则先构作，然后对的i，在顶点i与间加上一条边；（3） 若m为奇数（设），且n也是奇数，则先构作，然后对的i，在顶点i与间加上一条边，再在顶点0与、0与之间各加上一边。3210547652104376832105476H4,8 (m=4, r=2, n=8) H5,8 (m=5, r=2, n=8) H5,9 (m=5, r=2, n=9) 定理2.4.1 是m连通的。证明：只证的情况。的情况类似可证。我们用反证法来证明中没有少于个顶点的点割集。若不然，设是一个点割集且。又设i与j是中属于不同连通分支的两个顶点。考察顶点集和。这里加法取模n。因且，不失一般性，设。则在中必存在一个始于i而终于j，且任二相继项之差的序列。但由的构成（1），这样的序列中相邻项之间存在边。因此这个序列构成了中一条路。这与i, j的取法矛盾。证毕。推论2.4.1 。证明：容易检查。由上一定理，是m连通的，故。另一方面，前已述及。故。证毕。注：因，故也是m边连通的。若表示n个顶点的m边连通图可能的最少边数，则。习题四1. 证明恰有两个顶点不是割点的简单连通图是一条路。2. 设G连通且。证明：e在G的每棵生成树中当且仅当e是G的割边。3. 证明：若G的每个顶点均为偶度顶点，则G无割边。4. 证明：若G是k边连通的，则。5. 证明：若G是简单图且其最小度，则连通度。6. 证明：图G是2边连通的当且仅当G的任二顶点至少由两条边不重的路所连。7. 证明：若图G无偶圈，则G的每个块要么是K2要么是奇圈。8. 证明：对不是块的连通图，至少由两个块，它们每个恰含有G的一个割点。阅读文献1W. Mader, Connectivity and edge-connectivity in finite graphs, London Math. Lecture Note Series, 38(1979)66-95.2. J.C. Bermond, N. Homobono and C. Peyrat, Large fault-tolerant interconnection networks, Graphs and Combinatorics, Springer, 5(1989),107-123.3. D.F. Hsu, On container width and length in graphs, groups and networks, IEICE Trans. Fundam, 1994, E(77A), 668-680.4. D.W. Matula, Determine edge connectivity in O(mn), Proc. 28th Symp. On Foun