主要定理二分图的最大匹配算法二分图的带权重的最大匹配

2021/1/6第6章图与网络分析6.7最大匹配问题2021/1/6山东大学软件学院2最大对集（匹配）问题二分图的对集，基本概念，主要定理二分图的最大匹配算法二分图的带权重的最大匹配——分派问题及算法2021/1/6山东大学软件学院3图G=(V,E)的对集M：M是E的子集，且M中任意两条边均不相邻（都不共享顶点）。M-饱和点i：V(M)中的顶点（iV(M)，匹配的点）。M-非饱和点i：V(M)之外的顶点（iV(M)，没有匹配的点）。极大对集M：不存在另外一个对集M，使得MM。最大对集M：不存在另外一个对集M，使得MM。完美对集M：对集M，匹配了G上所有的点。基本概念2021/1/6山东大学软件学院4使用最大流算法求二分图上的最大匹配给定二分图G=(V,U,E)，构造流网络。增加一个源点s，从s到V中每个顶点引一条有向边。增加一个目标顶点t，从U中每个顶点向t引一条有向边。E中的边均从V指向U。记得到的流网络为G’=(V’,E’)。G’中的每条边均为单位容量。计算G’上从s到t的最大流。E中的饱和边即构成G上的一个最大匹配。2021/1/6山东大学软件学院5例子2021/1/6山东大学软件学院6定理定理：记G’上的最大流为f*，流值为|f*|。G上的最大匹配为M*。则|f*|=|M*|。证明：首先证|f*||M*|。给定最大匹配M*，令G’上M*中的边的流值为1，s到M*匹配的V一侧点的各条边上流值为1，M*匹配的U一侧点到t的各条边上流值为1，则构造了一个流值为|M*|的流f。因此，显然有|f*||M*|。再证|f*||M*|。设f*为G’上的最大流。由整流定理，G’上每条边上的流值为整数。由于每条边的容量均为1，因此G’上每条边的流值不是0就是1。2021/1/6山东大学软件学院7证明再由流守恒约束，V中每个顶点最多有一条出去的边流值为1。同理，U中每个顶点最多有一条进来的边流值为1。记M={eE|e上的流值0}，因此M中的任何两条边均不共享顶点，即，M是一个匹配，且|f*|=|M|。因此，显然有|f*||M|。2021/1/6山东大学软件学院8M-交错路：边在对集M和ME\中交错出现的路。M-增广路：起点和终点都不在V(M)中的M-交错路。顶点覆盖K：K是V(G)的子集，且G的每条边都至少有一个端点在K中。最小顶点覆盖K：不存在另外一个覆盖K’，使得KK。基本概念2021/1/6山东大学软件学院9顶点覆盖2021/1/6山东大学软件学院10定理6.8.1（Berge,1957）图G中的一个匹配M是最大匹配当且仅当G不包含M-增广路。（说明：G是一般图，不要求是二分图。）证：()。G上若有M-增广路，则可以使用这条路更新M得到基数更大（多1）的一个匹配，与M是最大匹配矛盾。()。假设M是一个匹配，图G上不含有M-增广路，而M不是最大匹配。于是，存在G上另外一个匹配M’，有|M’||M|。定理6.8.12021/1/6山东大学软件学院11令H是G上M’M的导出子图。由于H中的每个顶点最多只能和M中的一条边以及M’中的一条边关联，因此H中每个顶点的度都不超过2（都是1或者2）。因此，H的每个连通分支或者是边在M和M’中交错出现的路，或者是边在M和M’中交错出现的偶圈。由于在G中有|M’||M|，而H是M’和M的对称差，M’在H中的边数必然也M在H中的边数。这表明H中至少有一个连通分支，是一条起始于M’中的边又终止于M’中的边的路。由定义，这条路是一条M-增广路，与给定条件矛盾。证明2021/1/6山东大学软件学院12从图G=(S,T,E)的任意一个匹配M开始，比如空集。由S的一个未被匹配的顶点出发，用一个系统方法搜索一条M-增广路P。若P存在，则通过交换P在M和不在M中的边，便得到一个其基数增加1的匹配。然后从新的匹配开始，继续迭代，直到不存在M-增广路，则当前的匹配就是G的最大匹配。通过增广路求二分图上的最大匹配2021/1/6山东大学软件学院13输入：二分图G=(S,T,E)。输出：G的最大匹配M。1M。2对S中所有不在M中的顶点标号“”，然后将这些顶点都加入Q。/*Q是已标号但未检查的顶点的集合*/3whileQdo4从Q中取出一个顶点k，然后将k从Q中删除。5ifkSthen6对每条同k关联的边(k,j)M，若j尚未被标号，则给点j标号k，并将j加入Q。7else/*kT*/二分图上最大匹配的标号算法2021/1/6山东大学软件学院148ifk在M中then/*此时有kTV(M)*/9设(i,k)是关联于i、属于M的边（此时iS）。给点i标号k，并将i加入Q。10else/*此时有kT\V(M)*/11终止在k的一条增广路被找到。从k开始，反向追踪标号找到这条增广路P，路的起始顶点有标号“”。12用增广路P更新M。13删除G上所有的标号。重新对S中所有不在M中的顶点标号“”，然后将这些顶点都加入Q。14endif二分图上最大匹配的标号算法2021/1/6山东大学软件学院1515endif16endwhile17returnM。（此时S中没有标号的点的集合和T中已标号的点的集合构成对偶于M的最小顶点覆盖。）二分图上最大匹配的标号算法2021/1/6山东大学软件学院16例子123456789102021/1/6山东大学软件学院17例子12345678910找到一条增广路(1,7)。更新M。12021/1/6山东大学软件学院18例子12345678910找到一条增广路(2,8)。更新M。222021/1/6山东大学软件学院19例子12345678910找到一条增广路(3,10)。更新M。33332021/1/6山东大学软件学院20例子12345678910找到一条增广路(4,10,3,9)。更新M。410332021/1/6山东大学软件学院21例子12345678910找不到增广路，结束。55510872021/1/6山东大学软件学院22例子12345678910{红边}为最大匹配，{蓝色顶点}为顶点覆盖。55510872021/1/6山东大学软件学院23令|S|=m，|T|=n，假设mn。找一条增广路（或判断不能找到）标号算法最多进行O(mn)次检查（因为最多有这么多条边）。初始匹配最多被增广m次。所以，总的计算量为O(m2n)。时间复杂度分析2021/1/6山东大学软件学院24解释从S中未匹配的顶点开始，标号找M-增广路的过程，实际上是一个从S中未匹配的顶点开始进行广度优先搜索的过程。该过程与标准的广度优先搜索不完全相同。设搜索树的根位于第1层。区别仅在于，在搜索过程中，奇数层顶点（在S一侧）按广度优先展开；偶数层顶点（在T一侧）按M中的（唯一一条）边顺延（而不是按广度优先展开）。2021/1/6山东大学软件学院25解释2021/1/6山东大学软件学院26标号，找增广路v2v2u2u6v3v5v5u3u4u5v12021/1/6山东大学软件学院27找增广路过程中形成的搜索树虚线表示v5,u3相邻，但在对v5进行检查的过程中，u3已经标号，因此从v5不能对u3标号。2021/1/6山东大学软件学院28增广，得到一个更大的匹配2021/1/6山东大学软件学院29广度优先搜索的观点构造的辅助图从辅助图上入度为0的点v2开始的广度优先搜索2021/1/6山东大学软件学院30辅助图的构造顶点集=V。从v1到v2有一条有向边，当且仅当v2是从v1开始的增广路上下一个V中的顶点。2021/1/6山东大学软件学院31定理6.8.2（Hall,1935）设G=(S,T,E)是一个二分图。则：G含有匹配S中的每个点的匹配当且仅当SX，有XX。(*)证：()。假设G有一个匹配M，匹配了S中所有的顶点。任取S的一个子集X。则X通过M匹配到的点的集合Y是X的一个子集。因此XYX。()。反证。假设G满足(*)式，但G没有匹配S中所有顶点的匹配。令M*是G的一个最大匹配。则M*没有匹配S中所有的顶点。设u是一个未被M*匹配的顶点。Hall定理2021/1/6山东大学软件学院32令Z为从u出发经过M*-交错路可达的所有顶点的集合。由假设，Z中除u外所有的点都被M*匹配。（否则可找到一条M*-增广路，与M*是最大匹配矛盾。）令X=ZS，Y=ZT。则uX。由于X\{u}中的点与Y中的点在M*下匹配，因此|Y|=|X|1。由定义，Y是从X中的点出发“经过与u连通的M*-交错路上的一条边可达”的T中顶点的集合。(X)是从X中的点出发“经过任意一条边可达”的T中顶点的集合。因此，Y(X)。证明2021/1/6山东大学软件学院33任取X中的一点s，由X的定义，s通过M*-交错路与u相连。ut2X(X)st1考察与s相邻的(X)中的顶点t。若(s,t)M，如图中的(s,t1)，则t1位于从u到s的交错路上。若(s,t)M，如图中的(s,t2)，则从u到s的M*-交错路{(s,t2)}是一条从u到t2的交错路。证明2021/1/6山东大学软件学院34取遍X中所有的点s，就能遍历(X)中所有的点t。因此(X)是T中通过“只经过X中的点的M*-交错路”与u连通的顶点的集合。而Y是T中通过“M*-交错路”与u连通的所有顶点的集合。因此，(X)Y。即，(X)=Y。因此，|(X)|=|Y|=|X|1|X|，与(*)矛盾。证明2021/1/6山东大学软件学院35定理6.8.3（König，1931）在二分图中，最大基数对集的边数等于最小顶点覆盖的点数。证：设G=(S,T,E)是一个二分图，M*是G上的最大匹配。通过构造一个大小和|M*|相等的最小顶点覆盖来证明定理。令U表示S中M*未匹配的顶点的集合，Z表示从U中的顶点出发经过M*-交错路能够到达的顶点的集合。令X=ZS，Y=ZS。由Y的定义，可知M*匹配了Y中的所有的顶点；由Hall定理的证明，可知(X)=Y。König定理2021/1/6山东大学软件学院36定义K=(S\X)Y。YXUS\X则G中的每一条边至少有一个端点在K中（即，K是一个顶点覆盖）。否则，G中有一条边其一个端点在X中，另一个端点不在Y中，与(X)=Y矛盾。König定理2021/1/6山东大学软件学院37显然，|M*|=|K|。由于任意的顶点覆盖K’至少要覆盖M*中的所有边，因此|K’||M*|。现在顶点覆盖K有|K|=|M*|，因此K是最小顶点覆盖。König定理2021/1/6山东大学软件学院38指派问题：二分图上带权重的最大匹配实例：二分图G=(S,T,E)，边上定义有非负权重{we}。询问：图G上的一个匹配M，使得总权重eMwe最大。……1291018工人任务2021/1/6山东大学软件学院39将指派问题归约到最小费用流问题1.先进行预处理。通过增加权重为0的边，可以假定G是完全二分图。这是因为权重为0的边对最大权重匹配不产生影响。若S一侧和T一侧的顶点数目不一样多，比如|S|=m|T|=n，则向S一侧增加n–m个顶点，以及这些顶点到T一侧所有顶点权重为0的边。这样，可以假定S和T的顶点数目一样多。经过上面两个步骤，G是一个S和T的顶点数目相等的完全二分图。2021/1/6山东大学软件学院40将指派问题归约到最小费用流问题2.再将最大权重匹配问题变换到最小权重完美匹配问题。由于G是S和T大小相等的完全二分图，因此可以假定G上的最大权重匹配是一个完美匹配。定义W=max{wij|1i,jn}。对G上的每条边(i,j)，定义w’ij=W–wij。于是在(G,w)上计算最大权重完美匹配M等价于在(G,w’)上计算最小权重完美匹配M’，因为w(M)=nW–w(M’)。2021/1/6山东大学软件学院41将指派