二分圖匹配算法及其應(yīng)用【畢業(yè)論文+開(kāi)題報(bào)告+文獻(xiàn)綜述】

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

1、本科畢業(yè)論文開(kāi)題報(bào)告數(shù)學(xué)與應(yīng)用數(shù)學(xué)二分圖匹配算法及其應(yīng)用一、綜述本課題國(guó)內(nèi)外研究動(dòng)態(tài),說(shuō)明選題的依據(jù)和意義圖的匹配理論簡(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算法是求最大權(quán)匹配的經(jīng)典算法,它是在匈牙利算法的進(jìn)一步提高,它是解決數(shù)學(xué)中一類(lèi)存在性問(wèn)題的基本工具,廣泛應(yīng)用于社會(huì)、經(jīng)濟(jì)、科技、自然等各個(gè)領(lǐng)域中.本文主要研究KM算法的具體原理,步驟,以及它一些實(shí)際問(wèn)題中的應(yīng)用.圖的匹配問(wèn)題起源于1935年霍爾

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

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

4、條邊都沒(méi)有公共端點(diǎn).的所有匹配中邊數(shù)最多的匹配稱(chēng)為最大匹配,其邊數(shù)稱(chēng)為匹配數(shù).如果()中任一頂點(diǎn)均為匹配中邊的端點(diǎn),那么稱(chēng)為()—完全匹配.若既是—完全匹配又是—完全匹配,則稱(chēng)為的完全匹配.定義7設(shè)二分圖,其中==匹配數(shù),中每條邊有權(quán),若能找到一個(gè)匹配(=匹配數(shù)),滿足所有匹配的邊權(quán)和最大(或最小),則稱(chēng)為的一個(gè)最大(或最小)權(quán)匹配.定義8稱(chēng)圖中頂點(diǎn)到是可達(dá)的,如果,或者有一條到的路徑.如果16的任何兩個(gè)頂點(diǎn)都是互相可達(dá)的,稱(chēng)無(wú)向圖是連通的.如果是的子圖,是連通的,并且不存在的真子圖,使是連通的,且以為真子圖,則圖稱(chēng)為圖的連通分支.定理1(霍爾定理)設(shè)圖.有—完全匹配的充分必要條件是:對(duì)每一,

5、其中為的鄰域,即,則有.定理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)成的子圖(稱(chēng)做相等子圖)有完全匹配,那么這個(gè)完全匹配就是二分圖的最大權(quán)匹配.劉桂真[1]對(duì)二分圖最大權(quán)匹配開(kāi)討論,介紹了二分圖最大權(quán)匹配并將匹配問(wèn)題從“婚姻問(wèn)題”推廣到工作分派問(wèn)題.耿素云[2]通過(guò)對(duì)二分圖的匹配及帶權(quán)圖的應(yīng)用進(jìn)行了討論也將其運(yùn)用到實(shí)際中,并以此解決了最短路徑問(wèn)題、關(guān)鍵路徑問(wèn)題以及中國(guó)郵遞員問(wèn)題.楊勝超、張瑞軍[3]將在介紹畢業(yè)論文選題系統(tǒng)的系統(tǒng)

6、用例、功能模塊、和流程圖的基礎(chǔ)上,針對(duì)學(xué)生選題不均衡這一突出問(wèn)題,引出了二分圖最大權(quán)匹配的經(jīng)典算法—KM算法,該算法能夠根據(jù)學(xué)生的題目預(yù)選、自命題、未定題等多種情況,完成題目與學(xué)生的智能匹配,使最終題目的整體滿意度最高,從而提高學(xué)生畢業(yè)論文選題質(zhì)量.該系統(tǒng)在武漢科技大學(xué)管理學(xué)院04級(jí)畢業(yè)論文選題中實(shí)施.謝政、程浩光[4]利用賦雙權(quán)的二分圖中求關(guān)于第一個(gè)權(quán)最大的限制下、第二個(gè)權(quán)最小的完美匹配的網(wǎng)絡(luò)模型，給出了這一模型的有效性，并用此算法解決了企業(yè)的優(yōu)化組合分工中的挖潛問(wèn)題.彭宇新,NgoChong-Wah,肖建國(guó)[5]利用嘗試將二分圖的最大權(quán)匹配用于鏡頭檢索.把兩個(gè)鏡頭的相似度度量建模為一個(gè)帶權(quán)

7、的二分圖:鏡頭中的每一幀看成二分圖的一個(gè)結(jié)點(diǎn),兩個(gè)鏡頭之間任意幀的相似值作為邊的權(quán)值.在一一對(duì)應(yīng)的前提下,利用最大權(quán)匹配的KM算法求出該二分圖的最大權(quán),以此作為兩個(gè)鏡頭的相似度.考慮到檢索的速度的問(wèn)題,提出了兩個(gè)改進(jìn)算法.對(duì)于二分圖最大權(quán)匹配的算法有不少,如:頂點(diǎn)標(biāo)記法等.但KM16算法是求解二分圖最大權(quán)匹配的經(jīng)典算法.本文主要研究用KM算法解決二分圖最大權(quán)匹配的步驟過(guò)程及二分圖最大權(quán)匹配算法的一