【正文】 5 (f1,m3), (f2,m1) ,(f3,m2) ,(f4,m5) ,(f5,m4) 匹配問題是運籌學(xué)的重要問題之一，也是圖論的重要內(nèi)容，它在所謂 “ 人員分配問題 ” 和 “ 最優(yōu)分配問題 ”中有重要作用。 f1 f2 m1 f3 f4 f5 m2 m3 m4 m5 167。第五章 匹配 167。 1 最大匹配－ 1 ? 具體問題描述： 有 n個女士和 n個男士參加舞會，每位女士與其中若干位男士相識，每位男士與其中若干位女士相識，問如何安排，使得盡量多配對的男女舞伴相識。 1 匹配 167。 ? 假定有一個男生有窮集合，其中每個男生認(rèn)識一些女生，在什么條件下每個男生都可以和他認(rèn)識的女生配對？ ? 類似的工作分配問題：現(xiàn)有 n個人， m份工作，每個人有其擅長的工作。 1 最大匹配－定義 ? 定義 ：若圖 G=(V,E)的頂點可以分成 X， Y兩個子集，每個子集里的頂點互不相鄰，這樣的圖稱為 二分圖 。 1 最大匹配－定義 1 ? 定義 ：若 M是圖 G=(V,E)的邊子集，且 M中的任意兩條邊在 G中不相鄰，則稱 M為 G中的一個 匹配 ， M中的每條邊的兩個端點稱為是 M飽和的 的。 1 最大匹配－定義 2 ? 定義 ：若圖 G中每個頂點均被 M許配時，稱M為 G中的一個 完美匹配 。 1 最大匹配－定義 3 ? 定義 ：圖 G中邊數(shù)最多的匹配 M，稱為 G中的一個 最大匹配 。 1 最大匹配－定義 4 ? 定義 ：若匹配 M的某邊和頂點 v關(guān)聯(lián)，稱 v是M飽和的 ，否則就是 M不飽和的 。 1 最大匹配－定義 5 ? 定義 ：若 M是圖 G的一個匹配，若從 G中一個頂點到另一個頂點存在一條道路，此路徑由屬于 M和不屬于 M的邊交替出現(xiàn)組成的，則稱此路徑為 M交錯路 。 1 最大匹配－定義 6 ? 定義 ：若交錯路的兩個端點為關(guān)于 M的不飽和頂點時，稱此交互道為 可增廣道路 。 f1 f2 m1 f3 f4 f5 m2 m3 m4 m5 167。 1 3 2 1 3 2 4 5),(f5,m4)} 167。 M={(f1,m3), (f2,m1) ,(f3,m2) ,(f5,m5)} f1 f2 m1 f3 f4 f5 m2 m3 m4 m5 [引理 ] 設(shè) P是匹配Ｍ 可增廣道路，則 P?M是一個比 M更大的匹配，且 | P?M｜＝ |M|+1. [定理 1] (Berge) 設(shè) G=(V,E)， M為 G中匹配，則 M為 G的最大匹配當(dāng)且僅當(dāng) G中不存在 M?可增廣道。矛盾！ 充分性 ：如果有最大匹配 M’, |M’||M|. 考慮 M?M’， 在 可增廣路中，第一條邊與最后一條邊都不是 中的邊，因而 可增廣路中屬于 的邊數(shù)比不在 中邊數(shù)少一條。 其中回路包含相同數(shù)目的 M邊和 M’邊。 2 Hall定理 設(shè)有 m個人， n項工作，每個人會做其中的若干項工作，能不能適當(dāng)安排，使得每個人都有工作做？ w1 w2 m1 w3 w4 w5 m2 m3 m4 167。但如果每個人能做的工作越多，越容易實現(xiàn)。 2 Hall定理－ 1 ? Hall定理 (1935)： 二分圖 G存在一匹配 M，使得 X的所有頂點關(guān)于 M飽和的 充要條件 是：對于 X任一子集A，及與 A鄰接的點集為 N(A)，恒有 ：|N(A)|≥|A|。 3 人員分派問題 1965年，匈牙利著名數(shù)學(xué)家 Edmonds設(shè)計了一種求最大匹配的算法，稱為匈牙利(Hungarian)算法。在什么條件下每個人都可以得到一份他擅長的工作？如何分配？ 167。 3 匈牙利算法例 用匈牙利算法求下圖的最大匹配： 例 x1 x2 y1 x3 x4 x5 y2 y3 y4 y5 167。 3 匈牙利算法例解 1 （ 3）在 X中找一個非飽和點 x0， V1={x0}， V2=空集 （ 4）若 N(V1)=V2則停止，否則任選一點 y∈ N(V1)V2 解 x1 x2 y1 x3 x4 x5 y2 y3 y4 y5 M={(x1,y1 ),(x3,y5),(x5,y3)} V1={x2},V2=空集 N(V1)={y2, y3} 167。 3 匈牙利算法例解 3 （ 4）若 N(V1)=V2則停止，否則任選一點y∈ N(V1)V2； 解 x1 x2 y1 x3 x4 x5 y2 y3 y4 y5 M={(x1,y1 ),(x3,y5),(x5,y3)} V1={x2,x5}； V2={y3} N(V1)={y2,y3,y4,y5} 167。 3 匈牙利算法例解 5 （ 4）若 N(V1)=V2則停止，否則任選一點y∈ N(V1)V2； 解 x1 x2 y1 x3 x4 x5 y2 y3 y4 y5 M={(x1,y1 ),(x3,y5),(x5,y3)} V1={x2,x5, x3}； V2 ={y3 ,y5}； N(V1)={y2,y3,y4,y5} 167。 3 匈牙利算法例解 7 （ 2）若 X已經(jīng)飽和，結(jié)束；否則轉(zhuǎn)（ 3）； （ 3）在 X中找一個非飽和點 x0， V1={x0}， V2={} （ 4）若 N(V1)=V2則停止，否則任選一點y∈ N(V1)V2 解 x1 x2 y1 x3 x4 x5 y2 y3 y4 y5 V1={x4}； V2 =空集 M={(x1,y1 ),(x2,y3),(x3,y2),( x5,y5)} N(V1)={y3} 167。 3 匈牙利算法例解 9 （ 4）若 N(V1)=V2則停止，否則任選一點y∈ N(V1)V2 解 x1 x2 y1 x3 x4 x5 y2 y3 y4 y5 M={(x1,y1 ),(x2,y3),(x3,y2),( x5,y5)} V1={x4,x2,}； V2 ={y3 } N(V1)={y2,y3} 167。 3 匈牙利算法例解 11 （ 4）若 N(V1)=V2則停止，否則任選一點y∈ N(V1)V2 解 x1 x2 y1 x3 x4 x5 y2 y3 y4 y5 M={(x1,y1 ),(x2,y3),(x3,y2),( x5,y5)} V1={x4,x2,x3}； V2={y3,y2} N(V1)={y2,y3,y5} 167。 3 匈牙利算法例解 13 （ 4）若 N(V1)=V2則停止，否則任選一點y∈ N(V1)V2 解 x1 x2 y1 x3 x4 x5 y2 y3 y4 y5 M={(x1,y1 ),(x2,y3),(x3,y2),( x5,y5)} V1={x4,x2,x3,x5}； V2 ={y3,y2,y5} N(V1)={y2,y3,y5,y4} 167。 3 匈牙利算法例解 15 （ 2）若 X已經(jīng)飽和，結(jié)束；否則轉(zhuǎn)（ 3）； 解 x1 x2 y1 x3 x4 x5 y2 y3 y4 y5 這時， M={(x1,y1 ),(x2,y2),(x3,y5),( x4,y3 ),(x5,y4)} 就是所求的最大匹配。 4 最佳匹配 公司里有 n名工作人員，他們每個人都能承擔(dān) n項工作的其中若干項，因為每個人的特長不同，所以對每項工作創(chuàng)造的價值也有所不同。 4 最佳匹配 x對每項工作創(chuàng)造的價值的如右邊的矩陣所表示： x1 x2 y1 x3 x4 x5 y2 y3 y4 y5 3 5 5 4 1 2 2 0 2 2 2 4 4 1 0 0 1 1 0 0 1 2 1 3 3 C= x1 x2 x3 x4 x5 y1 y2 y3 y4 y5 167。 167。 167。令 Gl是以 El為邊集的生成子圖，如果有 Gl完美匹配 M，則 M即為 G的最佳匹配。 5 最佳匹配算法 3 ? KM算法： （ 1）選定初始正常標(biāo)頂 l，構(gòu)作圖 Gl，在 Gl中用匈牙利算法求一個最大匹配； （ 2）若 X飽和則結(jié)束，此時所得匹配就是最佳匹配，否則在 X中任選一個非飽和點 x0，令 V1={x0} ， V2={}； （ 3）若 NGl(V1)=V2，則取 α=min(l(xi)+l(yj)cij)，其中 xi∈ V1， yj∈ NG(V1) V2，使得 l(v)α v∈ V1 l(v)= l(v)+α v∈ V2 l(v) 其他 重新構(gòu)作圖 Gl，在 NGl(V1)V2任取一點 y，