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

1、2021-12-23第第6章章 图与网络分析图与网络分析6.7 最大匹配问题最大匹配问题2021-12-23山东大学 软件学院2最大对集（匹配）问题二分图的对集，基本概念，主要定理二分图的对集，基本概念，主要定理二分图的最大匹配算法二分图的最大匹配算法二分图的带权重的最大匹配二分图的带权重的最大匹配分派问题及算法分派问题及算法2021-12-23山东大学 软件学院3基本概念2021-12-23山东大学 软件学院4使用最大流算法求二分图上的最大匹配给定二分图给定二分图G = (V, U, E)，构造流网络。，构造流网络。增加一个源点增加一个源点 s，从，从 s 到到 V 中每个顶点引一条有向边。

2、中每个顶点引一条有向边。增加一个目标顶点增加一个目标顶点 t，从，从 U 中每个顶点向中每个顶点向 t 引一条有向边。引一条有向边。E中的边均从中的边均从 V 指向指向 U。记得到的流网络为记得到的流网络为G = (V, E)。G中的每条边均为单位容中的每条边均为单位容量。量。计算计算G上从上从 s 到到 t 的最大流。的最大流。E 中的饱和边即构成中的饱和边即构成 G 上的一个最大匹配。上的一个最大匹配。2021-12-23山东大学 软件学院5例子2021-12-23山东大学 软件学院6定理定理定理：记：记G上的最大流为上的最大流为f*，流值为，流值为|f*|。G上的最大匹配上的最大匹配为为

3、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

4、上每条边的流值不是上每条边的流值不是0就是就是1。2021-12-23山东大学 软件学院7证明再由流守恒约束，再由流守恒约束，V中每个顶点最多有一条出去的边流值为中每个顶点最多有一条出去的边流值为1。同理，。同理，U中每个顶点最多有一条进来的边流值为中每个顶点最多有一条进来的边流值为1。记记M = e E | e上的流值上的流值 0，因此，因此M中的任何两条边均不中的任何两条边均不共享顶点，即，共享顶点，即，M是一个匹配，且是一个匹配，且|f*| = |M|。因此，显然有因此，显然有|f*| |M|。2021-12-23山东大学 软件学院8基本概念2021-12-23山东大学 软件学院9顶点覆

5、盖2021-12-23山东大学 软件学院10定理6.8.12021-12-23山东大学 软件学院11证明2021-12-23山东大学 软件学院12通过增广路求二分图上的最大匹配2021-12-23山东大学 软件学院13二分图上最大匹配的标号算法2021-12-23山东大学 软件学院14二分图上最大匹配的标号算法2021-12-23山东大学 软件学院15二分图上最大匹配的标号算法2021-12-23山东大学 软件学院16例子123456789102021-12-23山东大学 软件学院17例子12345678910找到一条增广路找到一条增广路(1, 7)。更新。更新M。12021-12-23山东大

6、学 软件学院18例子12345678910找到一条增广路找到一条增广路(2, 8)。更新。更新M。222021-12-23山东大学 软件学院19例子12345678910找到一条增广路找到一条增广路(3, 10)。更新。更新M。33332021-12-23山东大学 软件学院20例子12345678910找到一条增广路找到一条增广路(4, 10, 3, 9)。更新。更新M。410332021-12-23山东大学 软件学院21例子12345678910找不到增广路，结束。找不到增广路，结束。55510872021-12-23山东大学 软件学院22例子12345678910红边红边为最大匹配，为最大

7、匹配，蓝色顶点蓝色顶点为顶点覆盖。为顶点覆盖。55510872021-12-23山东大学 软件学院23时间复杂度分析2021-12-23山东大学 软件学院24解释从从S中未匹配的顶点开始，标号找中未匹配的顶点开始，标号找M-增广路的过程，实际上增广路的过程，实际上是一个从是一个从S中未匹配的顶点开始进行广度优先搜索的过程。中未匹配的顶点开始进行广度优先搜索的过程。该过程与标准的广度优先搜索不完全相同。该过程与标准的广度优先搜索不完全相同。设搜索树的根位于第设搜索树的根位于第1层。区别仅在于，在搜索过程中，奇层。区别仅在于，在搜索过程中，奇数层顶点（在数层顶点（在S一侧）按广度优先展开；偶数层顶

8、点（在一侧）按广度优先展开；偶数层顶点（在T一侧）按一侧）按M中的（唯一一条）边顺延（而不是按广度优先中的（唯一一条）边顺延（而不是按广度优先展开）。展开）。2021-12-23山东大学 软件学院25解释2021-12-23山东大学 软件学院26标号，找增广路v2v2u2u6v3v5v5u3u4u5v12021-12-23山东大学 软件学院27找增广路过程中形成的搜索树虚线表示v5, u3相邻，但在对v5进行检查的过程中，u3已经标号，因此从v5不能对u3标号。2021-12-23山东大学 软件学院28增广，得到一个更大的匹配2021-12-23山东大学 软件学院29广度优先搜索的观点构造的辅

9、助图从辅助图上入度为0的点v2开始的广度优先搜索2021-12-23山东大学 软件学院30辅助图的构造顶点集顶点集 = V。从从v1到到v2有一条有向边，当且仅当有一条有向边，当且仅当 v2是从是从v1开始的增广路上开始的增广路上下一个下一个V中的顶点。中的顶点。2021-12-23山东大学 软件学院31Hall定理2021-12-23山东大学 软件学院32证明2021-12-23山东大学 软件学院33证明2021-12-23山东大学 软件学院34证明2021-12-23山东大学 软件学院35Knig定理2021-12-23山东大学 软件学院36Knig定理2021-12-23山东大学 软件学

10、院37Knig定理2021-12-23山东大学 软件学院38指派问题：二分图上带权重的最大匹配实例：二分图实例：二分图G = (S, T, E)，边上定义有非负权重，边上定义有非负权重we。询问：图询问：图G上的一个匹配上的一个匹配M，使得总权重，使得总权重e M we最大。最大。1291018工人任务2021-12-23山东大学 软件学院39将指派问题归约到最小费用流问题1. 先进行预处理。先进行预处理。通过增加权重为通过增加权重为0的边，可以假定的边，可以假定G是完全二分图。这是因是完全二分图。这是因为权重为为权重为0的边对最大权重匹配不产生影响。的边对最大权重匹配不产生影响。若若S一侧和

11、一侧和T一侧的顶点数目不一样多，比如一侧的顶点数目不一样多，比如|S| = m 0的顶点的顶点i出发的出发的增广路。增广路。若这样的增广路能够找到，则用它更新当前的若这样的增广路能够找到，则用它更新当前的M后，后，(6.8.5)和和(6.8.7)仍然是满足的，而仍然是满足的，而(6.8.6)比以前多一些被满足。比以前多一些被满足。若这样的增广路找不到，则算法调整若这样的增广路找不到，则算法调整ui和和vj的值。的值。当没有匹配的点的当没有匹配的点的ui调整到调整到0时，时，(6.8.6)全部满足，算法求全部满足，算法求到最优解。到最优解。2021-12-23山东大学 软件学院46匈牙利算法Ha

12、rold Kuhn, 1955 1 M ； i S, ui maxwij； j T, vj 0, j +。 2 给给S中未匹配的顶点标中未匹配的顶点标“”。 3 while S中有未检查的标号点中有未检查的标号点 或或 (*) T中有中有 j = 0的未检查的标号点的未检查的标号点 (*) do 4 找一个符合找一个符合(*)或或(*)的顶点的顶点k。 5 if k S then 6 对于每条边对于每条边(k, j) M，若，若uk + vj wij 0, j S， min 1, 2。17 对对S中的每个有标号的顶点，中的每个有标号的顶点，ui ui ；对对T中每个中每个 j = 0的顶点，的

13、顶点， vj vj + ；对对T中每个有标号且中每个有标号且 j 0的顶点，的顶点， j j 。18 若若 1，则回到第，则回到第3步。步。19 /* 否则，找到了最大权重匹配否则，找到了最大权重匹配 */return M。2021-12-23山东大学 软件学院49例子1234567812322132423uivj标号标号j_44440000+第1阶段，初始化。2021-12-23山东大学 软件学院50例子1234567812322132423uivj标号标号j11_4444000032+第1阶段，处理顶点1。2021-12-23山东大学 软件学院51例子1234567812322132423

14、uivj标号标号j212_44440000122+第1阶段，处理顶点2。2021-12-23山东大学 软件学院52例子1234567812322132423uivj标号标号j2323444400001122第1阶段，处理顶点3。2021-12-23山东大学 软件学院53例子1234567812322132423uivj标号标号j2424444400001021第1阶段，处理顶点4。2021-12-23山东大学 软件学院54例子1234567812322132423uivj标号标号j2424444400001021第1阶段，处理顶点6，找到一条增广路(4, 6)。2021-12-23山东大学 软

15、件学院55例子1234567812322132423uivj标号标号j_44440000+第2阶段，初始化。2021-12-23山东大学 软件学院56例子1234567812322132423uivj标号标号j_11_4444000032+第2阶段，处理顶点1。2021-12-23山东大学 软件学院57例子1234567812322132423uivj标号标号j_212_44440000122+第2阶段，处理顶点2。2021-12-23山东大学 软件学院58例子1234567812322132423uivj标号标号j_2323444400001122第2阶段，处理顶点3。2021-12-23山

16、东大学 软件学院59例子1234567812322132423uivj标号标号j_2323444400001122第2阶段，所有点都检查完毕，计算。1 = 42 = 1 = 12021-12-23山东大学 软件学院60例子1234567812322132423uivj标号标号j_2323333400000011第2阶段，所有点都检查完毕，调整ui、vj、j。1 = 42 = 1 = 12021-12-23山东大学 软件学院61例子1234567812322132423uivj标号标号j_2323333400000011第3阶段，处理顶点5，找到增广路(2, 5)。2021-12-23山东大学

17、软件学院62例子1234567812322132423uivj标号标号j_33340000+第4阶段，初始化。2021-12-23山东大学 软件学院63例子1234567812322132423uivj标号标号j_11_3334000021+第4阶段，处理顶点1。2021-12-23山东大学 软件学院64例子1234567812322132423uivj标号标号j_13_33334000020+1第4阶段，处理顶点3。2021-12-23山东大学 软件学院65例子1234567812322132423uivj标号标号j_613_33334000020+1第4阶段，处理顶点6。2021-12-2

18、3山东大学 软件学院66例子1234567812322132423uivj标号标号j_61343333400002021第4阶段，处理顶点4。2021-12-23山东大学 软件学院67例子1234567812322132423uivj标号标号j_61343333400002021第4阶段，处理完所有标号的顶点。计算。1 = 32 = 1 = 12021-12-23山东大学 软件学院68例子1234567812322132423uivj标号标号j_61343232301001010第4阶段，调整ui、vj、j。1 = 32 = 1 = 12021-12-23山东大学 软件学院69例子123456

19、7812322132423uivj标号标号j_61343232301001010第5阶段，处理顶点8，找到增广路(3, 8)。2021-12-23山东大学 软件学院70例子1234567812322132423uivj标号标号j_23230100+第6阶段，初始化。2021-12-23山东大学 软件学院71例子1234567812322132423uivj标号标号j_11_2323010011+第6阶段，处理顶点1。2021-12-23山东大学 软件学院72例子1234567812322132423uivj标号标号j_11_2323010011+第6阶段，处理完所有顶点，计算。1 = 22 = 1 = 12021-12-23山东大学 软件学院73例子1234567812322132423uivj标号标号j_11_1323010000+第6阶段，调整ui、vj、j。1 = 22 = 1 = 12021-12-23山东大学 软件学院74例子1234567812322132423uivj标号标号j5_11_1323010000+第7阶段，处理顶点5。2021-12-23山东大学 软件学院75例子1234567812322132423uivj标号标号j5_611_1323010000