第八節(jié)最大對集問題-資料下載頁
2025-09-19 13:26本頁面
【導讀】意兩邊均不相鄰。M-非飽和點i：i∈N，且i不同M的任一條邊關聯(lián)。G的最大基數(shù)對集M：不存在另外一個對集M’,和的一條M-交錯路。條邊都至少有一個端點在K中。圖G的最小覆蓋K：G不存在另外一個覆蓋K'，僅當G不包含M-增廣路。定理6.8.2設G為具有二分劃(S,T)的一個二分圖，從圖G的任意一個對集M開始，若M飽和S的所有點，出發(fā)，用一個系統(tǒng)方法搜索一條M-增廣路P。到一個其基數(shù)增加1的對集，然后從新的對集開始，找一個具有未檢查的標號點i，如果i∈S，轉向()；步；否則，辨認同點i關聯(lián)的屬于M的唯一邊{i,j}，LSTU，表示所有標號點的集合，則。在路上點i的前點，通過把路上不在M中的邊加入M，令vi=0和πj=+∞，這時沒有點被標號。果ui+vj-wij<πj，給點j標號“i”，并令πj=ui+vj-wij，抹掉所有標號，轉回。第4步設δ1=min{ui|i∈S}，對每個i∈L∩S，從ui減去δ；對每個。權對集，變量ui和vj是最優(yōu)對偶解。
【正文】 標號點 ， 但每個未檢查的標號點 i∈ T有 πi0， 則轉向第 4步 。 ()找一個未檢查的標號點 i， 其中或者 i∈ S， 或者 i∈ T且 πi=0， 如果 i∈ S， 則轉向 ()；如果 i∈ T，則轉向 ()。 最大權對集算法的步驟 ()檢查點 i的標號如下：對每條邊 {i,j}不屬于 M， 如果 ui+vjwijπj， 給點 j標號 “ i”， 并令 πj=ui+vjwij，轉回 ()。 ()檢查點 i的標號如下：如果點 i是非飽和點 ， 轉向第 3步；否則 ， 辨認唯一邊 {i,j}∈ M， 給點 j標號“ i”， 轉向 ()。 續(xù)一 第 3步 (增廣 ) 終止在 i的一條增廣路被找到 ， 通過方向追蹤辨認在路上點 i的前點 ， 通過把路上不在 M中的邊加入 M， 而把路中在 M中的邊從 M中除去來增廣M。 對每個點 j∈ T， 令 πj=+∞。 抹掉所有標號 ， 轉回()。 最大權對集算法的步驟 第 4步 ( 對偶變量的改變 ) 設 δ1=min{ui|i∈ S} ，δ2=min{πj|πj0,j∈ T}， δ=min{δ1,δ2}。 令 L表示所有標號點的集合 。 對每個 i∈ L∩S， 從 ui減去 δ；對每個πj=0的點 j∈ T， 則 vj加上 δ；對每個 πj0的點 j∈ L∩T，則 πj減去 δ。 如果 δδ1， 轉向 ()；否則 ， M是最大權對集 ， 變量 ui和 vj是最優(yōu)對偶解 。 續(xù)二
教學課件相關推薦
鄂ICP備17016276號-1