图论-二部图、连通性.doc

《图论-二部图、连通性.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、二部图　　定义：图称为二部图(bipartitegraph)，如果是两个互不相交的集合的开集，且和中的顶点互不相邻.这样的二部图也常称为-二部图.　　定义：图的匹配是由中没有公共顶点构成的集合，与匹配中的边关联的顶点称为是被-浸润的(saturatedbyM)，其余的顶点称为未被-浸润的(M-unsaturated).图的一个完美匹配(perfectmatching)是浸润的所有顶点的匹配.图的边数最多的匹配称为一个最大匹配(maximummatching).　　例如在上图中，粗边给出了一个匹配，显然两条细边给出了

2、一个最大匹配.　　定义：设是图的一个匹配.如果路径的边交替出现在和不出现在中，则称是一条-交错路径(M-alternatingpath).两个顶点都未被-浸润的交错路径称为-增广路径(M-augmentingpath).　　在上例中存在-增广路径，是最大匹配，而不存在-增广路径，这不是偶然的.因为可以让（留作习题）：图的一个匹配是最大匹配中无-增广路径.定义：图的一个顶点覆盖(covering)是一些顶点构成的集合，使得的任何一边都有一个顶点含于.一个顶点覆盖称为最小顶点覆盖，是指不存在覆盖，使得.设是的一个顶点覆

3、盖，是的一个匹配，显然.我们关心对于最大匹配的最小顶点覆盖来说，等式是否成立.在图1(a)中，等式成立，而图1(b)中最小顶点覆盖大小为3，而最大匹配大小为2.注意图1(a)为二部图，图1(b)为有5条边的圈，从而不是二部图（可以一个图是二部图中不含奇数边的图，证明留作习题）.对于二部图，我们有下面一般的结论：定理：设是-二部图，则的最大匹配的大小等于的最小顶点覆盖的大小(könig1931).证明：设是的最大匹配，而是的最小顶点覆盖，要证.显然，故只需证明存在的个顶点的覆盖（则），对于中每一条边，如果存在未被-浸

4、润的中顶点出发的交错路径可达这条边，则选择此边在中的顶点；否则选择此边在中的顶点，这样就选了个顶点，记为.设，，只需证明或，或，则由的定义得证.下证之：设.又由是最大匹配，故（其中）且或.若（此时），由于是-交错路径，故.下设，如果，则，由的定义：某条交错路径可达.则存在交错路径可达；或（若）；或.这样就出现了-增广路径，与是最大匹配矛盾，故.对于-二部图，若存在一个浸润的匹配，则显然，至少在中存在个顶点与中的顶点相邻.我们用表示与中顶点相邻的顶点构成的集合，下面的定理说明“”这个显然的必要条件也是充分的定理(19

5、35)：-二部图中存在浸润的匹配.证明：“”由könig定理，只需证明对每个顶点覆盖，有.令，则的点都不在中，因此中的点都在中（由顶点覆盖定义），故，证毕.　图的连通性　　因为连通与否与图是否含环无关，故本小节假定所有图都不含环，且.　　定义1：图的一个点割(vertexcut)是一个集合，使得的连通分量多于一个的连通度(connectivity)，是使得不连通或只有一个顶点的顶点集合大小的最小值.如果的连通度最少是，则称是-连通的(κ-connected).由定义，显然可知：①连通图都是1-连通的；②是不连通的的

6、连通度为0；③顶点数大于2的图的连通度为1它是连通的且有一个割点.若图的连通度为，则，故中至少有条边（见习题１）.我们关心是否可以给出n个顶点的-连通图且有条边（即下界是否可以取到）.习题１给出了肯定的回答.定义2：图中的边割(edgecut)是一顶点在中，一顶点在中的中所有边构成的集合，记为（）.若使得不连通的边数最小值为，则称是-边连通的，称为的边连通度，记为.在下图中粗线标出的边割是的最小边割，因此，是2-边连通的.图中还标出了一个只含一个顶点的点割，故是1-连通的.定理3(Whitney1932)：设是简单

7、图，则.证明：设，即，则与关联的所有边构成一个边割，故，下证.显然，设为的最小边割，若中的顶点与中的顶点都邻接，则，命题得证.下设存在.则不相邻，构造集合：包含中的相邻顶点；包含中的所有与中顶点有相邻顶点的顶点（或：存在使得）.因为每条路径都通过，因此是一个点割，故.在中选条边：，若，则选边；若，则任意选取一条边，这样选取的条边都是不同的，因此下面给出2-连通图的特征.定理4(Whitney1932)：图是2-连通的，在中存在内部不相交的(internally-disjoint)-路径（即两条路径没有公共的内顶点）

8、.证明：“”删除一个顶点不能使一对任意顶点不可达，故是2-连通的.“”对用数学归纳法证明.，是连通的（因为）.中的-路径与边构成了内部不相交的两条-路径．假设时命题成立，下证时命题也成立.令是某条最短-路径上的前一顶点，则.由归纳假设，有内部不相交路径.若，则在圈上可以找两条内部不相交路径.若，由于是2-连通的，故连通，所以中含有一条-路径.若不含或的内部顶