下载文档原格式
第五章匹配与因子分解概念、性质、定理及应用重要，需要掌握；定理证明不要求。
P116页，5.6节不要求学。
难点学习指导1.匹配、完美匹配、最大匹配、M饱和的点、M非饱和的点概念；下图粗线表示相关匹配。
绿色所标的两条边不能是匹配边，因为匹配的边不能相邻。
注意：边相邻概念，如果两条边有一个公共顶点，则这两条边相邻。
2.M交错路、M可扩充路概念3.偶图的匹配与覆盖偶图的概念；点集S的邻域或邻集概念；在下面的偶图中，点集S由5个点，和这五个点相邻的所有点由4个，这四个点形成的集合就是点集S的邻集或邻域(如下图绿色圈所包)只要有一个点集不满足定理2，那就不能饱和所有的X集合里的点。
4.图G的覆盖与最小覆盖的概念最小覆盖：点数最小的覆盖。
5.Tutte定理与完美匹配图的奇分支与偶分支概念Peterson图满足推论，因此有完美匹配。
三正则图，有三条割边，不满足推论，没有完美匹配。
三正则图虽有割边，但有完美匹配，因此无割边仅是完美匹配的充分条件，不是不要条件。
6.因子分解1-因子分解（不相交的单条边集）：注意概念，将一个图边不相交的1-因子的并，就称为1-因子分解。
算法图如下。
然后水平两对点连线得：依次类推就分别得到其他1-因子分解图。
2-因子分解：K7如下图：三个圈的生成算法：把这三个图展开，就得三个圈，也就是三个2-因子分解。
7.荫度概念8.最优匹配与匈牙利算法匈牙利算法：注意M交错树概念，从一个非饱和点开始，到另一个非饱和点结束，通过改变原有匹配使两个非饱和点变为饱和点，以这种方式逐渐扩大匹配，有可能生成完美匹配，有可能生不成完美匹配。
经过这一次操作，得到新匹配如下：9.书中印刷错误更正10.最优匹配算法（1）可行顶点标号概念，相hhh等子图概念（2）比较复杂，不好理解，下面以一个例子来说明就简单一点。
图论与网络流理论（Graph Theory and Network Flow Theory）高随祥中科院研究生院专业基础课学时/学分：60/3本课程适合基础数学、应用数学、计算数学、运筹学与控制论、概率论与数理统计各专业的硕士学位研究生作为专业基础课，也可供物理学、化学、天文学、地学、生物科学、计算机科学与技术、计算机软件、管理科学与工程以及通信、信号等学科专业的硕士研究生选修。
主要讲授图论与网络流理论的基本概念、方法和定理，介绍该领域重要的问题以及典型的算法，展示图论与网络流模型及方法的广泛应用。
为学习者将来从事有关方面的理论研究打下基础，也为进行应用性研究提供一种有力的工具。
内容提要第一章 图的基本概念图的基本概念；二部图及其性质；图的同构；关联矩阵与邻接矩阵。
路、圈与连通图；最短路问题。
树及其基本性质；生成树；最小生成树。
第二章 图的连通性割点、割边和块；边连通与点连通；连通度；Whitney定理；可靠通信网络的设计。
第三章 匹配问题匹配与最大匹配；完美匹配；二部图的最大匹配；指派问题与最大权匹配。
第四章 欧拉图与哈密尔顿图欧拉图；中国邮递员问题；哈密尔顿图；旅行商问题。
第五章 支配集、独立集、覆盖集与团支配集、点独立集、点覆盖集、边覆盖集与团的概念及其求法。
第六章图的着色问题点着色；边着色；平面图；四色猜想；色多项式；色数的应用。
第七章网络流理论有向图；网络与网络流的基本概念；最大流最小割定理；求最大流的标号算法；最小费用流问题；最小费用最大流；网络流理论的应用。
主要参考书[1] J.A. Bondy and U.S. Murty, Graph theory with applications, 1976, 有中译本（吴望名等译）。
[2] B.Bollobas, Modern graph theory (现代图论)，科学出版社，2001。
[3] 蒋长浩，图论与网络流，中国林业出版社，2001。
1、支配集：设D集合是无向图G的一个顶点子集，对于G中的任意顶点u，要么在D里，要么与D集合的一个顶点相邻，那么称我们集合D的G的一个支配集。
如果去掉D中任何一个顶点，D不在是支配集，则支配集是极小支配集。
G中所有支配集中顶点个数最小的支配集称为最小支配集，即是极小支配集。
最小支配集的顶点个数为支配数。
2、独立集：设I集合无向图G的一个顶点子集，对于集合I中任意两点都不相邻，则我们称集合I为G 的一个独立集。
如果在I中加入一个非I集合的顶点后，I集合不在是独立集，则称集合I 为极大独立集。
G中所有独立集中顶点个数最多的独立集称为最大独立集，即是极大独立集。
最大独立集的顶点个数为独立数。
3、覆盖集：设K集合是无向图G的一个顶点子集，对于G中的任意一条边e，至少有一个端点属于K，那么我们称集合K是G的一个覆盖集。
如果去掉K中的任意一个顶点，K不在是覆盖集，则称集合K是极小覆盖集。
在G中所有覆盖集中顶点个数最少的覆盖集称为最小覆盖集。
即是极大覆盖集。
最小覆盖集的顶点个数为覆盖数。
4、网络流：a、网络与流：网络D=(V,A,C）设D是一个简单有向图，V是顶点集，A是边集，C弧容量集。
网络流FF(i,j)=集合A上的一个函数，为弧(vi,vj)的流量。
b、可行流与最大流：可行流（1）容量限制对于每条弧(vi,vj)属于A，则0<=|F(i,j)|<=c(i,j)。
（2）平衡条件对于V里的每个顶点i!=s,t;(源点和汇点)都有流入量=流出量对顶点s的流出量-s的流入量=-1*（顶点t的流出量-t的流入量）最大流求最大流问题即是求顶点s的流出量-流入量的最大值或者求顶点t的流出量-流入量的最小值。
c、可改进路P如果|F(i,j)|=C(i,j)，称该弧为饱和弧如果|F(i,j)|<C(i,j)，称该弧为非饱和弧如果|F(i,j)|>0，称该弧为非零弧如果|F(i,j)|=0，称该弧为零弧设P是一条有源点s到汇点t一条路（边不同，顶点可以相同），在P路构成的边中，我们将边和P的方向相同的边称为前向弧，反之为后向弧。
1第五章 支配集、独立集、覆盖集和Ramsey数 本章讨论图中具有某种特性的顶点子集和边子集，以及它们之间的关系。本章所讨论的图均为简单图。
§5.1 支配集、点独立集、点覆盖集 一、支配集(Domination set) 定义5.1.1设)(GVD⊆，若对)(GVu∈∀，要么Du∈，要么u与D中的某些顶点相邻，则称D为图G的一个支配集。如果一个支配集的任何真子集都不是支配集，则称它为极小支配集。图G的含顶点最少的支配集称为最小支配集。最小支配集的顶点个数称为G的支配数，记为()Gγ或γ。
例如，在下图中，}{00vD=，},,{7411vvvD=，},,,{65312vvvvD=都是G的支配集，前两个是极小支配集，0D是最小支配集。1)(=Gγ。
G 注：（1）最小支配集必是一个极小支配集，反之不然。 （2）任一支配集必含有一个极小支配集。 （3）极小支配集不唯一，最小支配集一般也不唯一。 （4）对二部图),(YXG=，X和Y都是支配集。 （5）若图G有完美匹配M*，则从M*中每边取一个端点构成的顶点集是一个支配集。 定理5.1.1 设图G中无孤立顶点，则存在支配集D，使得()DVGD=−也是一个支配集。 证明：无妨设G是连通图。于是G有生成树T。任取)(0GVv∈。令 )(|{GVvvD∈=且),(0vvdT＝偶数}，
则(){|()DVGDvvVG=−=∈且),(0vvdT＝奇数}，且D和D都是支配集。证毕。
定理5.1.2设图G无孤立顶点，1D是一个极小支配集，则11()DVGD=−也是一个支配集。 证明（反证法）：若不然，存在10Dv∈，它与1
D中所有顶点都无边相连，但它又不是孤立顶
点，故必与1D中顶点连边，因此01vD−仍是支配集。这与1D是极小支配集矛盾。证毕。 推论5.1.1设图G中无孤立顶点。对G的任一个极小支配集1D，必存在另一个极小支配集2D，
使得φ=21DD∩。 证明：由定理5.1.2，11()DVGD=−也是一个支配集，且φ=DD∩1。1D中必含有一个极小支配集2D。显然φ=21DD∩。证毕。
v7 v8 v2v1v5v6v3v4
v0 2
定理5.1.3 图G的支配集D是一个极小支配集当且仅当D中每个顶点v满足下列条件之一： （1）存在()uVGD∈−使得(){}NuDv=∩；（2）()NvDφ=∩。 证明：充分性：设D是G的一个支配集。对D中任一个顶点v，因v满足上述条件之一，故要么与v相邻的某个顶点不能被{}Dv−支配，要么v自己不能被{}Dv−支配，可见，{}Dv−
不再是支配集。这表明D是极小支配集。 必要性：设D是G的一个极小支配集，则对D中任一个顶点v，{}Dv−不再是支配集。因此在{}Dv−之外存在顶点u，它不与{}Dv−中任何点相邻。如果uv=，则说明v不与D中任何点相邻，即()NvDφ=∩；如果uv≠，则因D是支配集，故u必与v相邻，但不与
D中其它点相邻，即(){}NuDv=∩。证毕。
定理5.1.4 设G是无孤立顶点的图，则G必有最小支配集D满足：对vD∀∈，uGD∃∈−使得(){}NuDv=∩。
证明：用反证法。在G的全部最小支配集中，设D为使得导出子图G[D]含边数最多的一个。假定定理结论不真，即 vD∃∈，使得对uGD∀∈−都有(){}NuDv≠∩。
由定理5.1.3，()NvDφ=∩，即D中所有其它点都不与v相邻。而上式表明，GD−中每个点要么不与v相邻，要么既与v相邻也与D中另外某些点相邻。因G无孤立点，故v在GD−中必有某个邻点w，令1({}){}DDvw=−∪，则1D也是G的一个最小支配集，但其导出子图G[D1]含的边数比G[D]中多。这与D的取法矛盾。证毕。
以下是关于支配数的几个估计式。 定理5.1.5 如果图G无孤立顶点，则(G)2υγ≤。 证明：设D是G的一个极小支配集，则由定理5.1.2，V(G)D−也是G的支配集。因此，(G)min{|D|,|V(G)D|}2υγ≤−≤。
证毕。 定理5.1.6 (Arnautov 1974, Payan 1975) 设G是一个最小度为δ图，则1ln(1)(G)1δγυδ++≤+。
证明：对G的任一非空顶点子集SV(G)⊆，用U表示未被S中顶点支配的所有顶点之集。对()vVG∀∈，用()Nv∗表示顶点v及其所有邻点组成的集合，即()(){}NvNvv∗=∪。由 于U中每个顶点至少有k个邻点，故|()|||(1)vUNvUδ∗∈≥+∑。从而在()VGS−中至少有一
个顶点x，它在求和过程中至少被重复计算||(1)Uδυ+次。(否则，若()VGS−中每个点被重复计算都少于||(1)Uδυ+次，则|||()|(|S|)(1)||(1)vUUNvUυδδυ∗∈<−⋅+<+∑，与前式矛盾)。这意味着在()VGS−中存在某个顶点x，它支配U中至少||(1)Uδυ+各顶点。 3
现在我们通过迭代来生成G的一个支配集，用S表示在迭代过程中形成的支配集的一部分，初始时可取最大度顶点放入S。在迭代的每一步选择一个顶点放入S，所选择的顶点应能够尽可能多地支配当前的S尚未支配的顶点。由前一部分的结论，如果当前的S尚未支配的
顶点有||Uk=个， 则在()VGS−中存在某个顶点x，它支配U中至少(1)kδυ+个顶点。因
此按照我们的选点规则，再选择一个点放入S后，剩下未被支配的顶点不超过1(1)kδυ+−个。
在ln(1)1δυδ++步后，未被支配的顶点个数至多为
ln(1)ln(1)11(1)1eδυδδδυυυυδ+⋅−++
+−<=
+。
（上式推导中用到不等式1ppe−−<）。将当前S中的点和未被S支配的点放在一起，便组成G的一个支配集，它含有ln(1)1δυδ+++1υδ+=1ln(1)1δυδ+++个顶点。结论得证。
定理5.1.7 对任何图G，有(G)(G)1(G)υγυ⎡⎤≤≤−Δ⎢⎥+Δ⎢⎥。 证明：设D是G的一个最小支配集，则V(G)D()vDNv∈−⊆∪，因此|V(G)D||D|(G)−≤⋅Δ。
而|V(G)D||D|υ−=−，|D|(G)γ=，故(G)(G)(G)υγγ−≤Δ，于是(G)1(G)υγ⎡⎤≥⎢⎥
+Δ⎢⎥
。
证毕。 图的支配集是内容相当丰富的一个研究专题，它在许多学科领域有重要的应用，是目前研究的一个热点方向[1~5]。进一步的了解可参看Haynes－Hedetniemi－Slater的长达1200页的专著[6]。支配集理论在电力网络中的应用见文献[7]。支配集在无线通信网络中的应用见文献[ 8~11]。 [1] B.G.. Xu, Two classes of edge domination in graphs, Discrete Applied Mathematics, 154(2006), 1541-1546. [2] T.W. Haynes, M.A. Henning, and J. Howard, Locating and total dominating sets in trees, Discrete Applied Mathematics, 154(2006), 1293-1300.
[3] J.S. Deogun, and D. Kratsch, Dominating pair graphs, SIAM J. Discrete Mathematics, 15:3(2001-2002), 353-366.
[4] Chin Lung Lu, Ming-Tat Ko and Chuan Yi Tang, Perfect edge domination and efficient edge domination in graphs, Discrete Applied Mathematics, 119(2002), 227-250.
[5] Chin Lung Lu and Chuan Yi Tang, Weighted efficient domination problem on some perfect graphs, Discrete Applied Mathematics, 117(2002), 163-182.
[6] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., 1998.
[7] T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi, and M.A. Henning, Domination in graphs applied to electric power networks, SIAM J. Discrete Mathematics, 15:4(2001-2002), 519-529. 4
[8] I. Stojmenovic, M. Seddigh, and J. Zunic, Dominating sets and neighbor elimination based broadcasting algorithms in wireless networks, Proc. IEEE Hawaii Int. Conf. On System Sciences, Jan. 2001.
[9] J. Wu, and H.L.Li, On calculating connected dominating set for efficient routing in ad hoc wireless networks, Proceedings of the 3rd ACM International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, 1999,7-14.
[10] S. Guha, and S. Khuller, Approximation algorithms for connected dominating sets, Algorithmica, 20:4(1998), 347-387.
[11] B. Das, and V. Bharghavan, Routing in ad hoc networks using minimum connected dominating sets, ICC’97, Montreal, Canada, June, 1997.
二、点独立集(vertex independent set) 定义5.1.2 设）（GVI⊆，若I中任二顶点均不相邻，则称I为图G 的一个点独立集（简称独立集）；若对IGVu\)(∈∀，}{uI∪都不再是G的独立集，则称独立集I为图G 的一个极大点独立集。G的含点数最多的点独立集称为最大点独立集，它含点的个数称为G的独立数，记为)(Gα或α。
