二分圖最大匹配.ppt

二分圖匹配 匈牙利算法和KM算法簡介 二分圖的概念 二分圖又稱作二部圖 是圖論中的一種特殊模型 設(shè)G V R 是一個(gè)無向圖 如頂點(diǎn)集V可分割為兩個(gè)互不相交的子集 并且圖中每條邊依附的兩個(gè)頂點(diǎn)都分屬兩個(gè)不同的子集 則稱圖G為二分圖 最大匹配 給定一個(gè)二分圖G 在G的一個(gè)子圖M中 M的邊集 E 中的任意兩條邊都不依附于同一個(gè)頂點(diǎn) 則稱M是一個(gè)匹配 選擇這樣的邊數(shù)最大的子集稱為圖的最大匹配問題 maximalmatchingproblem 如果一個(gè)匹配中 圖中的每個(gè)頂點(diǎn)都和圖中某條邊相關(guān)聯(lián) 則稱此匹配為完全匹配 也稱作完備匹配 匈牙利算法 求最大匹配的一種顯而易見的算法是 先找出全部匹配 然后保留匹配數(shù)最多的 但是這個(gè)算法的復(fù)雜度為邊數(shù)的指數(shù)級(jí)函數(shù) 因此 需要尋求一種更加高效的算法 增廣路的定義 也稱增廣軌或交錯(cuò)軌 若P是圖G中一條連通兩個(gè)未匹配頂點(diǎn)的路徑 并且屬M(fèi)的邊和不屬M(fèi)的邊 即已匹配和待匹配的邊 在P上交替出現(xiàn) 則稱P為相對(duì)于M的一條增廣路徑 匈牙利算法 由增廣路的定義可以推出下述三個(gè)結(jié)論 1 P的路徑長度必定為奇數(shù) 第一條邊和最后一條邊都不屬于M 2 P經(jīng)過取反操作可以得到一個(gè)更大的匹配M 3 M為G的最大匹配當(dāng)且僅當(dāng)不存在相對(duì)于M的增廣路徑 匈牙利算法 用增廣路求最大匹配 稱作匈牙利算法 匈牙利數(shù)學(xué)家Edmonds于1965年提出 算法輪廓 1 置M為空 2 找出一條增廣路徑P 通過取反操作獲得更大的匹配M 代替M 3 重復(fù) 2 操作直到找不出增廣路徑為止 匈牙利算法 程序清單 Functionfind k integer integer varst sf i j t integer queue father array 1 100 ofinteger beginqueue 1 k st 1 sf 1 fillchar father sizeof father 0 repeat 匈牙利算法 fori 1tondoif father i 0 and a queue st i 1 thenbeginifmatch2 i 0thenbegininc sf queue sf match2 i father i queue st endelse 匈牙利算法 beginj queue st whiletruedobegint match1 j match1 j i match2 i j ift 0thenbreak i t j father t 匈牙利算法 end find 1 exit end end inc st untilst sf find 0 end 匈牙利算法 在主程序中調(diào)用下面的程序即可得出最大匹配數(shù) Bmatch 0 ForI 1tondoBmatch Bmatch find i Writeln Bmatch 一個(gè)關(guān)于二分圖的性質(zhì) 最大匹配數(shù) 最大獨(dú)立集 X Y 最佳匹配 如果邊上帶權(quán)的話 找出權(quán)和最大的匹配叫做求最佳匹配 實(shí)際模型 某公司有職員x1 x2 xn 他們?nèi)プ龉ぷ鱵1 y2 yn 每個(gè)職員做各項(xiàng)工作的效益未必一致 需要制定一個(gè)分工方案 使得人盡其才 讓公司獲得的總效益最大 數(shù)學(xué)模型 G是加權(quán)完全二分圖 求總權(quán)值最大的完備匹配 KM算法 窮舉的效率 n 我們需要更加優(yōu)秀的算法 定理 設(shè)M是一個(gè)帶權(quán)完全二分圖G的一個(gè)完備匹配 給每個(gè)頂點(diǎn)一個(gè)可行頂標(biāo) 第i個(gè)x頂點(diǎn)的可行標(biāo)用lx i 表示 第j個(gè)y頂點(diǎn)的可行標(biāo)用ly j 表示 如果對(duì)所有的邊 i j inG 都有l(wèi)x i ly j w i j 成立 w i j 表示邊的權(quán) 且對(duì)所有的邊 i j inM 都有l(wèi)x i ly j w i j 成立 則M是圖G的一個(gè)最佳匹配 證明很容易 KM算法 對(duì)于任意的G和M 可行頂標(biāo)都是存在的 l x maxw x y l y 0欲求完全二分圖的最佳匹配 只要用匈牙利算法求其相等子圖的完備匹配 問題是當(dāng)標(biāo)號(hào)之后的Gl無完備匹配時(shí)怎么辦 1957年 居然比匈牙利算法早 Kuhn和Munkras給出了一個(gè)解決該問題的有效算法 用逐次修改可行頂標(biāo)l v 的辦法使對(duì)應(yīng)的相等子圖之最大匹配逐次增廣 最后出現(xiàn)完備匹配 KM算法 修改方法如下 先將一個(gè)未被匹配的頂點(diǎn)u uin x 做一次增廣路 記下哪些結(jié)點(diǎn)被訪問那些結(jié)點(diǎn)沒有被訪問 求出d min lx i ly j w i j 其中i結(jié)點(diǎn)被訪問 j結(jié)點(diǎn)沒有被訪問 然后調(diào)整lx和ly 對(duì)于訪問過的x頂點(diǎn) 將它的可行標(biāo)減去d 對(duì)于所有訪問過的y頂點(diǎn) 將它的可行標(biāo)增加d 修改后的頂標(biāo)仍是可行頂標(biāo) 原來的匹配M仍然存在 相等子圖中至少出現(xiàn)了一條不屬于M的邊 所以造成M的逐漸增廣 KM算法 上述算法的證明也很容易Kuhn Munkras算法流程 1 初始化可行頂標(biāo)的值 2 用匈牙利算法尋找完備匹配 3 若未找到完備匹配則修改可行頂標(biāo)的值 4 重復(fù) 2 3 直到找到相等子圖的完備匹配為止 參考文獻(xiàn) 王樹禾 離散數(shù)學(xué)引論 吳文虎王建德 圖論算法與程序設(shè)計(jì) 劉汝佳黃亮 算法藝術(shù)與信息學(xué)競(jìng)賽 2002年冬令營論文 孫方成 偶圖的算法及應(yīng)用 2004年冬令營論文 黃源河 淺談圖論模型的建立與應(yīng)用 例題1PlacetheRobots ZOJ1654 問題描述有一個(gè)N M N M 50 的棋盤 棋盤的每一格是三種類型之一 空地 草地 墻 機(jī)器人只能放在空地上 在同一行或同一列的兩個(gè)機(jī)器人 若它們之間沒有墻 則它們可以互相攻擊 問給定的棋盤 最多可以放置多少個(gè)機(jī)器人 使它們不能互相攻擊 例題1PlacetheRobots ZOJ 模型一 于是 問題轉(zhuǎn)化為求圖的最大獨(dú)立集問題 在問題的原型中 草地 墻這些信息不是我們所關(guān)心的 我們關(guān)心的只是空地和空地之間的聯(lián)系 因此 我們很自然想到了下面這種簡單的模型 以空地為頂點(diǎn) 有沖突的空地間連邊 我們可以得到右邊的這個(gè)圖 例題1PlacetheRobots ZOJ 模型一 在問題的原型中 草地 墻這些信息不是我們所關(guān)心的 我們關(guān)心的只是空地和空地之間的聯(lián)系 因此 我們很自然想到了下面這種簡單的模型 以空地為頂點(diǎn) 有沖突的空地間連邊 我們可以得到右邊的這個(gè)圖 這是NP問題 我們將每一行 每一列被墻隔開 且包含空地的連續(xù)區(qū)域稱作 塊 顯然 在一個(gè)塊之中 最多只能放一個(gè)機(jī)器人 我們把這些塊編上號(hào) 同樣 把豎直方向的塊也編上號(hào) 例題1PlacetheRobots ZOJ 模型二 1 2 3 4 5 例題1PlacetheRobots ZOJ 模型二 1 2 3 4 5 把每個(gè)橫向塊看作X部的點(diǎn) 豎向塊看作Y部的點(diǎn) 若兩個(gè)塊有公共的空地 則在它們之間連邊 于是 問題轉(zhuǎn)化成這樣的一個(gè)二部圖 由于每條邊表示一個(gè)空地 有沖突的空地之間必有公共頂點(diǎn) 所以問題轉(zhuǎn)化為二部圖的最大匹配問題 例題1PlacetheRobots ZOJ 模型二 1 2 3 5 4 比較前面的兩個(gè)模型 模型一過于簡單 沒有給問題的求解帶來任何便利 模型二則充分抓住了問題的內(nèi)在聯(lián)系 巧妙地建立了二部圖模型 為什么會(huì)產(chǎn)生這種截然不同的結(jié)果呢 其一是由于對(duì)問題分析的角度不同 模型一以空地為點(diǎn) 模型二以空地為邊 其二是由于對(duì)原型中要素的選取有差異 模型一對(duì)要素的選取不充分 模型二則保留了原型中 棋盤 這個(gè)重要的性質(zhì) 由此可見 對(duì)要素的選取 是圖論建模中至關(guān)重要的一步 例題1PlacetheRobots ZOJ 小結(jié) 例題2救護(hù)傷員 TOJ1148 無情的海嘯奪取了無數(shù)人的生命 很多的醫(yī)療隊(duì)被派往災(zāi)區(qū)拯救傷員 就在此時(shí) 醫(yī)療隊(duì)突然發(fā)現(xiàn)自己帶的藥品已經(jīng)不夠用了 只剩下了N種 1 n 20 隨著病人病情的發(fā)展 每種藥在每天能獲得的效果是不一樣的 同時(shí) 每天病人只能服用一種藥 也就是說 這些藥還夠支持N天 現(xiàn)在 給出你每種藥在每天使用的效果 請(qǐng)你判斷當(dāng)每種藥都用完后所有藥達(dá)到的效果之和最大可以是多少 例題3打獵 獵人要在n n的格子里打鳥 他可以在某一行中打一槍 這樣此行中的所有鳥都被打掉 也可以在某一列中打 這樣此列中的所有鳥都打掉 問至少打幾槍 才能打光所有的鳥 建圖 二分圖的X部為每一行 Y部為每一列 如果 i j 有一只鳥 那么連接X部的i與Y部的j 該二分圖的最大匹配數(shù)則是最少要打的槍數(shù) 例題4最小路徑覆蓋 一個(gè)不含圈的有向圖G中 G的一個(gè)路徑覆蓋是一個(gè)其結(jié)點(diǎn)不相交的路徑集合P 圖中的每一個(gè)結(jié)點(diǎn)僅包含于P中的某一條路徑 路徑可以從任意結(jié)點(diǎn)開始和結(jié)束 且長度也為任意值 包括0 請(qǐng)你求任意一個(gè)不含圈的有向圖G的最小路徑覆蓋數(shù) 理清一個(gè)關(guān)系 最小路徑覆蓋數(shù) G的定點(diǎn)數(shù) 最小路徑覆蓋中的邊