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

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

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

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

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

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

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

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

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

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