一、定義與定理
匹配：設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 閱讀(587)
評論(0) 編輯 收藏 引用 所屬分類:
圖論