山大《運籌學》課件06圖與網(wǎng)絡分析-8最大對集問題

1、第八節(jié) 最大對集問題二分圖的對集 基本概念 主要定理二分圖的最大基數(shù)對集 基本思想 算法步驟 算法復雜性二分網(wǎng)絡的最大權對集分派問題 規(guī)劃形式 算法步驟基本概念圖G=(N,E)的對集M：M是E的子集，且M中任意兩邊均不相鄰。M-飽和點i：iN，且i同M的一條邊關聯(lián)。M-非飽和點i：iN，且i不同M的任一條邊關聯(lián)。G的完美對集M：G的每一個點都是M-飽和點。G的最大基數(shù)對集M：不存在另外一個對集M,使得|M|M|，其中|M|表示M的基數(shù)?；靖拍頖的一條M-交錯路：邊在對集M和EM中交錯出現(xiàn)的路。G的一條M-增廣路：起點和終點都是M非飽和的一條M-交錯路。圖G=(N,E)的覆蓋K：K是N的子集，

2、且G的每條邊都至少有一個端點在K中。圖G的最小覆蓋K：G不存在另外一個覆蓋K，使得|K|K|。續(xù)主要定理定理6.8.1 圖G中的一個對集M是最大基數(shù)對集當且僅當G不包含M-增廣路。 引理6.8.1 設M是一個對集，K是一個覆蓋，它們滿足|M|=|K|，則M必定是最大基數(shù)對集，而K是最小覆蓋。定理6.8.3 在二分圖中，最大基數(shù)對集的邊數(shù)等于最小覆蓋的點數(shù)。證明最大基數(shù)對集算法的基本思想從圖G的任意一個對集M開始，若M飽和S的所有點，則M是G的最大基數(shù)對集；否則，由S的M-非飽和點出發(fā)，用一個系統(tǒng)方法搜索一條M-增廣路P。若P存在，則通過交換P在M和不在M中的邊，便得到一個其基數(shù)增加1的對集，然

3、后從新的對集開始，繼續(xù)迭代。若P不存在，則現(xiàn)行的對集就是G的最大基數(shù)對集。最大基數(shù)對集算法的步驟第1步(開始) 給定二分圖G=(S,T,E)，令M是一個任意對集，可能是空對集，這時沒有點被標號。第2步(標號) (2.0)在S中，每個非飽和點給以標號“0”。(2.1)如果不存在未檢查的標號點，轉向第4步；否則，找一個具有未檢查的標號點i，如果iS，轉向(2.2)；如果iT，轉向(2.3)(2.2)檢查點i的標號如下：對每個同點i關聯(lián)的邊i,j，除非j已經(jīng)被標號；否則，給點j標號“i”，轉向(2.1)。(2.3)檢查點i的標號如下：如果點i是非飽和點，轉向第3步；否則，辨認同點i關聯(lián)的屬于M的唯一

4、邊i,j，給點j標號“i”，轉向(2.1)。最大基數(shù)對集算法的步驟第3步(增廣)終止在i的一條增廣路被找到，通過反方向追蹤辨認在路上點i的前點，通過把路上不在M中的邊加入M，而把路中在M中的邊從M中除去來增廣M，抹掉所有標號，轉回(2.0)。 續(xù)例最大基數(shù)對集算法的復雜性若令|S|=m，|T|=n，且m0，則轉向第4步。(2.2)找一個未檢查的標號點i，其中或者iS，或者 iT且i=0，如果iS，則轉向(2.3)；如果iT，則轉向(2.4)。最大權對集算法的步驟(2.3)檢查點i的標號如下：對每條邊i,j不屬于M，如果ui+vj-wij0,jT，=min1,2。令L表示所有標號點的集合。對每個iLS，從ui減去；對每個j=0的點