图的匹配一、什么是图的匹配1.图的定义无向图：无向图G 是指非空有限集合V G ，和V G 中某些元素的无序对的集合E G ，构成的二元组(V G ，E G )。

V G 称为G 的顶点集，其中的元素称为G 的顶点。

E G 称为G 的边集，其中的元素称为G 的边。

在不混淆的情况下，有时记V ＝V G ，E ＝E G 。

如果V ＝{v 1,…,v n }，那么E 中的元素e 与V 中某两个元素构成的无序对(v i ，v j )相对应，记e ＝v i v j ，或e ＝v j v i 。

在分析问题时，我们通常可以用小圆圈表示顶点，用小圆圈之的连线表示边。

二分图：设G 是一个图。

如果存在V G 的一个划分X ，Y ，使得G 的任何一条边的一个端点在X 中，另一个端点在Y 中，则称G 为二分图，记作G ＝(X ，Y ，E)。

如果G 中X 的每个顶点都与Y 的每个顶点相邻，则称G 为完全二分图。

2.匹配的相关概念设G ＝(V ，E)是一个图，E M ⊆，如果M 不含环且任意两边都不相邻，则称M 为G 的一个匹配。

G 中边数最多的匹配称为G 的最大匹配。

对于图G ＝(V ，E)，在每条边e 上赋一个实数权w(e)。

设M 是G 的一个匹配。

定义∑∈=me e w M w )()(，并称之为匹配M 的权。

G 中权最大的匹配称为G 的最大权匹配。

如果对一切，e ∈E ，w(e)=1,则G 的最大权匹配就是G 的最大匹配。

设M 是图G=(V ,E)的一个匹配，v i ∈V 。

若v i 与M 中的边相关联，则称v i 是M 饱和点，否则称v i 为M 非饱和点。

如果G 中每个顶点都是M 饱和点，则称M 为G 的完美匹配。

设M 是G 的一个匹配，P 是G 的一条链。

如果P 的边交替地一条是M 中的边，一条不是M 中的边，则称P 为M 交错链。

类似地，我们可以定义G 的交错圈。

易知，G 的交错圈一定是偶圈。

一条连接两个不同的M 非饱和点的M 交错链称为M 增广链。

两个集合S 1与S 2的“异或”操作S 1⊕S 2是指集合S 1⊕S 2＝（S 1∩S 2）\（S 1∪S 2） 容易看出，设M 是G 的匹配，P 是G 中的M 增广链、则M ⊕P 也是G 的匹配，而且1+=⊕M P M 。

图表 1 “异或”操作可以证明，G 中匹配M 是最大匹配当且仅当G 中没有M 增广链。

二、匹配算法1.二分图的最大匹配设有M个工人x1, x2, …, x m，和N项工作y1, y2, …, y n，规定每个工人至多做一项工作，而每项工作至多分配一名工人去做。

由于种种原因，每个工人只能胜任其中的一项或几项工作。

问应怎样分配才能使尽可能多的工人分配到他胜任的工作。

这个问题称为人员分配问题。

人员分配问题可以用图的语言来表述。

令X={x1, x2, …, x m}，Y={y1, y2, …,y n}，构造二分图G=(X, Y, E)如下：对于1≤i≤m，1≤j≤n，当且仅当工人xi 胜任工作yi时，G中有一条边xiyi，于是人员分配问题就成为在G中求一个最大匹配的问题。

求最大匹配常用匈牙利算法，它的基本思想是：对于已知的匹配M，从X中的任一选定的M非饱和点出发，用标号法寻找M增广链。

如果找到M增广链，则M就可以得到增广；否则从X中另一个M非饱和点出发，继续寻找M增广链。

重复这个过程直到G中不存在增广链结束，此时的匹配就是G的最大匹配。

这个算法通常称为匈牙利算法，因为这里介绍的寻找增广链的标号方法是由匈牙科学者Egerváry最早提出来的。

图表2 匈牙利算法理解了这个算法，就不难写出人员分配问题的解答了。

在给出程序之前，先做一些假设：为了简单起见，假设工人数等于工作数，即N=M，且N≤100，这里，N也可以看作是二分图的|X|和|Y|。

数据从文件input.txt中读入，首先是N和|E|，下面|E|行每行两个数(I, J)，表示工人I 可以胜任工作J，即二分图中的边x i y j。

结果输出到文件output.txt，第一行是最大匹配数s，下面s行每行两个数(I, J)，表示分配工人I做工作J，即匹配边x i y j。

下面是人员分配问题的参考解答，该算法的时间复杂度为O(n3)。

Program match;constmaxn = 100;varmap: array[1 .. maxn, 1 .. maxn] of boolean; {保存二分图} cover: array[1 .. maxn] of boolean; {标记一个点是否为饱和点} link: array[1 .. maxn] of integer; {保存匹配边}n: integer; {顶点数}procedure init; {读入}vari, e, x, y: integer;beginassign(input, 'input.txt'); reset(input);readln(n, e);for i := 1 to e do beginreadln(x, y); map[x, y] := true;end;close(input);end;function find(i: integer): boolean; {从i出发，找增广链}vark, q: integer;beginfind := true;for k := 1 to n doif map[i, k] and not cover[k] then beginq := link[k]; link[k] := i; cover[k] := true;if (q = 0) or find(q) then exit;link[k] := q;end;find := false;end;procedure main; {求匹配}vari: integer;beginfor i := 1 to n do beginfillchar(cover, sizeof(cover), 0);find(i);end;end;procedure print; {输出}vari, s: integer; beginassign(output, 'output.txt'); rewrite(output);s := 0; for i := 1 to n do if link[i] <> 0 then s := s + 1; writeln(s);for i := 1 to n do if link[i] <> 0 then writeln(link[i], ' ', i); close(output); end;begin init; main; print; end.2.二分图的最大权匹配对于上面的人员分配问题，如果还考虑到工人做工的效率，就可以提出所谓的分派问题：应该怎样分配才能使总的效率最大？同上一节，我们可以构造一个二分图G ，如果把工人x i 做工作y i 的效率w ij 看作是G 中边x i y i 的权，则分派问题就相当于在赋权二分图G 中求一个最大全匹配。

由线性规划的知识，求二分图G 的最大权匹配，只需在匈牙利算法的基础上少许改进即可。

它的基本思想是，对二分图的顶点编号，然后根据编号构造一个新的二分图G ’，最后把求G 的最大权匹配转换为求G ’的完美匹配。

下面的这条定理是这个算法的理论基础。

定理：设M 是赋权图（权非负）的完全二分图),,,(w E Y X G =的一个完美匹配，这里Y X =。

如果存在一组},{j i μλ，满足),,2,1,(,n j i w ij j i =≥+μλ，并且对一切M y x j i ∈，均有ij j i w =+μλ，则M 是G 的最大权匹配。

下面，给出求最大权匹配的程序。

输入文件中首先是N 和|E|，下面|E|行每行三个数(I, J, W)，表示工人I 做工作J 的效率是W 。

程序输出包括每个工人的选择和最后的总效益。

其它假设参见上一节的算法假设。

这个算法的时间复杂度也是O(n 3)。

Program maxmatch; constmaxn = 100; varmap: array[1 .. maxn, 1 .. maxn] of integer; {保存二分图}link, lx, ly: array[1 .. maxn] of integer; {保存匹配边和每个点的标号} x, y: array[1 .. maxn] of boolean; {标记一个点是否为饱和点} n: integer; {顶点数}procedure init; {读入} vari, e, x, y: integer; beginassign(input, 'input.txt'); reset(input);for i := 1 to e do readln(x, y, map[x, y]);close(input);end;function find(v: integer): boolean; {从v出发，找增广链} vari, k: integer;beginfind := true;x[v] := true;for i := 1 to n doif not y[i] and (lx[v] + ly[i] = map[v, i]) then beginy[i] := true; k := link[i]; link[i] := v;if (k = 0) or find(k) then exit;link[i] := k;end;find := false;end;procedure main; {求最大权匹配}vari, j, k, d: integer;beginfillchar(lx, sizeof(lx), 0); fillchar(ly, sizeof(ly), 0);for i := 1 to n dofor j := 1 to n doif map[i, j] > lx[i] then lx[i] := map[i, j];for k := 1 to n dorepeatfillchar(x, sizeof(x), 0); fillchar(y, sizeof(y), 0);if find(k) then break;d := maxint;for i := 1 to n do if x[i] thenfor j := 1 to n do if not y[j] thenif lx[i] + ly[j] - map[i, j] < d thend := lx[i] + ly[j] - map[i, j];for i := 1 to n do if x[i] then lx[i] := lx[i] - d;for i := 1 to n do if y[i] then ly[i] := ly[i] + d;until false;end;procedure print; {输出}vari, s: integer;beginassign(output, 'output.txt'); rewrite(output);s := 0;for i := 1 to n do s := s + map[link[i], i];close(output);end;begininit;main;print;end.3. 任意图的匹配任意图的最大匹配算法也是建立在找增广链的基础上的，只是任意图的增广链要比二分图难找得多。