图论 第3章 连通度匹配

1、第三章 连通度、匹配本章的特点：（1）理论深；（2）本科基本用不上（计算机体系结构上用到一点），只有研究生才能用上；（3）只介绍这个领域最基本的概念和一些有用的结果。 一个图是否是连通的，这是图的一个重要性质。内容：本章首先引入图的顶点连通度和边连通度，由此可以比较两个图中哪个“更加连通”；接着讨论了它们的一些简单性质；然后讨论偶图的匹配问题。第一节 顶点连通度和边连通度1.1 动机和目的 一个图是否是连通的，是图的一个重要性质。于是，我们就想来刻画两个图“连通程度”的大小，但是刻画两个图“连通程度”的大小方法很多，我们只介绍两个常用的方法：顶点连通度和边连通度例：树的每个度大于1的顶点都是割

2、点。一个具有割点的连通图，当去掉这个割点时，就产生了一个不连通图。对于一个没有割点的连通图，必须去掉多于一个顶点才有可能得到一个不连通图。于是，具有割点的连通图较之没有割点的连通图的“连通程度”要低。类似地，树的每条边的都是桥。有桥的连通图，当去掉桥时，就产生了一个不连通图。对于无桥的连通图，要想去掉一些边得到不连通图，至少要去掉两条才有可能得到不连通图。从去掉边来获得不连通图的角度看，有桥的连通图较之无桥的连通图的“连通程度”要低。特别是，一个非平凡树是一个有最少边连通图。图的顶点和边，在不同应用中有不同意义。在通讯网络中，通讯站是顶点，通讯线路是边。它们的失灵势必危机系统的通讯。所以，网络

3、图的“连通程度”越高，通讯网络越可靠。这种直观的想法，启发我们建立以下的严格概念：1.2 顶点连通度（连通度）定义1 设G=(V，E)是一个无向图，要想从G中得到一个不连通图或平凡图所需要从G中去掉的最少顶点数称为G的顶点连通度，简称连通度。记为。说明：（1）对这个定义我们需要说明的是，希望每个图都有顶点连通度。但对完全图Kp，不论去掉哪些顶点，都不会得到不连通图，当去掉p-1个顶点时得到K1-平凡图。为了使这样的连通图也有顶点连通度，所以在定义中加入了“为得到平凡图所需要去掉的顶点的最少数”这一条件。（2）对于特殊的图顶点连通度是知道的。K1-平凡图； 有割点的图；不连通的图； 完全图Kp

4、。推论1：若G连通，则；若，则G连通或是非平凡图。定义2设G=(V，E)是一个无向图，要想从G中得到一个不连通图或平凡图所需要从G中去掉的最少边数称为G的边连通度，简称连通度。记为。对于特殊的图边连通度是知道的。；当p1时，；非平凡树 ；有桥的图。说明：（1）对于连通图来说，边连通度就是割集中最小的那个。（2）对于一个图来说，割集-可以有多个，但边连通度-却只有一个。（3）对于非平凡图来说，割集-永远也不能为零（空集），但边连通度-在图不连通时却是零。（4）连通度与割集的联系和区别？-自己综合。1.3 顶点连通度、边连通度、最小度之间有以下的关系：定理1 对任一图G，有证 先证(G)(G)，若

5、(G)=0，则G不连通，从而(G)=0。所以，这时(G)(G)；若(G)0，不妨设degu =(G)，从G中去掉与v关联的(G)条边后，得到的图中v是弧立顶点。所以，这时(G)(G)。因此，对任何图G有(G)(G)。其次，证明对任何图G有(G)(G)。若G是不连通的或平凡图，则显然有(G)(G)=0；今设G是连通的且非平凡的。若G有桥x，则去掉x的某个端点就得到一个不连通图或平凡图，从而(G)=1=(G)。所以，这时有(G)(G)；若G没有桥，则(G)2。于是，从G中去掉某些(G)边得到一个不连通图。这时从G中去掉这(G)条边的每一条的某个端点后，至少去掉了这(G)条边。于是，产生了一个不连通

6、图或平凡图，从而(G)(G)。因此，对任何G，(G)(G)。定理2 对任何整数a，b，c，0abc，存在一个图G使得,。证 若a=b=c，则图G=Ka+1就是所要求的图。若a=bc，则所要求的图G的图解为图1(a)所示。 Kc+1 Kc+1 a条边 (a) Kc+1 Kc+1 a-1条边 (b)图1若ab=c，则G=2Kb-a+1+Ka就是所要求的图。其中G的图解是这样画出的：把完全图Kb-a+1的图解在平面上画两次，再画出Ka图解，然后在Ka的每个顶点与Kb-a+1的每个顶点间联一条边而得到的图。若ab0，则存在V的真子集A，使得G中联结A中的一个顶点与VA中一个顶点的边的总数恰为(G).证

7、 因为(G)0，所以G中有(G)条边，把它们去掉后得到一个恰有两个支的不连通图。令其中一个支的顶点集为A，则A是V的一个真子集。由于(G)0，那些被去掉的每一条边，其一个端点在A中，另一个端点在VA。这些边当然为(G)条。定理3 设G=(V，E)有p个顶点且(G)p/2，则(G)=(G)。证 因为(G)P/2，所以G是连通的。由定理3.1.1知，(G)(G)。于是只要证明(G)(G)即可。由于G是连通的，所以(G)0。由引理3.1.1，存在V的真子集A使得G中联结A中的一个顶点与VA中的一个顶点的边恰有(G)条。设|A|=m，则G中两个端点均属于A的边的条数至少为(m(G)-(G)/2于是，假

8、如(G)(m(G)-(G)/2=(G)(m-1)/2若m(G)，则(m(G)-(G)/2m(m-1)/2。这是不可能的，所以(G)p，矛盾。所以，(G)(G)。于是，(G)=(G)。定理4 设G是一个(p，q)图，则 (1 )若qp-1，则(G)=0； (2 )若qp-1，则(G)2q/p 证(1)若qp-1，则G不连通，故 (G)=0。(1) 若qp-1，则有握手定理可知：，故，于是。由定理1便得到。1.4 n-顶点连通、n-边连通定义3 设G是一个图，则若n，则称G是n-顶点连通的，简称n-连通；若n，则称G是n-边连通的。显然，图G是1-连通的，当且仅当是连通的。定理5 设G =(V，E

9、)是p个顶点的图，p3，则G是2-连通图，当且仅当G的任两个不同顶点在G的同一个回路上。证 设G是2-连通的，u和v是G的两个不同顶点。施归纳于u与v的距离d(u，v)来证明u与v在一个回路上。当d(u，v)=1，由于(G)2，所以uv不是桥。由定理2.3.3，边uv必在G的某个回路上，所以u与v在G的某个回路上。假设对d(u，v)k的任意两个不同顶点u和v，u与v必在G的某个回路上。今设 d(u，v)=k，往证u和v在G的某个回路上。考虑G中u与v间的一条长为k的路P：uv1v2 vk-1v。显然d(u，vk-1)=k-1。由归纳假设u与vk-1在G的某个回路上。于是，u与vk-1间有两条没

10、有内部公共顶点(即除u与vk-1外)的两条路W，Q。由于(G) 2，所以G无割点，从而G-vk-1是连通图。于是，G-vk-1中有u到v的路S。u是W，Q，S的公共顶点。设w是S上从u到v且在Q或W上的最后一个顶点(见图3.1.2)。不妨设w在Q上，则在G中就有含u与v的回路：Q上的u与w间一段后接S上w与v间的那段，然后是边vk-1v，最后是W。定理6 图G =(V，E)是n-边连通的充分必要条件是不存在V的真子集A，使得G的联结A的一个顶点与VA的一个顶点的边的总数小于n 。证 =设G是n-边连通的，则(G)n。若存在V的真子集A，使得G的联结A的一个顶点与VA的一个顶点的边的总数jn，则去掉这j条边便得到一个不连通图，所以，(G)j。这与 (G)n相矛盾。因此，V的这样的真子集A是不存在的。=若(G)n，则由引理3.1.1，存在V的真子集A，使得G的联结A的一个顶点与VA的一个顶点的总数为(G)rt，即mt，结论成立。注意：定理3中反过来不能推出t条件。例4 现有4名教师：张、王、李、赵，要求他们去教4门课程：数学、物理、电工和计算机科学。已知张能教数学和计算机科学；王能教物理和电工；李能教数学、物理和电工；赵只能教电工。如何安排才能使4位教师都能教课，并且每门课都有人教？共有几种方案？ 解: 设V1=张、王、