一、定义与定理
匹配：设G(V, E)为无环图，设M为E的一个非空子集，如果M中的任意两条边在G中不相邻，则称M是图G中的一个匹配。若对图G的任何匹配M'，均有|M'|≤|M|，则称M为G的最大匹配。
饱和点：设M是图G中的匹配，G中与M中的边关联的顶点称为M饱和点，否则称为M非饱和点。若图中顶点均是M饱和点，则称M为G的完美匹配。
M交错路：设P是G的一条路，且在P中，M的边和E-M的边交错出现，则称P是G的一条M交错路。若M交错路P的两个端点为M非饱和点，则称P为M可增广路。
根在x的M交错子图：设x为G中M非饱和点。G中由起点为x的M交错路所能连接的顶点集所导出的G的导出子图。
S的邻集：设S为G的任一顶点集，G中与S的顶点邻接的所有顶点的集合，称为S的邻集，记作N(S)。
最优匹配：对于一个加权二部图，一个权最大的匹配叫作最优匹配。
可行定标：映射l：V(G)→R，满足对G的每条边e={u, v}，均有l(u)+l(v)≥w(u, v)，其中w(u, v)表示边e的权，则称l为G的可行顶标。令El={(u, v) | {u, v}∈E(G)，l(u)+l(v)=w(u, v)}，Gl为以El为边集的G的生成子图，则称Gl为l等子图。
二、最大匹配（匈牙利算法）
描述：
（1）G是具有划分(V1, V2)的二分图，任给初始匹配M；
（2）若M饱和V1则结束；
（3）否则，在V1中找一M非饱和点，，置S={x}， T为空；
（4）若N(S) = T，则停止，否则任选一点y∈N(S)-T；
（5）若y为M非饱和点，则求一条从x到y的M可增广路P，置M为M异或P并转（2）；
（6）否则，由于y是M的饱和点，故M中有一边{y, u}，置S = S∪{u}，T = T∪{y}，转（4）。
实现：
1 HUNGARY
2 for i : 1 to |V2|
3 do match[i] = 0
4 for each vertex u in V1
5 do for i : 1 to |V2|
6 do visit[i] = false
7 DFS(u)
8 DFS(u)
9 for each vertex v in V2
10 if (u, v) in E(G) and visit[v] is false
11 then visit[v]=true
12 if match[v] is 0 or DFS(match[v]) is true
13 then match[v] = u
14 return true
15 return false
说明：第7行的DFS(u)过程，当存在从u开始的M可增广路，则返回true，并完成M的扩展，此时|M|加一。如果返回false，则表示不存在M可增广路。
示例：POJ 1274 解题报告。
三、最优匹配（KM算法）
描述：
（1）从任意可行顶标l开始，确定l等子图Gl，并且在Gl中选取匹配M。若M饱和V1，则M是完美匹配，也即M是最优匹配，算法终止；
（2）否则，运用匈牙利算法，终止于S属于V1，T属于V2且使对于Gl，N(S)=T。令al=min{l(x)+l(y)-w(x, y) | x∈S, y∈V2-T}，令l'(u)=l(u)-al如果u∈S；l'(u)=l(u)+al如果u∈T；l'(u)=l(u)，其它。用l'代替l，用Gl'代替Gl转入（1）。
实现：
1 KUHN-MUNKRES(G)
2 for each vertex u in V1
3 do lx[u] = max{w[u][v] | (u, v) in E(G)}
4 for each vertex v in V2
5 do ly[v] = 0
6 for each vertex u in V1
7 do while(true)
8 do for each vertex u in V1
9 do vx[u] = false
10 for each vertex v in V2
11 do vy[v] = false
12 slack[v] = MAX
13 if DFS(u) is true
14 then break
15 d = min{slack[v] | v in V2 and vy[v] is false}
16 for each vertex u in V1
17 do lx[u] = lx[u] - d
18 for each vertex v in V2
19 do ly[v] = ly[v] + d
20 DFS(u)
21 vx[u] = true
22 for each vertex v in V2
23 do if lx[u]+ly[v]==w[u][v] and vy[v] is false
24 then vy[v] = true
25 if match[v] is NIL or DFS(match[v])
26 then match[v] = u
27 return true
28 else if lx[u]+ly[v]>w[u][v]
29 then slack[v] = min{slack[v], lx[u]+ly[v]-w[u][v]}
30 return false
示例：POJ 2195 解题报告
posted on 2009-06-29 14:48
Icyflame 阅读(542)
评论(0) 编辑 收藏 引用 所属分类:
图论