山大《運(yùn)籌學(xué)》課件06圖與網(wǎng)絡(luò)分析-8最大對(duì)集問(wèn)題

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

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

3、后從新的對(duì)集開始，繼續(xù)迭代。若P不存在，則現(xiàn)行的對(duì)集就是G的最大基數(shù)對(duì)集。最大基數(shù)對(duì)集算法的步驟第1步(開始) 給定二分圖G=(S,T,E)，令M是一個(gè)任意對(duì)集，可能是空對(duì)集，這時(shí)沒(méi)有點(diǎn)被標(biāo)號(hào)。第2步(標(biāo)號(hào)) (2.0)在S中，每個(gè)非飽和點(diǎn)給以標(biāo)號(hào)“0”。(2.1)如果不存在未檢查的標(biāo)號(hào)點(diǎn)，轉(zhuǎn)向第4步；否則，找一個(gè)具有未檢查的標(biāo)號(hào)點(diǎn)i，如果iS，轉(zhuǎn)向(2.2)；如果iT，轉(zhuǎn)向(2.3)(2.2)檢查點(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)向(2.1)。(2.3)檢查點(diǎn)i的標(biāo)號(hào)如下：如果點(diǎn)i是非飽和點(diǎn)，轉(zhuǎn)向第3步；否則，辨認(rèn)同點(diǎn)i關(guān)聯(lián)的屬于M的唯一

4、邊i,j，給點(diǎn)j標(biāo)號(hào)“i”，轉(zhuǎn)向(2.1)。最大基數(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)回(2.0)。 續(xù)例最大基數(shù)對(duì)集算法的復(fù)雜性若令|S|=m，|T|=n，且m0，則轉(zhuǎn)向第4步。(2.2)找一個(gè)未檢查的標(biāo)號(hào)點(diǎn)i，其中或者iS，或者 iT且i=0，如果iS，則轉(zhuǎn)向(2.3)；如果iT，則轉(zhuǎn)向(2.4)。最大權(quán)對(duì)集算法的步驟(2.3)檢查點(diǎn)i的標(biāo)號(hào)如下：對(duì)每條邊i,j不屬于M，如果ui+vj-wij0,jT，=min1,2。令L表示所有標(biāo)號(hào)點(diǎn)的集合。對(duì)每個(gè)iLS，從ui減去；對(duì)每個(gè)j=0的點(diǎn)