資源描述：
《二分圖匹配算法及其應(yīng)用【畢業(yè)論文】》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
1、本科畢業(yè)論文（20屆）二分圖匹配算法及其應(yīng)用專業(yè)：數(shù)學(xué)與應(yīng)用數(shù)學(xué)16摘要圖的匹配理論簡(jiǎn)單的說就是使得圖中每?jī)蓚€(gè)點(diǎn)之間都有聯(lián)系.匹配理論是圖論中的一個(gè)重要內(nèi)容,它在運(yùn)籌學(xué)、系統(tǒng)工程中都有著廣泛的應(yīng)用,近幾十年來,隨著組合數(shù)學(xué)的迅速發(fā)展,匹配理論成為許多重要理論的基礎(chǔ)和源泉.二分圖的最大匹配算法是匹配理論研究的熱點(diǎn)之一.KM算法是求最大權(quán)匹配的經(jīng)典算法,它是在匈牙利算法的進(jìn)一步提高,它是解決數(shù)學(xué)中一類存在性問題的基本工具,廣泛應(yīng)用于社會(huì)、經(jīng)濟(jì)、科技、自然等各個(gè)領(lǐng)域中.本文主要研究KM算法的具體原理,步驟,以及它一些實(shí)際問題中的應(yīng)用.關(guān)鍵詞:二分圖;匹配;KM算法;應(yīng)用;工作分派16Binary
2、ChartMatchingAlgorithmsandItsApplicationAbstractChartmatchingtheorysimplymeansthatitmakeseverytwopointsingraphhaverelations.Matchingtheoryisanimportantcontentofgraph,ithasbeenwidelyusedinbothoperationsresearch,systemengineering,inrecentdecades,withtherapiddevelopmentofcombinatorialmathematics,matc
3、hingtheoryhasbecomethefoundationandsourceofmanyimportanttheories.Thebiggestmatchingalgorithmofbinarychartisthehotspotofmatchingtheory.KMalgorithmisaclassicalalgorithmsofobtainingmaximummatching,itisfurtherimprovementofHungaryalgorithm,itisabasictooltosolveakindofexistenceproblemsinmathematics,wide
4、lyusedareasofsociety,economic,technology,nature,etc.Thisarticlemainlystudiesthespecificprinciple,modificationsoftheKMalgorithm,andalsostudiestheapplicationsofsomeactualproblems.Keywords:Binarychart;Matching;KMalgorithms;Application;Referral16目錄摘要IAbstractII1前言12二分圖最大權(quán)匹配的KM算法32.1相關(guān)定義及其定理32.2KM算法的步驟
5、63KM算法的應(yīng)用93.1KM算法在工作分派中的應(yīng)用93.2KM算法在鏡頭檢索中的應(yīng)用134小結(jié)16參考文獻(xiàn)17致謝18161前言現(xiàn)實(shí)世界中,許多問題的數(shù)學(xué)抽象形式可以用圖來描述,如互聯(lián)網(wǎng)、通訊網(wǎng)、集成電路、分子結(jié)構(gòu)等.為了方便對(duì)這些問題的探索,通過幾百年來我們對(duì)圖的研究,從而形成了一個(gè)專門的數(shù)學(xué)學(xué)科:圖論.圖的匹配理論簡(jiǎn)單的說就是使得圖中每?jī)蓚€(gè)點(diǎn)之間都有聯(lián)系.圖的匹配理論是圖論中的一個(gè)重要的內(nèi)容.近幾年來,隨著組合數(shù)學(xué)的迅速發(fā)展,匹配理論成為許多重要的理論的基礎(chǔ)和源泉.二分圖的最大權(quán)匹配問題已成為匹配理論研究的熱點(diǎn)問題之一,引起了廣大學(xué)者的研究和關(guān)注,并應(yīng)用到實(shí)際中.KM算法是解決這類問
6、題的經(jīng)典算法,二分圖最大權(quán)匹配的KM算法看似簡(jiǎn)單,但二分圖最大權(quán)匹配在數(shù)學(xué)的許多領(lǐng)域中都有著廣泛的應(yīng)用,同時(shí)它的局限性也很明顯.用KM算法解決二分圖最大權(quán)匹配問題使它的許多重要性質(zhì)仍然得以保留,成為二分圖最大權(quán)匹配新的研究方向.圖的匹配問題起源于1935年霍爾的“婚姻問題”.當(dāng)時(shí)他成功地解決了下面問題:有個(gè)小伙子和個(gè)姑娘,每個(gè)小伙子認(rèn)識(shí)個(gè)姑娘中的某些人,問在什么條件下每個(gè)小伙子能夠找到一個(gè)他認(rèn)識(shí)的姑娘結(jié)婚?該問題抽象為圖論問題為用個(gè)頂點(diǎn)代表個(gè)小伙子,用個(gè)頂點(diǎn)代表個(gè)姑娘.當(dāng)且僅當(dāng)小伙子認(rèn)識(shí)姑娘時(shí)在和之間連一條邊.上面問題則抽象為在什么條件下這個(gè)圖中存在條邊分別以為端點(diǎn),使這些邊中任意兩條邊都
7、沒有公共端點(diǎn)?很顯然對(duì)于“婚姻問題”有解的一個(gè)必要條件是任意個(gè)小伙子認(rèn)識(shí)的姑娘總數(shù)至少為個(gè).霍爾證明了這個(gè)條件也是充分的.這就構(gòu)成了一個(gè)關(guān)于二分圖的匹配問題.而在上面問題中加上一個(gè)條件,就是每位小伙子對(duì)各個(gè)姑娘的喜歡程度又各不相同,并將每位小伙子對(duì)各個(gè)姑娘的喜歡程度賦予為每條邊的權(quán)值,這就將求二分圖的完全匹配問題轉(zhuǎn)化為求二分圖的最大權(quán)匹配問題.而KM算法是Kuhn和Munkras分別于1955年和1957年獨(dú)立提出來的,
