二分圖匹配及其應用

1、二分圖匹配及其應用1x5x4x3x2x1y2y3y4y5y例題1 棋盤的覆蓋n一張普通的國際象棋棋盤n8*8 = 64 格中被刪除了一些格子n使用1*2 的多米諾骨牌進行覆蓋n求最大覆蓋的格數(shù)和方案 例題1 思路n染色n建圖n性質n最大匹配和完美匹配基本概念n點集分為互補的兩個集合1x5x4x3x2x1y2y3y4y5y基本定理n判定定理：判定定理：n一個圖為二分圖的充要條件是其所有回路均一個圖為二分圖的充要條件是其所有回路均為偶數(shù)長。為偶數(shù)長。q如何判斷一張圖是否為二分圖，并對節(jié)點進如何判斷一張圖是否為二分圖，并對節(jié)點進行正確的劃分呢？行正確的劃分呢？二分圖的判斷問題n染色法n將節(jié)點用黑白兩

2、種顏色染n實現(xiàn)：深度優(yōu)先搜索二分圖判斷問題解答1nvarn visited: array1.100 of integer;n data: array1.1001.100 of integer;n n: integer;n success: boolean;二分圖判斷問題解答2procedure dfs(which, color:integer);var i: integer;begin if not success then exit; if visitedwhich 0 then begin if visitedwhich color then success = false; exit;

3、end; visitedwhich := color; for i:=1 to n do if datawhichi 0 then dfs(i, 3-color);end;二分圖判斷問題解答3function judge:boolean;var i: integer;begin success := true; for i:=1 to n do if visitedi = 0 then dfs(i,1); judge := success;end.HALL 定理n二分圖，存在完美匹配的充分必要條件是，對于任意一個頂點集合的子集A，它的相鄰點構成的鄰集X(A)，都滿足以下條件：AAX)(HALL

4、 定理 證明n必要性n充分性例題2 HALL定理的應用n構造N*N的矩陣，使得每行都有1到n每個數(shù)字出現(xiàn)一次且僅一次，每列都有1到n每個數(shù)字出現(xiàn)一次且僅一次例題2 思路n每次構造一行n循環(huán)n次構造n行n建圖n如何證明？例題3 思考題nN為奇數(shù)，M=(N-1)/2，由組合數(shù)學知:n因為M+M+1 = N1mnmnCC例題3 思考題現(xiàn)將所有的從n個數(shù)里取m個數(shù)的組合構成一個集合A將所有的從n個數(shù)里取m+1個數(shù)的組合構成另一個集合B這兩個集合是否存在著一一映射的關系？使得A中的每個元素a都對應到B中的元素b，且a為b的一個子集？例題3 思考題解答n建圖n找完美匹配n如何證明？增廣路和匈牙利算法n增廣

5、路（交錯軌）的概念n匈牙利算法：找增廣路n如何找？算法選擇？增廣路和匈牙利算法 實例11x5x4x3x2x1y2y3y4y5y增廣路和匈牙利算法 實例21x5x4x3x2x1y2y3y4y5y找增廣路的兩種辦法n廣度優(yōu)先搜索n深度優(yōu)先搜索廣度優(yōu)先算法程序nvarndata: array1.100,1.100 of integer;nmatch1,match2: array1.100 of integer;nn：integer;廣度優(yōu)先算法程序nfunction bmatch:integer;nvarn i,r:integer;nbeginn for i:=1 to n don r := r +

6、 find(i);n bmatch := r;nend;廣度優(yōu)先算法程序nfunction find(s:integer):integer;nvarn i,j, d,t, qh,ql:integer;n father2,queue1:array1.100 of integer;nbeginn fillchar(father2,sizeof(father2),0);n queue11 := s;n qh := 1;n ql := 1;廣度優(yōu)先算法程序while (qh 0) or (dataqueue1qhi=0) then continue; if (match2i0) then begin

7、inc(ql); queue1ql:=match2i; father2i:=queue1qh;廣度優(yōu)先算法程序 end else begin j := queueqh; while (true) do begin t:=match1j; match1j:=i; match2i:=j; if (t = 0) then break; i:=t; j:=father2t;廣度優(yōu)先算法程序 end; find := 1; Exit; end; end; end; find := 0;end;深度優(yōu)先算法程序vardata: array1.100,1.100 of integer;match1,matc

8、h2: array1.100 of integer;int n;used2: array1.100 of integer;深度優(yōu)先算法程序function bmatch:integer;var i,r:integer;begin for i:=1 to n do begin fillchar(used2,sizeof(used2),0); r := r + find(i); end; bmatch := r;end;深度優(yōu)先算法程序function find(s:integer):integer;var i:integer;begin for i:=1 to n do if (datasi 0

9、) and (used2i=0) then begin used2i := 1; if (match2i = 0) or find(match2i) then begin match2i := s; match1s := i; find := 1; exit; end; end; find := 0;end;二分圖與網(wǎng)絡流的關系 例題4 攔截導彈n某國為了防御敵國的導彈襲擊，發(fā)展出一種導彈攔截某國為了防御敵國的導彈襲擊，發(fā)展出一種導彈攔截系統(tǒng)。但是這種導彈攔截系統(tǒng)系統(tǒng)。但是這種導彈攔截系統(tǒng) 有一個缺陷：雖然它的有一個缺陷：雖然它的第一發(fā)炮彈能夠到達任意的高度，但是以后每一發(fā)炮第一發(fā)炮彈能夠到達

10、任意的高度，但是以后每一發(fā)炮彈都不能高彈都不能高 于前一發(fā)的高度。某天，雷達捕捉到敵國于前一發(fā)的高度。某天，雷達捕捉到敵國的導彈來襲。由于只有一套系統(tǒng)，因此有可能不能攔的導彈來襲。由于只有一套系統(tǒng)，因此有可能不能攔截所有的導彈。截所有的導彈。 n已知導彈依次飛來的高度，計算已知導彈依次飛來的高度，計算 這套系統(tǒng)最多能攔截這套系統(tǒng)最多能攔截多少導彈，和如果要攔截所有導彈最少要配備多少套多少導彈，和如果要攔截所有導彈最少要配備多少套這種導彈攔截這種導彈攔截 系統(tǒng)。系統(tǒng)。 例題4 攔截導彈 標準解法n動態(tài)規(guī)劃n貪心法例題4 攔截導彈 匹配解法n將特殊情況一般化n建圖n化為最小路徑覆蓋最小路徑覆蓋n轉

11、換轉換n拆分頂點拆分頂點n化為二分圖匹配化為二分圖匹配例題5 傘兵降落n某個城市的街道圖是一個有向無環(huán)圖，某個城市的街道圖是一個有向無環(huán)圖，現(xiàn)在傘兵可在圖中任意一個節(jié)點降落，現(xiàn)在傘兵可在圖中任意一個節(jié)點降落，并負責清掃后面他走過的街道。并負責清掃后面他走過的街道。n任意一條街道必須有一個傘兵清掃，并任意一條街道必須有一個傘兵清掃，并不允許其他傘兵經(jīng)過不允許其他傘兵經(jīng)過n求最少需要的傘兵數(shù)求最少需要的傘兵數(shù)例題6 旅館預訂n一個旅館接到一個旅館接到n張定單，表示要從第張定單，表示要從第s天天開始入住，從第開始入住，從第e天結束并離開，天結束并離開，n求最少需要的房間數(shù)目，以滿足所有定求最少需要的

12、房間數(shù)目，以滿足所有定單的要求。單的要求。例題7 火星探測器n火星探測器要在一個火星探測器要在一個n*n的網(wǎng)格內(nèi)采集的網(wǎng)格內(nèi)采集巖石標本，它從巖石標本，它從(1,1)出發(fā)，到達出發(fā)，到達(n,n)n有些網(wǎng)格內(nèi)是標本，探測器第一次經(jīng)過有些網(wǎng)格內(nèi)是標本，探測器第一次經(jīng)過時將得到此標本時將得到此標本n有些網(wǎng)格內(nèi)是障礙物，不能通過有些網(wǎng)格內(nèi)是障礙物，不能通過n探測器只能走最短路線探測器只能走最短路線例題7 火星探測器 問題n問題問題1. 只有一個探測器，如何走采集到只有一個探測器，如何走采集到最多的標本？最多的標本？n問題問題2. 至少要幾個探測器才能收集完這至少要幾個探測器才能收集完這里所有的標本？里所有的標本？n問題問題3. 若只有若只有k個探測器，最多能收集個探測器，最多能收集到幾個標本？到幾個標本？例題8 打獵n獵人要在獵人要在n*n的格子里打鳥，他可以在的格子里打鳥，他可以