图论第3章连通度、匹配.doc

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

类似地，树的每条边的都是桥有桥的连通图，当去掉桥时，就产生了一个不连通图对于无桥的连通图，要想去掉一些边得到不连通图，至少要去掉两条才有可能得到不连通图从去掉边来获得不连通图的角度看，有桥的连通图较之无桥的连通图的“连通程度”要低特别是，一个非平凡树是一个有最少边连通图图的顶点和边，在不同应用中有不同意义在通讯网络中，通讯站是顶点，通讯线路是边它们的失灵势必危机系统的通讯所以，网络图的“连通程度”越高，通讯网络越可靠这种直观的想法，启发我们建立以下的严格概念：1.2 顶点连通度（连通度）定义 1 设 G=(V，E)是一个无向图，要想从 G中得到一个不连通图或平凡图所需要从 G中去掉的最少顶点数称为 G的顶点连通度，简称连通度)(G说明：（1）对这个定义我们需要说明的是，希望每个图都有顶点连通度但对完全图Kp，不论去掉哪些顶点，都不会得到不连通图，当去掉 p-1个顶点时得到 K1-平凡图为了使这样的连通图也有顶点连通度，所以在定义中加入了“为得到平凡图所需要去掉的顶点的最少数”这一条件2）对于特殊的图顶点连通度是知道的K1-平凡图 ； 有割点的图 ；0)(1K1)(G不连通的图 ； 完全图 Kp 。

G2p推论 1：若 G连通，则 ；若 ，则 G连通或是非平凡图)()(定义 2设 G=(V，E)是一个无向图，要想从 G中得到一个不连通图或平凡图所需要从 G中去掉的最少边数称为 G的边连通度，简称连通度)(对于特殊的图边连通度是知道的当 p≥1 时， ；0)(1K1)(pK非平凡树 ；有桥的图 T1)(T说明：（1）对于连通图来说，边连通度就是割集中最小的那个2）对于一个图来说，割集--可以有多个，但边连通度--却只有一个3）对于非平凡图来说，割集--永远也不能为零（空集） ，但边连通度--在图不连通时却是零4）连通度与割集的联系和区别？---自己综合1.3 顶点连通度 、边连通度 、最小度 之间有以下的关系：)(G)()(G定理 1 对任一图 G，有 )()(证 先证 λ(G)≤δ(G)，若 δ(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)条边于是，产生了一个不连通图或平凡图，从而 χ(G)≤λ(G)因此，对任何 G，χ(G)≤λ(G)定理 2 对任何整数 a，b，c，0≤a≤b≤c，存在一个图 G使得, , )(b)(c)(证 若 a=b=c，则图 G=Ka+1就是所要求的图若 a=b0，则存在 V的真子集 A，使得 G中联结 A中的一个顶点与 V\A中一个顶点的边的总数恰为 λ(G).证 因为 λ(G)>0，所以 G中有 λ(G)条边，把它们去掉后得到一个恰有两个支的不连通图令其中一个支的顶点集为 A，则 A是 V的一个真子集由于 λ(G)>0，那些被去掉的每一条边，其一个端点在 A中，另一个端点在 V\A这些边当然为 λ(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中的一个顶点与 V\A中的一个顶点的边恰有 λ(G)条设|A|=m，则G中两个端点均属于 A的边的条数至少为(mδ(G)-λ(G))/2于是，假如 λ(G)(mδ(G)-δ(G))/2=δ(G)(m-1)/2若 m≤δ(G)，则(mδ(G)-λ(G))/2>m(m-1)/2这是不可能的，所以 δ(G)p，矛盾所以，λ(G)≥δ(G)于是，λ(G)=δ(G)定理 4 设 G是一个(p，q)图，则(1 )若 q设 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：uv 1v2 …vk-1v显然 d(u，v k-1)=k-1由归纳假设 u与 vk-1在 G的某个回路上于是，u 与 vk-1间有两条没有内部公共顶点(即除 u与 vk-1外)的两条路 W，Q由于 χ(G)≥ 2，所以 G无割点，从而 G-vk-1是连通图于是，G-v k-1中有 u到 v的路 Su 是 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的一个顶点与 V\A的一个顶点的边的总数小于 n 证 =>设 G是 n-边连通的，则 χ(G)≥n若存在 V的真子集 A，使得 G的联结 A的一个顶点与 V\A的一个顶点的边的总数 jrt，即 m>t，结论成立注意：定理 3中反过来不能推出 t条件例 4 现有 4名教师：张、王、李、赵，要求他们去教 4门课程：数学、物理、电工和计算机科学。

已知张能教数学和计算机科学；王能教物理和电工；李能教数学、物理和电工；赵只能教电工如何安排才能使 4位教师都能教课，并且每门课都有人教？共有几种方案？ 解: 设 V1={张、王、李、赵}，V 2={数学、物理、计算机、电工}某人能教某课程就在相应的顶点之间连一条线，得到一个偶图此偶图 G满足“相异性条件” ，因此存在 V1到 V2的完备匹配(此匹配也是完美匹配)但因赵只能教电工，因而王只能教物理，李就只能教数学，张也就只能教计算机科学了即方案只有一种 推论 1 任何 r-正则偶图 G＝(V 1∪V 2，E)必有一个完美匹配，其中 r≥1。