二分圖匹配算法及其應(yīng)用【文獻(xiàn)綜述】

《二分圖匹配算法及其應(yīng)用【文獻(xiàn)綜述】》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、畢業(yè)設(shè)計(jì)文獻(xiàn)綜述數(shù)學(xué)與應(yīng)用數(shù)學(xué)二分圖匹配算法及其應(yīng)用圖的匹配理論簡(jiǎn)單的說(shuō)就是使得圖中每?jī)蓚€(gè)點(diǎn)之間都有聯(lián)系.匹配理論是圖論中的一個(gè)重要內(nèi)容,它在運(yùn)籌學(xué)、系統(tǒng)工程中都有著廣泛的應(yīng)用,近幾十年來(lái),隨著組合數(shù)學(xué)的迅速發(fā)展,匹配理論成為許多重要理論的基礎(chǔ)和源泉.二分圖的最大匹配算法是匹配理論研究的熱點(diǎn)之一.KM算法是求最大匹配的經(jīng)典算法,它是在匈牙利算法的進(jìn)一步提高,它是解決數(shù)學(xué)中一類存在性問(wèn)題的基本工具,廣泛應(yīng)用于社會(huì)、經(jīng)濟(jì)、科技、自然等各個(gè)領(lǐng)域中.本文主要研究KM算法的具體原理,步驟,以及它一些實(shí)際問(wèn)題中的應(yīng)用.圖的匹配問(wèn)題起

2、源于1935年霍爾的“婚姻問(wèn)題”.KM算法是Kuhn和Munkras分別于1955年和1957年獨(dú)立提出來(lái)的,他們?cè)谘芯繄D論中最大權(quán)匹配問(wèn)題時(shí)很巧妙運(yùn)用KM算法去解決問(wèn)題.定義1圖有三部分所組成(1)非空集合,稱為的結(jié)點(diǎn)集,其成員稱為結(jié)點(diǎn)或頂點(diǎn).(2)集合,稱為的邊集,其成員稱為邊.(3)函數(shù),稱為邊和頂點(diǎn)的關(guān)聯(lián)映射.這里稱為的偶對(duì)集,其成員偶對(duì)形如,,為結(jié)點(diǎn),它們未必不同.當(dāng)時(shí),稱邊關(guān)聯(lián)端點(diǎn),.當(dāng)用作序偶時(shí),稱為有向邊,以為起點(diǎn),以為終點(diǎn),圖稱為有向圖;當(dāng)用作無(wú)序偶對(duì)時(shí),,稱為無(wú)向邊(或邊),圖稱為無(wú)向圖(或圖).定義

3、2無(wú)向圖稱為二分圖,如果有非空集合,使,,且對(duì)每一,,,.此時(shí)常用表示二分圖.若對(duì)中任一及中的任一恰有一邊,使,則稱為完全二分圖.當(dāng),時(shí),完全二分圖記為.定義3圖的頂點(diǎn)到頂點(diǎn)的擬路徑是指如下頂點(diǎn)與邊的序列:其中為的頂點(diǎn),為的邊,且以及為端點(diǎn)(對(duì)有向圖,以為起點(diǎn),以為終點(diǎn)).當(dāng)各不相同時(shí),該擬路徑稱為路徑.定義4若是二分圖的一個(gè)匹配.設(shè)從圖中的一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)存在一條路徑,這條路是由屬于的邊和不屬于的邊交替出現(xiàn)組成的,則稱這條路為增廣路(或稱交互樹(shù)或交錯(cuò)樹(shù)).如果增廣路的首尾兩個(gè)頂點(diǎn)不屬于,則稱這條路為可增廣路.定義5

4、設(shè)為二分圖,當(dāng)給賦予映射或,為任意集合、常用實(shí)數(shù)集及其子集,此時(shí)為賦權(quán)圖,常用或或表示之.稱為結(jié)點(diǎn)的權(quán),稱為的權(quán).定義6設(shè)為二分圖,.稱為的一個(gè)匹配,如果中任何兩條邊都沒(méi)有公共端點(diǎn).的所有匹配中邊數(shù)最多的匹配稱為最大匹配,其邊數(shù)稱為匹配數(shù).如果()中任一頂點(diǎn)均為匹配中邊的端點(diǎn),那么稱為()—完全匹配.若既是—完全匹配又是—完全匹配,則稱為的完全匹配.定義7設(shè)二分圖,其中==匹配數(shù),中每條邊有權(quán),若能找到一個(gè)匹配(=匹配數(shù)),滿足所有匹配的邊權(quán)和最大(或最小),則稱為的一個(gè)最大(或最小)權(quán)匹配.定義8稱圖中頂點(diǎn)到是可達(dá)的,

5、如果,或者有一條到的路徑.如果的任何兩個(gè)頂點(diǎn)都是互相可達(dá)的,稱無(wú)向圖是連通的.如果是的子圖,是連通的,并且不存在的真子圖,使是連通的,且以為真子圖,則圖稱為圖的連通分支.定理1(霍爾定理)設(shè)圖.有—完全匹配的充分必要條件是:對(duì)每一,其中為的鄰域,即,則有.定理2(Tutte定理)一個(gè)圖有完全匹配當(dāng)且僅當(dāng)對(duì)圖的任意頂點(diǎn)子集有圖的奇分支數(shù)不大于中的頂點(diǎn)數(shù),其中表示從圖中刪去頂點(diǎn)集及其關(guān)聯(lián)的邊所得的圖,圖的奇分支是指奇數(shù)個(gè)頂點(diǎn)的連通分支.定理3若由二分圖中所有滿足的邊構(gòu)成的子圖(稱做相等子圖)有完全匹配,那么這個(gè)完全匹配就是二

6、分圖的最大權(quán)匹配.Kuhn－Munkras算法(即KM算法)流程(1)初始化可行頂標(biāo)的值;(2)用匈牙利算法尋找完備匹配;(3)若未找到完全匹配則修改可行頂標(biāo)的值;(4)重復(fù)(2)(3)直到找到相等子圖的完全匹配為止.KM算法是通過(guò)給每個(gè)頂點(diǎn)一個(gè)標(biāo)號(hào)(我們有時(shí)稱之為頂標(biāo))來(lái)把求最大權(quán)匹配的問(wèn)題轉(zhuǎn)化為不斷地尋找增廣路以使二分圖的匹配數(shù)達(dá)到最大的完全匹配的問(wèn)題.我們令二分圖中部的節(jié)點(diǎn)的頂標(biāo)為.部的節(jié)點(diǎn)的頂標(biāo)為.部與部節(jié)點(diǎn)之間的權(quán)值為.要求在算法執(zhí)行過(guò)程中的任一時(shí)刻，對(duì)于任一條邊,使得始終成立.在初始時(shí),令為所有與頂點(diǎn)關(guān)聯(lián)的邊

7、的權(quán)值的最大值,令.如果當(dāng)前的相等子圖沒(méi)有完全匹配,就需要修改頂標(biāo)以使擴(kuò)大相等子圖,直到相等子圖具有完全匹配為止(這樣就可以求出最大權(quán)匹配).如果當(dāng)前相等子圖找不到完全匹配,那么是因?yàn)閷?duì)于某個(gè)頂點(diǎn),我們找不到一條從它出發(fā)的增廣路.這時(shí)為了獲得了一條增廣路,現(xiàn)在我們把增廣路中的頂點(diǎn)的頂標(biāo)全都減小某個(gè)值,的頂點(diǎn)的頂標(biāo)全都增加,就可以使得至少有一條新邊進(jìn)入相等子圖.那么我們會(huì)發(fā)現(xiàn):(1)兩端都在增廣路中的邊,的值沒(méi)有變化.也就是說(shuō),它原來(lái)屬于相等子圖,現(xiàn)在仍屬于相等子圖.(2)兩端都不在增廣路中的邊,和都沒(méi)有變化.也就是說(shuō),它

8、原來(lái)屬于(或不屬于)相等子圖,現(xiàn)在仍屬于(或不屬于)相等子圖.(3)端不在增廣路中,端在增廣路中的邊,它的的值有所增大.它原來(lái)不屬于相等子圖,現(xiàn)在仍不屬于相等子圖.(4)端在增廣路中,端不在增廣路中的邊,它的的值有所減小.也就說(shuō),它原來(lái)不屬于相等子圖,現(xiàn)在可能進(jìn)入了相等子圖,因而使相等子圖得到了擴(kuò)大.現(xiàn)在的問(wèn)題就是求