图论讲义2连通性new

第二章 图的连通性 第二章 图的连通性 连通图：任二顶点间有路相连。 例 可见在连通图中，连通的程度也是有高有低。 本章的目的就是定义一种参数来度量连通图连通程度的高低。 §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连通的。） 3．Whitney定理 定理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在同一圈上。归纳法完成。证毕。 推论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； 下设 。由推论2.2.1, x不是割点。按定理2.3.1，存在不含x的 路P，令w是P上从y出发第一个与C公共的顶点，则C上x-u-w段＋P上 段＋xy构成一个含u和e = xy的圈。 （3） （4）：与（2） （3）类似可证。 （4） （5）：设G中任二边共圈。对 及 ，如果 ，结论显然成立；如果u或v之一是e的端点，比如u是e的端点而v的一个邻点是w，则e与边wv共圈，故显然有 路含有边e。 下面假定u和v都不是e的端点。 因任二边共圈显然任二点共圈，故由（2） （3）知u与e共圈，v也与e共圈。设这二圈分别是 和 。若 或 ，则结论成立；若 且 ，则如下构作含e的 路：从u出发沿 到达 与 的第一个公共顶点w，再从w出发沿 含e的部分到达v，即可。 （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与 之间各加上一边。 H4,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的一个割点。 阅读文献 1．W. 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 Foundations of Computer Science, 1987,249-251. 5. J. Cheriyan, S. Vempala and A. Vatta, Approximation algorithms for minimum-cost k-vertex connected subgraphs, Proceeding of the 34th Annual ACM Symposium on Theory of Computing, Canada, 2002, pp306-312.