二分圖匹配算法及其應(yīng)用【畢業(yè)論文+開題報告+文獻綜述】

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

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

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

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

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

5、其中為的鄰域,即,則有.定理2(Tutte定理)一個圖有完全匹配當且僅當對圖的任意頂點子集有圖的奇分支數(shù)不大于中的頂點數(shù),其中表示從圖中刪去頂點集及其關(guān)聯(lián)的邊所得的圖,圖的奇分支是指奇數(shù)個頂點的連通分支.定理3若由二分圖中所有滿足的邊構(gòu)成的子圖(稱做相等子圖)有完全匹配,那么這個完全匹配就是二分圖的最大權(quán)匹配.劉桂真[1]對二分圖最大權(quán)匹配開討論,介紹了二分圖最大權(quán)匹配并將匹配問題從“婚姻問題”推廣到工作分派問題.耿素云[2]通過對二分圖的匹配及帶權(quán)圖的應(yīng)用進行了討論也將其運用到實際中,并以此解決了最短路徑問題、關(guān)鍵路徑問題以及中國郵遞員問題.楊勝超、張瑞軍[3]將在介紹畢業(yè)論文選題系統(tǒng)的系統(tǒng)

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

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