二部圖匹配網(wǎng)絡(luò)流

1、二部圖&網(wǎng)絡(luò)流,,二部圖,,2024/3/31,3 of 220,二部圖,定義 設(shè) G=為一個無向圖，若能將 V分成 V1和V2(V1?V2=V，V1?V2=?)，使得 G 中的每條邊的兩個端點都是一個屬于V1，另一個屬于V2，則稱 G 為二部圖 ( 或稱二分圖、偶圖等 )，稱V1和V2為互補頂點子集，常將二部圖G記為. 又若G是簡單二部圖，V1中每個頂點均與V2中所有的頂點相鄰，則稱G為完全二部圖，記為 Kr,s

2、，其中r=|V1|，s=|V2|.,2024/3/31,7.3 圖的矩陣表示,4 of 220,例 二部圖,二部圖,完全二部圖,K3,3,2024/3/31,5 of 220,二部圖的判別法,定理 無向圖G=是二部圖當且僅當G中無奇圈.,無向簡單圖的點覆蓋集、點獨立集、匹配,2024/3/31,7 of 220,點獨立集與點獨立數(shù),定義 設(shè)G=，V*?V.(1) (點)獨立集V*——V*中頂點彼此不相鄰(2) V*為極大點獨

3、立集——V*中再加入任何頂點就不是點獨立集(3) 最大點獨立集——元素最多的點獨立集(4) 點獨立數(shù)——最大獨立集中的元素個數(shù)，記為?0,在圖中，點獨立數(shù)依次為2, 2, 3.,(1) (2) (3),2024/3/31,8 of 220,點覆蓋集與點覆蓋數(shù),定義 設(shè)G=, V*?V.(1) V*是點覆蓋集——?e

4、?E，?v?V*，使e與v關(guān)聯(lián)(2) V*是極小點覆蓋集——V*的任何真子集都不是點覆蓋集(3) 最小點覆蓋集——頂點數(shù)最少的點覆蓋集(4) 點覆蓋數(shù)——?0(G)——最小點覆蓋的元素個數(shù),圖中，點覆蓋數(shù)依次為3，4，7.,2024/3/31,9 of 220,點覆蓋集與點獨立集的關(guān)系,?0+?0=n點覆蓋數(shù)+點獨立數(shù)=點數(shù),2024/3/31,10 of 220,匹配(邊獨立集)與匹配數(shù)(邊獨立數(shù)),定義 設(shè)G=, E*?E

5、，(1) 匹配(邊獨立集)E*——E*中各邊均不相鄰(2) 極大匹配E*——E*中不能再加其他邊了(3) 最大匹配——邊數(shù)最多的匹配(4) 匹配數(shù)——最大匹配中的邊數(shù)，記為?1,上圖中各圖的匹配數(shù)依次為3, 3, 4.,2024/3/31,11 of 220,關(guān)于匹配中的其他概念,定義 設(shè)M為G中一個匹配.(1) 匹配邊——(vi,vj)?M(2) v為M飽和點——有M中邊與v關(guān)聯(lián)(3) v為M非飽和點——無M中邊與v關(guān)

6、聯(lián)(4) M的交錯路徑——由匹配邊和非匹配邊交替構(gòu)成的路徑(5) M的增廣路徑——起、終點都是M非飽和點的交錯路徑,2024/3/31,12 of 220,最大匹配判別定理,定理 M為G中最大匹配當且僅當G中不含M的可增廣交錯路徑.,二部圖匹配,匈牙利算法,2024/3/31,14 of 220,增廣路徑,匹配M={{x1,y1}, {x2,y3}, {x3,y4}}有一條增廣路徑?,由M增廣路徑可構(gòu)造比M大的匹配 存在M增廣路徑

7、?M非最大匹配用(M-?)?(? -M)代替M,,,,,,,,,,,2024/3/31,15 of 220,匈牙利算法,由增廣路徑的定義可以推出下述三個結(jié)論：1、?的路徑長度必定為奇數(shù)，第一條邊和最后一條邊都不屬于M。2、?經(jīng)過取對稱差操作可以得到一個更大的匹配M?。3、M為G的最大匹配當且僅當不存在關(guān)于M的增廣路徑。,2024/3/31,16 of 220,匈牙利算法,用增廣路徑求最大匹配(稱作匈牙利算法)算法：(1)置M

8、為空(2)找出一條增廣路? ，通過取對稱差操作獲得更大的匹配M?代替M(3)重復(fù)(2)操作直到找不出增廣路徑為止,2024/3/31,17 of 220,匈牙利算法示例,,圖1 圖2,2024/3/31,18 of 220,二部圖的最小點覆蓋,定理: G是二部圖, 則?0= ?1.即二部圖的最大匹配數(shù)=最小點覆蓋數(shù) 注: 定理對一般圖不成立.,2024/3/31,19

9、of 220,二部圖的最大獨立集,定理：二部圖中:最大獨立集數(shù)＝頂點總數(shù)－最小點覆蓋數(shù) 也＝頂點總數(shù)－最大匹配數(shù),2024/3/31,20 of 220,例題1 Place the Robots,問題描述 有一個N*M(N,M<=50)的棋盤，棋盤的每一格是三種類型之一：空地、草地、墻。機器人只能放在空地上。在同一行或同一列的兩個機器人，若它們之間沒有墻，則它們可以互相攻擊。

10、問給定的棋盤，最多可以放置多少個機器人，使它們不能互相攻擊。,2024/3/31,21 of 220,例題1 Place the Robots（ZOJ）,模型一,于是，問題轉(zhuǎn)化為求圖的最大獨立集問題。,以空地為頂點，有沖突的空地之間連邊，可以得到右邊的這個圖：,2024/3/31,22 of 220,例題1 Place the Robots,模型一,這是NP問題！,2024/3/31,23 of 220,將每一行，每一列被墻隔開且包

11、含空地的連續(xù)區(qū)域稱作“塊”。顯然，在一個塊之中，最多只能放一個機器人。把這些塊編上號。,同樣，把豎直方向的塊也編上號。,例題1 Place the Robots（ZOJ）,模型二,1,2,3,4,5,2024/3/31,24 of 220,例題1 Place the Robots,模型二,1,2,3,4,5,把每個橫向塊看作X部的點，豎向塊看作Y部的點，若兩個塊有公共的空地，則在它們之間連邊。,于是，問題轉(zhuǎn)化成這樣的一個二部圖：,2

12、024/3/31,25 of 220,由于每條邊表示一個空地，有沖突的空地之間必有公共頂點，所以問題轉(zhuǎn)化為二部圖的最大匹配問題。,例題1 Place the Robots,模型二,1,2,3,5,4,2024/3/31,26 of 220,例題2 打獵,獵人要在n*n的格子里打鳥,他可以在某一行中打一槍,這樣此行中的所有鳥都被打掉，也可以在某一列中打,這樣此列中的所有鳥都打掉.問至少打幾槍,才能打光所有的鳥？,建圖：二部圖的X部為每

13、一行，Y部為每一列，如果(i,j)有一只鳥，那么連接X部的i與Y部的j。該二部圖最小點覆蓋數(shù)即是最少要打的槍數(shù)。,2024/3/31,27 of 220,Girls and Boys,The second year of the university somebody started a study on the romantic relations between the students. The relation “roma

14、ntically involved” is defined between one girl and one boy. For the study reasons it is necessaryto find out the maximum set satisfying the condition: there are no two students in the set who have been“romantically i

15、nvolved”. The result of the program is thenumber of students in such a set.The input contains several data sets in text format. Each data set represents one set of subjects of the study,with the following description

16、:the number of studentsthe description of each student, in the following format,2024/3/31,28 of 220,Girls and Boys,student_identifier:(number_of_romantic_relations) student_identifier1 student_identifier2 ...

17、orstudent_identifier:(0)The student_identifier is an integer number between 0and n-1, for n subjects.For each given data set, the program should write to standard output a line containing the result.,2024/3/31,29 o

18、f 220,Girls and Boys,Sample Input 7 0: (3) 4 5 61: (2) 4 6Y: (0)E: (0)4: (2) 0 15: (1) 06: (2) 0 1,Output 5,網(wǎng)絡(luò)流簡介,,2024/3/31,31 of 220,,2024/3/31,32 of 220,,,2024/3/31,33 of 220,,,s,,a,,d,,,,,b,,c,,t,,,,,,,,16,1

19、1,13,8,10,,4,1,12,12,20,15,7,7,9,4,14,11,4,4,2024/3/31,34 of 220,剩余圖 增廣之后的新流,,s,,a,,d,,,,,b,,c,,t,,,,,,,,16,13,10,4,12,20,7,9,14,4,2024/3/31,35 of 220,剩余圖 增廣之后的新流,2024/3/31,36 of 220,剩余圖

20、 增廣之后的新流,2024/3/31,37 of 220,,,2024/3/31,38 of 220,,2024/3/31,39 of 220,剩余圖,解決方法：,(1) EK算法:在剩余圖中找最短增廣路徑,(2) 最大容量增廣算法:,找最大瓶頸容量,2024/3/31,40 of 220,練習(xí)1: 無向圖的網(wǎng)絡(luò)流,下圖為某地區(qū)運輸網(wǎng). 邊上的數(shù)字表示運輸能力（單位：萬噸/小時），則從頂點1到頂點5的最

21、大運輸能力可以達到_____萬噸/小時.,2024/3/31,41 of 220,練習(xí)2,《算法導(dǎo)論》 P400 26.1-9,2024/3/31,42 of 220,阿P與阿Q都是四驅(qū)車好手，他們各有N輛四驅(qū)車。為了一比高下，他們約好進行一場比賽。這次比賽共有M個分站賽，贏得分站賽場次多的獲得總冠軍。每個分站賽中，兩人各選一輛自己的賽車比賽。分站賽的勝負大部分取決于兩車的性能，但由于種種原因（如相互之間的干擾），性能并不是決定勝負的

22、唯一指標，有時會出現(xiàn)A贏B、B贏C、C贏D、D又贏A的局面。幸好有一種高智能機器，只要給定兩輛四驅(qū)車，就能立刻判斷誰會贏，在總比賽前它就已經(jīng)把阿p的每輛車與阿q的每輛車都兩兩測試過了，并且還把輸贏表輸入了電腦。,2024/3/31,43 of 220,另外，由于比賽的磨損，每輛四驅(qū)車都有自己的壽命（即它們能參加分站賽的場次），不同的四驅(qū)車壽命可能不同，但最多不會超過50場。兩輛四驅(qū)車最多只能交手一次。 現(xiàn)給定N、M（1<=N

23、<=100，1<=M<=1000）、N*N的一個輸贏表、每輛四驅(qū)車的壽命，并假設(shè)每次分站賽兩人都有可選的賽車，請你計算一下阿P最多能夠贏得多少個分站賽。,2024/3/31,44 of 220,1、建立N個點代表阿P的N輛車，分別以1到N標號； 2、建立N個點代表阿Q的N輛車，分別以N+1到2N標號； 3、如果阿P的第I輛車能夠跑贏阿Q的第J輛車，則加一條弧I?N+J，容量為1，表示兩輛四驅(qū)車最