最大對(duì)集PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1 最大對(duì)集最大對(duì)集 第2頁(yè) 基本假設(shè)基本假設(shè)： 給定有向網(wǎng)絡(luò)給定有向網(wǎng)絡(luò)),(WCANG ，其中，其中 ij c表示弧表示弧Aji ),(的容量，的容量， ij w 表示單位流通過(guò)弧表示單位流通過(guò)弧Aji ),(的費(fèi)用。的費(fèi)用。則流則流)( ij xx 的費(fèi)用為的費(fèi)用為 ji ijijx w , 問題問題： 求一個(gè)可行流求一個(gè)可行流)( * ij xx ，使其流值為得，使其流值為得v，并且費(fèi)用達(dá)到最小。，并且費(fèi)用達(dá)到最小。 第1頁(yè)/共28頁(yè) 第3頁(yè) ),( ,0 , , , 0)( )( )( . t . s min ),( Ajicx tsiNixx vxx vxx xw ijij

2、j jiij j jttj j jssj Aji ijij 第2頁(yè)/共28頁(yè) 第4頁(yè) ,)( ),( , 0 ),( ,)()( . t . s )()( max ),( Niip Ajir Ajiwripjp rcvspvtp ij ijij Aji ijij 無(wú)無(wú)限限制制 第3頁(yè)/共28頁(yè) 第5頁(yè) 第第 1 步步 (開開始始) 讓讓所所有有的的流流0 ij x是是，所所有有點(diǎn)點(diǎn)對(duì)對(duì)應(yīng)應(yīng)的的數(shù)數(shù)0)( ip。 第第 2 步步 (決決定定哪哪些些弧弧可可以以改改變變流流量量) 用用 I 表表示示這這樣樣的的弧弧集集合合使使 ij wipjp )()(，同同時(shí)時(shí) ijij cx 用用 R 表表示

3、示這這樣樣的的弧弧集集合合使使 ij wipjp )()(，同同時(shí)時(shí)0 ij x 用用 Q 表表示示不不在在RI 中中的的弧弧集集合合。 第第 3 步步 (改改變變流流量量) 用用最最大大流流算算法法，在在RI 上上找找增增廣廣路路，增增加加流流量量。如如果果從從s 到到t 的的流流量量已已經(jīng)經(jīng)是是 v，那那么么計(jì)計(jì)算算停停止止，已已經(jīng)經(jīng)得得到到一一個(gè)個(gè)流流量量是是 v 的的最最小小費(fèi)費(fèi)用用流流。 如如果果從從s 到到t 不不能能再再增增加加流流量量，檢檢查查在在RIQ中中是是否否能能找找到到增增 廣廣路路。如如果果不不能能找找到到增增廣廣路路，那那么么該該網(wǎng)網(wǎng)絡(luò)絡(luò)的的最最大大流流達(dá)達(dá)不不到到

4、 v；如如果果在在 RIQ中中能能找找到到增增廣廣路路，就就轉(zhuǎn)轉(zhuǎn)入入第第 4 步步。 第第 4 步步 (改改變變頂頂點(diǎn)點(diǎn)的的)(ip值值) 把把所所有有點(diǎn)點(diǎn)分分成成兩兩類類：S 是是標(biāo)標(biāo)上上號(hào)號(hào)的的點(diǎn)點(diǎn)的的集集合合，T 是是標(biāo)標(biāo)不不上上號(hào)號(hào)的的點(diǎn)點(diǎn)的的集集合合， 讓讓 S 中中的的點(diǎn)點(diǎn))(ip值值不不變變，T 的的點(diǎn)點(diǎn))(ip值值全全部部加加 1，再再轉(zhuǎn)轉(zhuǎn)回回第第 2 步步。 第4頁(yè)/共28頁(yè) 第6頁(yè) 求解下圖所示網(wǎng)絡(luò)中自點(diǎn)求解下圖所示網(wǎng)絡(luò)中自點(diǎn) 1 到點(diǎn)到點(diǎn) 4 其值為其值為 3 的最的最 小費(fèi)用流。其中每條弧上的第一個(gè)數(shù)表示單位流的費(fèi)小費(fèi)用流。其中每條弧上的第一個(gè)數(shù)表示單位流的費(fèi) 用，第二

5、個(gè)數(shù)表示容量。用，第二個(gè)數(shù)表示容量。 1,2 3,4 1,2 3,1 1,2 第5頁(yè)/共28頁(yè) 第7頁(yè) st a b st a b st a b 1，2，0 3,4,0 1,2,0 3,1,0 1,2,0 st a b ),( st a b (+s,2) ),( (+a,2) st a b (+s,2) ),( 第6頁(yè)/共28頁(yè) 第8頁(yè) st a b st a b ),( st a b(+s,2) st a b (+a,2 ) (+b,2 ) st a b ),( (-b,1) (+s,1) st a b 1,2, 2 3,4,0 1,2, 2 3,1, 0 1,2, 2 第7頁(yè)/共28頁(yè) 第

6、9頁(yè) st a b st a b ),( st a b (-b,1) (+s,1) (+a,1 ) 第8頁(yè)/共28頁(yè) 第10頁(yè) 設(shè)設(shè)網(wǎng)網(wǎng)絡(luò)絡(luò)的的點(diǎn)點(diǎn)數(shù)數(shù)為為 n，弧弧數(shù)數(shù)為為 m，弧弧的的最最大大容容量量為為 w。 算算法法的的循循環(huán)環(huán)次次數(shù)數(shù)取取決決于于點(diǎn)點(diǎn)的的 p(i)值值修修正正的的次次數(shù)數(shù)最最多多進(jìn)進(jìn)行行 mw 次次， 因因此此第第 2 步步的的計(jì)計(jì)算算量量為為)( 2w mO。 如如果果最最大大流流值值為為 v，則則留留增增廣廣最最多多進(jìn)進(jìn)行行 v 次次， 所所以以第第 3 步步的的計(jì)計(jì)算算量量為為)(mvO。 第第 4 步步的的計(jì)計(jì)算算量量為為)(nmvO 所所以以，總總的的計(jì)計(jì)算

7、算量量為為)( 2 mvwmO 。 第9頁(yè)/共28頁(yè) 第11頁(yè) 第10頁(yè)/共28頁(yè) 第12頁(yè) 圖圖 G=(N,E)的對(duì)集的對(duì)集 M：M 是是 E 的子集，且的子集，且 M 中任意兩邊均不相鄰。中任意兩邊均不相鄰。 M - 飽和點(diǎn)飽和點(diǎn) i：Ni ，且，且 i 同同 M 的一條邊關(guān)聯(lián)。的一條邊關(guān)聯(lián)。 M - 非飽和點(diǎn)非飽和點(diǎn) i：Ni ，且，且 i 不同不同 M 的任一條邊關(guān)聯(lián)。的任一條邊關(guān)聯(lián)。 G 的完美對(duì)集的完美對(duì)集 M：G 的每一個(gè)點(diǎn)都是的每一個(gè)點(diǎn)都是 M - 飽和點(diǎn)。飽和點(diǎn)。 G 的最大基數(shù)對(duì)集的最大基數(shù)對(duì)集 M：不存在另外一個(gè)對(duì)集另外一個(gè)對(duì)集：不存在另外一個(gè)對(duì)集另外一個(gè)對(duì)集 M，使得，

8、使得|MM ， 其中其中| M表示表示 M 的基數(shù)。的基數(shù)。 G 的一條的一條 M -交錯(cuò)路交錯(cuò)路：邊在對(duì)集：邊在對(duì)集 M 和和ME 中交錯(cuò)出現(xiàn)的路。中交錯(cuò)出現(xiàn)的路。 G 的一條的一條 M - 增廣路增廣路：起點(diǎn)和終點(diǎn)都是：起點(diǎn)和終點(diǎn)都是 M 非飽和的一條非飽和的一條 M - 交錯(cuò)路。交錯(cuò)路。 圖圖 G=(N,E)的覆蓋的覆蓋 K：K 是是 N 的子集，且的子集，且 G 的每條邊都至少有一個(gè)端點(diǎn)在的每條邊都至少有一個(gè)端點(diǎn)在 K 中。中。 圖圖 G 的最小覆蓋的最小覆蓋 K：G 不存在另外一個(gè)覆蓋不存在另外一個(gè)覆蓋 K，使得，使得 |KK 。 第11頁(yè)/共28頁(yè) 第13頁(yè) 定理定理 6.8.1

9、圖圖 G 中中的一個(gè)對(duì)集的一個(gè)對(duì)集 M 是最大基數(shù)對(duì)集當(dāng)且僅當(dāng)是最大基數(shù)對(duì)集當(dāng)且僅當(dāng) G 不包含不包含 M - 增廣路。增廣路。 定理定理 6.8.2 設(shè)設(shè) G 為具有二分劃為具有二分劃(S,T)的一個(gè)二分圖，則的一個(gè)二分圖，則 G 含有飽和含有飽和 S 的每個(gè)點(diǎn)的的每個(gè)點(diǎn)的對(duì)對(duì) 集當(dāng)且僅當(dāng)集當(dāng)且僅當(dāng)對(duì)任意的對(duì)任意的SX ，有，有| )(|XX 。 引理引理 6.8.1 設(shè)設(shè) M 是一個(gè)對(duì)集，是一個(gè)對(duì)集，K 是一個(gè)覆蓋，它們滿足是一個(gè)覆蓋，它們滿足|KM ，則，則 M 必定是必定是 最最大基數(shù)對(duì)集，而大基數(shù)對(duì)集，而 K 是最小覆蓋。是最小覆蓋。 定理定理 6.8.3 在二分圖中，最大基數(shù)對(duì)集的

10、邊數(shù)等于最小覆蓋的點(diǎn)數(shù)。在二分圖中，最大基數(shù)對(duì)集的邊數(shù)等于最小覆蓋的點(diǎn)數(shù)。 第12頁(yè)/共28頁(yè) 第14頁(yè) 從從圖圖 G 的任意一個(gè)對(duì)集的任意一個(gè)對(duì)集 M 開始，若開始，若 M 飽和飽和 S 的所有點(diǎn)，則的所有點(diǎn)，則M是是 G 的最大基數(shù)對(duì)集；否則，由的最大基數(shù)對(duì)集；否則，由 S 的的 M - 非飽和點(diǎn)出發(fā)，用一個(gè)系統(tǒng)方非飽和點(diǎn)出發(fā)，用一個(gè)系統(tǒng)方 法法搜索一條搜索一條 M - 增廣路增廣路 P。若若 P 存在，則通過(guò)交換存在，則通過(guò)交換 P 在在 M 和不在和不在 M 中的邊，便得到一個(gè)其基數(shù)增加中的邊，便得到一個(gè)其基數(shù)增加 1 的對(duì)集，然后從新的對(duì)集開始，繼的對(duì)集，然后從新的對(duì)集開始，繼 續(xù)迭

11、代。續(xù)迭代。若若 P 不存在，則現(xiàn)行的對(duì)集就是不存在，則現(xiàn)行的對(duì)集就是 G 的最大基數(shù)對(duì)集。的最大基數(shù)對(duì)集。 第13頁(yè)/共28頁(yè) 第15頁(yè) 第第 1 步步 (開開始始)給給定定二二分分圖圖 G=(S,T,E)，令令 M 是是一一個(gè)個(gè)任任意意對(duì)對(duì)集集，可可能能是是空空對(duì)對(duì)集集，這這時(shí)時(shí)沒沒有有點(diǎn)點(diǎn)被被標(biāo)標(biāo)號(hào)號(hào)。 第第 2 步步 (標(biāo)標(biāo)號(hào)號(hào)) (2.0) 在在 S 中中，每每個(gè)個(gè)非非飽飽和和點(diǎn)點(diǎn)給給以以標(biāo)標(biāo)號(hào)號(hào)“0”。 (2.1) 如如果果不不存存在在未未檢檢查查的的標(biāo)標(biāo)號(hào)號(hào)點(diǎn)點(diǎn)，轉(zhuǎn)轉(zhuǎn)向向第第 4 步步；否否則則，找找一一個(gè)個(gè)具具有有未未檢檢查查的的標(biāo)標(biāo)號(hào)號(hào)點(diǎn)點(diǎn) i，如如果果Si ， 轉(zhuǎn)轉(zhuǎn)向向（2

12、.2） ；如如果果Ti ，轉(zhuǎn)轉(zhuǎn)向向（2.3） (2.2) 檢檢查查點(diǎn)點(diǎn) i 的的標(biāo)標(biāo)號(hào)號(hào)如如下下：對(duì)對(duì)每每個(gè)個(gè)同同點(diǎn)點(diǎn) i 關(guān)關(guān)聯(lián)聯(lián)的的邊邊i , j，除除非非 j 已已經(jīng)經(jīng)被被標(biāo)標(biāo)號(hào)號(hào)；否否則則，給給點(diǎn)點(diǎn) j 標(biāo)標(biāo)號(hào)號(hào)“i”， 轉(zhuǎn)轉(zhuǎn)向向(2.1)。 (2.3) 檢檢查查點(diǎn)點(diǎn) i 的的標(biāo)標(biāo)號(hào)號(hào)如如下下：如如果果點(diǎn)點(diǎn) i 是是非非飽飽和和點(diǎn)點(diǎn)，轉(zhuǎn)轉(zhuǎn)向向第第 3 步步；否否則則，辨辨認(rèn)認(rèn)同同點(diǎn)點(diǎn) i 關(guān)關(guān)聯(lián)聯(lián)的的屬屬于于 M 的的 唯唯一一邊邊i , j，給給點(diǎn)點(diǎn) j 標(biāo)標(biāo)號(hào)號(hào)“i”，轉(zhuǎn)轉(zhuǎn)向向(2.1)。 第第 3 步步 (增增廣廣) 終終止止在在 i 的的一一條條增增廣廣路路被被找找到到，通通過(guò)

13、過(guò)方方向向追追蹤蹤辨辨認(rèn)認(rèn)在在路路上上點(diǎn)點(diǎn) i 的的前前點(diǎn)點(diǎn)，通通過(guò)過(guò)把把路路上上不不在在 M 中中的的邊邊加加入入 M，而而把把路路中中在在 M 中中的的邊邊從從 M 中中除除去去來(lái)來(lái)增增廣廣 M，抹抹掉掉所所有有標(biāo)標(biāo)號(hào)號(hào)，轉(zhuǎn)轉(zhuǎn)回回(2.0)。 第第 4 步步 (匈匈牙牙利利標(biāo)標(biāo)號(hào)號(hào)) 標(biāo)標(biāo)號(hào)號(hào)是是匈匈牙牙利利的的，這這時(shí)時(shí)沒沒有有增增廣廣路路存存在在，M 是是最最大大基基數(shù)數(shù)對(duì)對(duì)集集。令令TSL ，表表示示所所有有標(biāo)標(biāo)號(hào)號(hào)點(diǎn)點(diǎn)的的集集 合合，則則)()(LTLSK 是是對(duì)對(duì)偶偶于于 M 的的最最小小覆覆蓋蓋。 第14頁(yè)/共28頁(yè) 第16頁(yè) 求下圖求下圖a a所示的二分圖所示的二分圖G G的

14、最大基數(shù)對(duì)集，若初始解如下圖的最大基數(shù)對(duì)集，若初始解如下圖b b所示所示 1 2 3 4 5 6 7 A 9 8 a 1 2 3 4 5 6 7 A 9 8 b 第15頁(yè)/共28頁(yè) 第17頁(yè) 1 2 3 4 5 6 7 A 9 8 3 1 3 3 3 標(biāo)號(hào)標(biāo)號(hào) 1 2 3 4 5 6 7 A 9 8 3 3 3 5 17 8 1 0 標(biāo)號(hào)標(biāo)號(hào) 1 2 3 4 5 6 7 A 9 8 增廣增廣 路路 1 2 3 4 5 6 7 A 9 8 增廣增廣 路路 第16頁(yè)/共28頁(yè) 第18頁(yè) 1 2 3 4 5 6 7 A 9 8 1 2 5 7 1 0 8 標(biāo)號(hào)標(biāo)號(hào) 1 2 3 4 5 6 7 A 9

15、 8 增廣路增廣路 第17頁(yè)/共28頁(yè) 第19頁(yè) 若令若令mS |，nT |，且，且nm 。 在找到一個(gè)匈牙利樹或找到一條增廣路之前，在找到一個(gè)匈牙利樹或找到一條增廣路之前， 標(biāo)標(biāo)號(hào)程序最多進(jìn)行號(hào)程序最多進(jìn)行)(mnO次；次； 在求出所需的對(duì)集之前，初始對(duì)集最多能增廣在求出所需的對(duì)集之前，初始對(duì)集最多能增廣 m 次；次； 所以，總的計(jì)算量為所以，總的計(jì)算量為)( 2n mO。 第18頁(yè)/共28頁(yè) 第20頁(yè) 設(shè)二分網(wǎng)絡(luò)是完全的設(shè)二分網(wǎng)絡(luò)是完全的),(WTSTSG ， mS |，nT |，且且nm ),.,2 , 1;,.,2 , 1( , 0 ),.,2 , 1( , 1 ),.,2 , 1(

16、, 1 . t . s max , njmix njx mix xw ij i ij j ij ji ijij 其中其中 Mji Mji xij , , 0 , , 1 第19頁(yè)/共28頁(yè) 第21頁(yè) ,.,2 , 1 , 0 ,.,2 , 1 , 0 ,.,2 , 1;,.,2 , 1 , . t . s )( min njv miu njmiwvu vu j i ijji j j i i 第20頁(yè)/共28頁(yè) 第22頁(yè) 第第 1 步步 (開開始始)給給定定二二分分網(wǎng)網(wǎng)絡(luò)絡(luò) G=(S,T,E,W)，令令 M，max ij ww ，對(duì)對(duì)每每個(gè)個(gè)Si ，令令wui ， 對(duì)對(duì)每每個(gè)個(gè)Tj ，令令0 i

17、 v和和 j ，這這時(shí)時(shí)沒沒有有點(diǎn)點(diǎn)被被標(biāo)標(biāo)號(hào)號(hào)。 第第 2 步步 (標(biāo)標(biāo)號(hào)號(hào))(2.0) 給給 S 中中每每個(gè)個(gè)非非飽飽和和點(diǎn)點(diǎn)標(biāo)標(biāo)號(hào)號(hào)“ ”。 (2.1) 如如果果不不存存在在未未檢檢查查的的標(biāo)標(biāo)號(hào)號(hào)點(diǎn)點(diǎn)或或者者存存在在未未檢檢查查的的標(biāo)標(biāo)號(hào)號(hào)點(diǎn)點(diǎn)，但但每每個(gè)個(gè)未未檢檢查查的的標(biāo)標(biāo)號(hào)號(hào)點(diǎn)點(diǎn)Ti 有有0 i ，則則 轉(zhuǎn)轉(zhuǎn)向向第第 4 步步。 (2.2) 找找一一個(gè)個(gè)未未檢檢查查的的標(biāo)標(biāo)號(hào)號(hào)點(diǎn)點(diǎn) i，其其中中或或者者Si ，或或者者Ti 且且0 i ，如如果果Si ，則則轉(zhuǎn)轉(zhuǎn)向向(2.3)；如如果果 Ti ，則則轉(zhuǎn)轉(zhuǎn)向向(2.4)。 (2.3) 檢檢查查點(diǎn)點(diǎn) i 的的標(biāo)標(biāo)號(hào)號(hào)如如下下：對(duì)對(duì)每每

18、條條邊邊Mji ,，如如果果 jijji wvu ，給給點(diǎn)點(diǎn) j 標(biāo)標(biāo)號(hào)號(hào)“i”，并并令令 ijjij wvu ，轉(zhuǎn)轉(zhuǎn)回回(2.1)。 (2.4) 檢檢查查點(diǎn)點(diǎn) i 的的標(biāo)標(biāo)號(hào)號(hào)如如下下：如如果果點(diǎn)點(diǎn) i 是是非非飽飽和和點(diǎn)點(diǎn)，轉(zhuǎn)轉(zhuǎn)向向第第 3 步步；否否則則，辨辨認(rèn)認(rèn)唯唯一一邊邊Mji ,，給給點(diǎn)點(diǎn) j 標(biāo)標(biāo)號(hào)號(hào) “i”，轉(zhuǎn)轉(zhuǎn)向向(2.1)。 第第 3 步步 (增增廣廣)終終止止在在 i 的的一一條條增增廣廣路路被被找找到到，通通過(guò)過(guò)方方向向追追蹤蹤辨辨認(rèn)認(rèn)在在路路上上點(diǎn)點(diǎn) i 的的前前點(diǎn)點(diǎn)，通通過(guò)過(guò)把把路路上上不不在在 M 中中的的邊邊 加加入入 M，而而把把路路中中在在 M 中中的的邊邊

19、從從 M 中中除除去去來(lái)來(lái)增增廣廣 M。對(duì)對(duì)每每個(gè)個(gè)點(diǎn)點(diǎn)Tj ，令令 j 。抹抹掉掉所所有有標(biāo)標(biāo)號(hào)號(hào)，轉(zhuǎn)轉(zhuǎn)回回 (2.0)。 第21頁(yè)/共28頁(yè) 第23頁(yè) 第第 4 步步 (對(duì)對(duì)偶偶變變量量的的改改變變)設(shè)設(shè)|min 1 Siui ，, 0|min 2 Tj jj ，,min 21 令令TSL 表表示示所所有有標(biāo)標(biāo)號(hào)號(hào)點(diǎn)點(diǎn)的的集集合合。對(duì)對(duì)每每個(gè)個(gè)SLi ，從從 i u減減去去 ；對(duì)對(duì)每每個(gè)個(gè)0 j 的的點(diǎn)點(diǎn)Tj ， 則則 j v加 加上上 ；對(duì)對(duì)每每個(gè)個(gè)0 j 的的點(diǎn)點(diǎn)TLj ，則則 j 減減去去 。如如果果 1 ，轉(zhuǎn)轉(zhuǎn)向向(2.1)；否否則則，M 是是最最大大權(quán)權(quán)對(duì)對(duì)集集，變變量量 i u和和 j v是是最最優(yōu)優(yōu)對(duì)對(duì)偶偶解解。 第22頁(yè)/共28頁(yè) 第24頁(yè) 1 2 3 4 5 6 7 8 1 2 3 2 2 1 3 2 4 2 3 求如圖所示的二分網(wǎng)絡(luò)中的最大權(quán)對(duì)集求如圖所示的二分網(wǎng)絡(luò)中的最大權(quán)對(duì)集 第23頁(yè)/共28頁(yè)