《图论-二部图、连通性.doc》由会员分享，可在线阅读，更多相关《图论-二部图、连通性.doc（5页珍藏版）》请在金锄头文库上搜索。
1、二部图定义：图称为二部图(bipartite graph)，如果是两个互不相交的集合的开集，且和中的顶点互不相邻. 这样的二部图也常称为-二部图.定义：图的匹配是由中没有公共顶点构成的集合，与匹配中的边关联的顶点称为是被-浸润的(saturated by M)，其余的顶点称为未被-浸润的(M-unsaturated). 图的一个完美匹配(perfect matching)是浸润的所有顶点的匹配. 图的边数最多的匹配称为一个最大匹配(maximum matching).例如在上图中，粗边给出了一个匹配，显然两条细边给出了一个最大匹配.定义：设是图的一个匹配. 如果路径的边交替出现在和不出现在中，
2、则称是一条-交错路径(M-alternating path). 两个顶点都未被-浸润的交错路径称为-增广路径(M-augmenting path).在上例中存在-增广路径，是最大匹配，而不存在-增广路径，这不是偶然的. 因为可以让（留作习题）：图的一个匹配是最大匹配中无-增广路径.定义：图的一个顶点覆盖(covering)是一些顶点构成的集合，使得的任何一边都有一个顶点含于. 一个顶点覆盖称为最小顶点覆盖，是指不存在覆盖，使得.设是的一个顶点覆盖，是的一个匹配，显然. 我们关心对于最大匹配的最小顶点覆盖来说，等式是否成立. 在图1(a)中，等式成立，而图1(b)中最小顶点覆盖大小为3，而最大匹
3、配大小为2. 注意图1(a)为二部图，图1(b)为有5条边的圈，从而不是二部图（可以一个图是二部图中不含奇数边的图，证明留作习题）.对于二部图，我们有下面一般的结论：定理：设是-二部图，则的最大匹配的大小等于的最小顶点覆盖的大小(knig 1931).证明：设是的最大匹配，而是的最小顶点覆盖，要证.显然，故只需证明存在的个顶点的覆盖（则），对于中每一条边，如果存在未被-浸润的中顶点出发的交错路径可达这条边，则选择此边在中的顶点；否则选择此边在中的顶点，这样就选了个顶点，记为.设，只需证明或，或，则由的定义得证.下证之：设. 又由是最大匹配，故（其中）且或. 若（此时），由于是-交错路径，故.下
4、设，如果，则，由的定义：某条交错路径可达. 则存在交错路径可达；或（若）；或. 这样就出现了-增广路径，与是最大匹配矛盾，故.对于-二部图，若存在一个浸润的匹配，则显然，至少在中存在个顶点与中的顶点相邻. 我们用表示与中顶点相邻的顶点构成的集合，下面的定理说明“”这个显然的必要条件也是充分的定理(1935)：-二部图中存在浸润的匹配.证明：“”由knig定理，只需证明对每个顶点覆盖，有. 令，则的点都不在中，因此中的点都在中（由顶点覆盖定义），故，证毕.图的连通性因为连通与否与图是否含环无关，故本小节假定所有图都不含环，且.定义1：图的一个点割(vertex cut)是一个集合，使得的连通分量
5、多于一个的连通度(connectivity)，是使得不连通或只有一个顶点的顶点集合大小的最小值. 如果的连通度最少是，则称是-连通的(-connected).由定义，显然可知：连通图都是1-连通的；是不连通的的连通度为0；顶点数大于2的图的连通度为1它是连通的且有一个割点.若图的连通度为，则，故中至少有条边（见习题）. 我们关心是否可以给出n个顶点的-连通图且有条边（即下界是否可以取到）.习题给出了肯定的回答.定义2：图中的边割(edge cut)是一顶点在中，一顶点在中的中所有边构成的集合，记为（）. 若使得不连通的边数最小值为，则称是-边连通的，称为的边连通度，记为.在下图中粗线标出的边割
6、是的最小边割，因此，是2-边连通的. 图中还标出了一个只含一个顶点的点割，故是1-连通的.定理3(Whitney 1932)：设是简单图，则.证明：设，即，则与关联的所有边构成一个边割，故，下证.显然，设为的最小边割，若中的顶点与中的顶点都邻接，则，命题得证.下设存在.则不相邻，构造集合：包含中的相邻顶点；包含中的所有与中顶点有相邻顶点的顶点（或：存在使得）. 因为每条路径都通过，因此是一个点割，故. 在中选条边：，若，则选边；若，则任意选取一条边，这样选取的条边都是不同的，因此下面给出2-连通图的特征.定理4(Whitney 1932)：图是2-连通的，在中存在内部不相交的(internal
7、ly-disjoint)-路径（即两条路径没有公共的内顶点）.证明：“”删除一个顶点不能使一对任意顶点不可达，故是2-连通的.“”对用数学归纳法证明.，是连通的（因为）.中的-路径与边构成了内部不相交的两条-路径假设时命题成立，下证时命题也成立.令是某条最短-路径上的前一顶点，则. 由归纳假设，有内部不相交路径. 若，则在圈上可以找两条内部不相交路径. 若，由于是2-连通的，故连通，所以中含有一条-路径. 若不含或的内部顶点，则完成了证明. 如若不然，不妨设与的内部顶点相交，设是这些交点中在上与最近的一个顶点，则上的-路径合并上的-路径就得到一条与内部不相交路径练习中给出2-连通图的其它特征. 定理4可以推广到一般的-连通图.证明较繁，我们这里略去，有兴趣的读者可参见D.B. West,Introduction to Graph Theory,2nd 2001.或J.A. Bondy,U.S.R. Murty,Graph Theory with Applications,1976.习题1.图的连通度为且，则至少有条边.2.证明下图中，从而满足 3.设，则是2-连通的是连通的且无割点 ，存在经过的环 且的每一对边均位于一个公共环上
