版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、-這是個問題-二分圖現(xiàn)有若干大齡男女青年,要安排相親,每位女青年只能和一位男青年結(jié)為對象,為了使得每位女青年都有對象,可供選擇的男青年至少要和女青年一樣多,可女青年不會草率地處理終生大事,她們都有一個自己認為可以接受的配偶的名單。那么: 1.每個女青年是否都可以和自己名單里的男青年結(jié)為對象? 2.什么條件下可以滿足所有女青年的心愿?如果不能滿足,那么最多有幾位女青年可以找到心儀的對象? 3.如何匹配,才能使結(jié)為對象后的家庭最為美滿?二分圖及匹配算法Made by siang01 02 03 04 05內(nèi)容大綱二分圖概述-二分圖概述-“二分”指中國人民銀行在以前發(fā)行的一種鈔票面值。二分圖又稱作二
2、部圖,是圖論中的一種特殊模型。 設(shè)G=(V,E)是一個無向圖,如果頂點V可分割為兩個互不相交的子集(A,B),并且圖中的每條邊(i,j)所關(guān)聯(lián)的兩個頂點i和j分別屬于這兩個不同的頂點集(i in A,j in B),則稱圖G為一個二分圖。二分圖最大匹配-二分圖匹配-給定一個二分圖G,M為G邊集的一個子集,如果M滿足當中的任意兩條邊都不依附于同一個頂點,則稱M是一個匹配匹配。極大匹配極大匹配是指在當前已完成的匹配下,無法再通過增加未完成匹配的邊的方式來增加匹配的邊數(shù)。最大匹配最大匹配是所有極大匹配當中邊數(shù)最大的一個匹配。選擇這樣的邊數(shù)最大的子集稱為圖的最大匹配問題。如果一個匹配中,圖中的每個頂點
3、都和圖中某條邊相關(guān)聯(lián),則稱此匹配為完全匹配,也稱作完備匹配完備匹配。-算法的前奏-內(nèi)容:圖G的匹配M是最大匹配當且僅當G中沒有M-增廣路。學習二分圖匹配需要用到3個定理:Berge定理,Hall定理,Konig定理給定圖G的一個匹配M。如果一條路徑的邊交替出現(xiàn)在M中和不出現(xiàn)在M中,則這條路徑為一條M-交錯路徑。路徑的起始點和終點未被M匹配的M-交錯路徑稱為M-增廣路徑。設(shè)增廣路徑M 則|M|=|M|+11.Berge定理2.Hall定理對于G=V,E,SV,V中與S通過邊直接相連的點稱為S的鄰集,記做N(S)內(nèi)容:在二分圖G=X,Y;E中,存在一個匹配M,使得X中所有點都被M匹配當且僅當對于任
4、意SV,都有|N(S)|=|S|-匈牙利算法-匈牙利算法是由匈牙利數(shù)學家Edmonds于1965年提出,因而得名。匈牙利算法是基于Hall定理中充分性證明的思想,它是部圖匹配最常見的算法,該算法的核心就是尋找增廣路徑,它是一種用增廣路徑求二分圖最大匹配的算法。算法輪廓:置M為空找出一條增廣路徑P,通過異或操作獲得更大的匹配M代替M重復操作直到找不出增廣路徑為止-Hopcroft-karp算法-為了降低時間復雜度,可以在增廣匹配集合M時,每次尋找多條增廣路徑。這樣就可以進一步降低時間復雜度,可以證明,算法的時間復雜度可以到達O(n0.5*m)看下面的還不如聽我解釋:(1)從G=(X,Y;E)中取
5、一個初始匹配。(2)若X中的所有頂點都被M匹配,則表明M為一個完美匹配,返回;否則,以所有未匹配頂點為源點進行一次BFS,標記各個點到源點的距離。(3)在滿足disv = disu + 1的邊集中,從X中找到一個未被M匹配的頂點x0,記S = x0,T = 。(4)若N(S) = T,則表明當前已經(jīng)無法得到更大匹配,返回;否則取一y0N(S) - T。(5)若y0已經(jīng)被M匹配則轉(zhuǎn)步驟(6),否則做一條x0-y0的M-增廣路徑P(x0,y0),取M = MP(x0,y0)。(6)由于y已經(jīng)被M匹配,所以M中存在一條邊(y0,z0)去S = S z0,T = Ty0,轉(zhuǎn)步驟(2)-二分圖多重匹配-
6、在二分圖最大匹配中,每個點(不管是X方點還是Y方點)最多只能和一條匹配邊相關(guān)聯(lián),然而,我們經(jīng)常遇到這種問題,即二分圖匹配中一個點可以和多條匹配邊相關(guān)聯(lián),但有上限,或者說,n表示點i最多可以和多少條匹配邊相關(guān)聯(lián)。解決一:利用網(wǎng)絡(luò)流解決二:改進匈牙利算法1.從G=X,Y;E中取一個初始值匹配M。設(shè)置上限下限2.對最大限制n進行二分搜索3.若x都被M匹配,則可行,轉(zhuǎn)至2.否則若與yi匹配的數(shù)量小于n,則匹配xi,yi4.如果yi匹配達到上限,那么在yi中選擇一個元素增廣,如果能讓出位置,匹配xi,yi。轉(zhuǎn)至2.二分圖最佳匹配-二分圖最佳匹配-KuhnMunkras算法:該算法是通過給每個頂點一個標號
7、(叫做頂標)來把求最大權(quán)匹配的問題轉(zhuǎn)化為求完備匹配的問題的。設(shè)頂點Xi的頂標為A i ,頂點Yj的頂標為B j ,頂點Xi與Yj之間的邊權(quán)為wi,j。在算法執(zhí)行過程中的任一時刻,對于任一條邊(i,j),A i +Bj=wi,j始終成立。KM算法的正確性基于以下定理:若由二分圖中所有滿足A i +Bj=wi,j的邊(i,j)構(gòu)成的子圖(稱做相等子圖)有完備匹配,那么這個完備匹配就是二分圖的最大權(quán)匹配。KM算法流程:(1)初始化可行頂標的值;(2)用匈牙利算法尋找完備匹配;(3)若未找到完備匹配則修改可行頂標的值;(4)重復(2)(3)直到找到相等子圖的完備匹配為止;這樣做是O(n4)的定義:圖G
8、中權(quán)值和最大的完全匹配。-二分圖最佳匹配-改進我們給每個Y頂點一個“松弛量”函數(shù)slack,每次開始找增廣路時初始化為無窮大。在尋找增廣路的過程中,檢查邊(i,j)時,如果它不在相等子圖中,則讓slackj變成原值與A i +Bj-wi,j的較小值。這樣,在修改頂標時,取所有不在交錯樹中的Y頂點的slack值中的最小值作為d值即可。但還要注意一點:修改頂標后,要把所有的不在交錯樹中的Y頂點的slack值都減去d。這樣是O(n3)的。-二分圖最佳匹配-KM算法的幾種轉(zhuǎn)化:1.二分圖最佳匹配=最小點權(quán)覆蓋(對偶問題)2.KM算法是求最大權(quán)完備匹配,如果要求最小權(quán)完備匹配怎么辦?方法很簡單,只需將所
9、有的邊權(quán)值取其相反數(shù),求最大權(quán)完備匹配,匹配的值再取相反數(shù)即可。3.KM算法的運行要求是必須存在一個完備匹配,如果求一個最大權(quán)匹配(不一定完備)該如何辦?依然很簡單,把不存在的邊權(quán)值賦為0。4.KM算法求得的最大權(quán)匹配是邊權(quán)值和最大,如果我想要邊權(quán)之積最大,又怎樣轉(zhuǎn)化?還是不難辦到,每條邊權(quán)取自然對數(shù),然后求最大和權(quán)匹配,求得的結(jié)果a再算出ea就是最大積匹配。至于精度問題則沒有更好的辦法了。-二分圖網(wǎng)絡(luò)流解法-具體解決方法略。你們懂得!關(guān)于費用流與KM算法的比較:KM時間復雜度比費用流好,但是實際上差不多,對于稀疏圖來說,許多優(yōu)秀的費用流算法效率也很高,相對而言KM編程復雜度低。二分圖模型的應
10、用-二分圖模型的應用-我們在談最佳匹配的時候已經(jīng)說明了:二分圖最佳匹配=最小點權(quán)覆蓋(證明略),所以現(xiàn)在談一談二分圖的其他變換:1.二分圖最大匹配=最小頂點覆蓋(要求在二分圖下)2.二分圖最大獨立集數(shù)=頂點總數(shù)-最大匹配數(shù)(要求在二分圖下)3.最小路徑覆蓋(有向無環(huán)圖) 在一個的有向圖中,路徑覆蓋就是在圖中找一些路經(jīng),使之覆蓋了圖中的所有頂點,且任何一個頂點有且只有一條路徑與之關(guān)聯(lián);(如果把這些路徑中的每條路徑從它的起始點走到它的終點,那么恰好可以經(jīng)過圖中的每個頂點一次且僅一次);如果不考慮圖中存在回路,那么每條路徑就是一個弱連通子集-二分圖模型的應用-由上面可以得出:.一個單獨的頂點是一條路
11、徑;如果存在一路徑p1,p2,.pk,其中p1 為起點,pk為終點,那么在覆蓋圖中,頂點p1,p2,.pk不再與其它的頂點之間存在有向邊我們這樣理清一個關(guān)系:最小路徑覆蓋數(shù)=G的點數(shù)-最小路徑覆蓋中的邊數(shù)將每一個頂點i拆分成兩個頂點Xi,Yi,然后根據(jù)原圖中邊的信息從X部向Y部引邊,方向由X到Y(jié)。這樣就構(gòu)成了一個二分圖。我們發(fā)現(xiàn),最大匹配數(shù)就是原圖G中最小路徑覆蓋數(shù)邊數(shù)。我們可以得到:最小路徑覆蓋數(shù)=G的頂點數(shù)-二分圖最大匹配穩(wěn)定婚姻問題-穩(wěn)定婚姻問題-你們班上有n位男生和n位女生,每個人對異性都有一個排序,表示對他們的愛戀程度?,F(xiàn)在你的任務是使他們湊成CP,使他們的愛情堅不可摧!滿足一下條件
12、的愛情不是堅不可摧的:男生u和女生v不是CP,但他們愛戀對方的程度都大于愛戀現(xiàn)任的程度。因為這樣男生u和女生v會拋下已經(jīng)是CP的那個她/他,另外組成一對。于是乎多出了兩位前任,這樣就會讓人再也無法相信愛情了!怎么能避免悲劇的發(fā)生呢?-穩(wěn)定婚姻問題-求婚拒絕算法(Gale-Shapley算法/延遲認可算法):先對所有男生進行單身標記,稱其為單身狗男。當存在單身狗男時,進行以下操作:選擇一位單身狗男在所有尚未拒絕她的女生中選擇一位被他排名最優(yōu)先的女神;女神將正在追求她的單身狗男與其現(xiàn)任進行比較,選擇其中排名優(yōu)先的男生作為其男友,即若單身狗男優(yōu)于現(xiàn)任,則現(xiàn)任被拋棄為前任;否則保留其男友,拒絕單身狗男
13、。若某男生被其女友拋棄,則重新變成單身狗男,至重復。-穩(wěn)定婚姻問題-求婚拒絕算法(Gale-Shapley算法/延遲認可算法):函數(shù) 穩(wěn)定婚姻 初始所有 m in M 與 w in W 為 單身 當 存在單身 男子 m w = m所有可考慮的女子中排名最高的 若 w 是 單身 撮合 (m, w) 否則 有些夫婦 (m, w) 存在 若 w 喜歡 m 更于 m (m, w) 為 夫婦 m 為 單身 否則 (m, w) 仍為 夫婦 -穩(wěn)定婚姻問題-這么個過程數(shù)學上可以證明:第一,這個過程會中止,也就是說,總有大家都訂了婚的一天,不可能無限循環(huán)。第二,中止后所有的婚姻是穩(wěn)定婚姻。所謂不穩(wěn)婚姻是說,比如說有兩對夫婦M1,F1和M2,F2,M1的老婆是F1,但他更愛F2;而F2的老公雖說是M2.但她更愛M1,這樣的婚姻就是不穩(wěn)婚姻,M1和F2理應結(jié)合,他們現(xiàn)在各自的婚姻都是錯誤.我們能證明的是,通過上面那個求婚過程,所有的婚姻都是穩(wěn)定的,沒有人犯錯誤。第三,比較引人注目的是,這個過程是male-optimal的,男性能夠獲得盡可能好的伴侶,比如說最后有二十個女人拒絕了他,他仍然能夠得到剩下的八十個女人中他最愛的那一個。第四,更有甚者,這個過程是female-pessimal的,
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024版軟件系統(tǒng)合同
- 2025年度合伙企業(yè)持股合同糾紛調(diào)解與仲裁規(guī)則3篇
- 2024物流金融服務框架協(xié)議
- 2025年度寵物活體產(chǎn)業(yè)鏈上下游資源整合合同3篇
- 2025年中國豪華客車行業(yè)市場調(diào)查研究及投資前景預測報告
- 2025個人虛擬貨幣購買分期還款協(xié)議3篇
- 2025年度個人汽車消費貸款標準合同范本4篇
- 2025年度個人公司代持股解除協(xié)議書4篇
- 2025年湖北工業(yè)建筑集團有限公司招聘筆試參考題庫含答案解析
- 2025年安徽港口集團五河有限公司招聘筆試參考題庫含答案解析
- 基礎(chǔ)設(shè)施零星維修 投標方案(技術(shù)方案)
- 人力資源 -人效評估指導手冊
- 大疆80分鐘在線測評題
- 2024屆廣東省廣州市高三上學期調(diào)研測試英語試題及答案
- 中煤平朔集團有限公司招聘筆試題庫2024
- 2023年成都市青白江區(qū)村(社區(qū))“兩委”后備人才考試真題
- 不付租金解除合同通知書
- 區(qū)域合作伙伴合作協(xié)議書范本
- 中學數(shù)學教學設(shè)計全套教學課件
- 環(huán)衛(wèi)公司年終工作總結(jié)
- 2023年德宏隴川縣人民法院招聘聘用制書記員考試真題及答案
評論
0/150
提交評論