二分圖(匈牙利,km算法詳解)-全文預(yù)覽
【正文】 意選一門或多門課 ,問是否達(dá)成 : （如果一個(gè)學(xué)生選修的那門課，那么他就可以代表這門課） PKU1469 輸入為 : P N(課程數(shù)跟學(xué)生數(shù) ) 接著有 P行 ,格式為 Count studenti studenti+1 ……studentcount (Count表示對課程 1感興趣的學(xué)生數(shù) ,接著有 Count個(gè)學(xué)生 ) 如第一行 2 1 2表示學(xué)生 1跟學(xué)生 2對課程 1感興趣 輸出為 : 若每門課都能找到一位代表則輸出 ”YES”,否則為 ”NO” PKU1469 假如有三個(gè)學(xué)生跟三門課程 ,學(xué)生 1,2,區(qū)分 ,假設(shè) 3個(gè)課程為 4,5,6 左邊節(jié)點(diǎn)是學(xué)生 ,右邊節(jié)點(diǎn)是課程 ,下圖表示 ,學(xué)生 1對課程 4,5感興趣 ,學(xué)生 2對課程 5,6感興趣 ,學(xué)生 3對課程 6感興趣 1 2 3 4 5 6 于是問題就變?yōu)樵诙謭D中尋找最大匹配 ,只要這個(gè)最大匹配大于或等于課程數(shù) P,那么就達(dá)到要求了 . 尋找最大匹配的匈牙利算法流程 首先我們先看節(jié)點(diǎn) 1,尋找下一條邊 ,假設(shè)找到節(jié)點(diǎn)5,因?yàn)?1跟 5都還沒匹配 ,所以找到一個(gè)匹配 .標(biāo)記,xM[1]=5,yM[5]=1。 如右圖所示：藍(lán)色部分 就構(gòu)成一個(gè)最大匹配， 同時(shí)它也是一個(gè)完美匹 配 完美匹配： 如果所有點(diǎn)都在匹配邊上，稱這個(gè)最大 匹配是完美匹配。二分圖匹配 Bipartite graph 二分圖的定義： 二分圖是這樣的一個(gè)圖，它的頂點(diǎn)可以分為兩個(gè)集合 X和 Y。 二分圖的最大匹配 ? 定義： 圖中包含邊數(shù)最多的匹配稱為圖的最大匹配。 二分圖的最大匹配 ? 匈牙利算法： ? 尋找增廣路： ? 初始時(shí)最大匹配為空 for 二分圖左半邊的每個(gè)點(diǎn) i do 從點(diǎn) i出發(fā)尋找增廣路徑 ? 如果找到，則把它取反 ? （即增加了總了匹配數(shù)）。已經(jīng)匹配了 . 此時(shí)我們就轉(zhuǎn)到節(jié)點(diǎn) 6的匹配點(diǎn) 2上去 ,發(fā)現(xiàn)節(jié)點(diǎn) 2的另一條邊 25中節(jié)點(diǎn) 5也已經(jīng)匹配了 ,yM[5]=1?？梢宰C明：最少的點(diǎn)（即覆蓋數(shù)）＝最大匹配數(shù)
電大資料相關(guān)推薦
鄂ICP備17016276號-1