最大對集PPT學習教案

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

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

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

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

5、個數(shù)表示容量。用，第二個數(shù)表示容量。 1,2 3,4 1,2 3,1 1,2 第5頁/共28頁 第7頁 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頁/共28頁 第8頁 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頁/共28頁 第

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

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

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

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

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

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

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

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

14、最大基數(shù)對集，若初始解如下圖的最大基數(shù)對集，若初始解如下圖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頁/共28頁 第17頁 1 2 3 4 5 6 7 A 9 8 3 1 3 3 3 標號標號 1 2 3 4 5 6 7 A 9 8 3 3 3 5 17 8 1 0 標號標號 1 2 3 4 5 6 7 A 9 8 增廣增廣 路路 1 2 3 4 5 6 7 A 9 8 增廣增廣 路路 第16頁/共28頁 第18頁 1 2 3 4 5 6 7 A 9 8 1 2 5 7 1 0 8 標號標號 1 2 3 4 5 6 7 A 9

15、 8 增廣路增廣路 第17頁/共28頁 第19頁 若令若令mS |，nT |，且，且nm 。 在找到一個匈牙利樹或找到一條增廣路之前，在找到一個匈牙利樹或找到一條增廣路之前， 標標號程序最多進行號程序最多進行)(mnO次；次； 在求出所需的對集之前，初始對集最多能增廣在求出所需的對集之前，初始對集最多能增廣 m 次；次； 所以，總的計算量為所以，總的計算量為)( 2n mO。 第18頁/共28頁 第20頁 設二分網(wǎng)絡是完全的設二分網(wǎng)絡是完全的),(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頁/共28頁 第21頁 ,.,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頁/共28頁 第22頁 第第 1 步步 (開開始始)給給定定二二分分網(wǎng)網(wǎng)絡絡 G=(S,T,E,W)，令令 M，max ij ww ，對對每每個個Si ，令令wui ， 對對每每個個Tj ，令令0 i

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

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

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