一、定义与定理
匹配:设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 阅读(536)
评论(0) 编辑 收藏 引用 所属分类:
图论