第八節(jié)最大對(duì)集問(wèn)題-文庫(kù)吧資料
2024-10-06 13:26本頁(yè)面
【正文】 ??? ?????? ijiji j i jiju + vu + v w , i = 1 , 2 , .. ., m 。 最大基數(shù)對(duì)集算法的步驟 第 3步 (增廣 ) 終止在 i的一條增廣路被找到 ， 通過(guò)反方向追蹤辨認(rèn)在路上點(diǎn) i的前點(diǎn) ， 通過(guò)把路上不在 M中的邊加入 M，而把路中在 M中的邊從 M中除去來(lái)增廣 M， 抹掉所有標(biāo)號(hào) ， 轉(zhuǎn)回 ()。 第 4 步 ( 匈牙利標(biāo)號(hào) ) 標(biāo)號(hào)是匈牙利的，這時(shí)沒(méi)有增廣路存在， M 是最大基數(shù)對(duì)集。 ()如果不存在未檢查的標(biāo)號(hào)點(diǎn) ， 轉(zhuǎn)向第 4步；否則 ，找一個(gè)具有未檢查的標(biāo)號(hào)點(diǎn) i， 如果 i∈ S， 轉(zhuǎn)向 ()；如果 i∈ T， 轉(zhuǎn)向 () ()檢查點(diǎn) i的標(biāo)號(hào)如下：對(duì)每個(gè)同點(diǎn) i關(guān)聯(lián)的邊 {i,j}， 除非 j已經(jīng)被標(biāo)號(hào)；否則 ， 給點(diǎn) j標(biāo)號(hào) “ i”， 轉(zhuǎn)向 ()。 最大基數(shù)對(duì)集算法的步驟 第 1步 (開(kāi)始 ) 給定二分圖 G=(S,T,E)， 令 M是一個(gè)任意對(duì)集 ， 可能是空對(duì)集 ， 這時(shí)沒(méi)有點(diǎn)被標(biāo)號(hào) 。 若 P存在 ， 則通過(guò)交換 P在 M和不在 M中的邊 ， 便得到一個(gè)其基數(shù)增加 1的對(duì)集 ， 然后從新的對(duì)集開(kāi)始 ，繼續(xù)迭代 。 定理 6 . 8 . 2 設(shè) G 為具有二分劃 ( S , T ) 的一個(gè)二分圖，則 G 含有飽和 S 的每個(gè)點(diǎn)的對(duì)集當(dāng)且僅當(dāng)對(duì)任意的?XS ，有 |Γ ( X ) | ≥ | X | 。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1