二分圖匹配及其應(yīng)用

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

2、種顏色染n實(shí)現(xiàn)：深度優(yōu)先搜索二分圖判斷問(wèn)題解答1nvarn visited: array1.100 of integer;n data: array1.1001.100 of integer;n n: integer;n success: boolean;二分圖判斷問(wèn)題解答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;二分圖判斷問(wèn)題解答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二分圖，存在完美匹配的充分必要條件是，對(duì)于任意一個(gè)頂點(diǎn)集合的子集A，它的相鄰點(diǎn)構(gòu)成的鄰集X(A)，都滿(mǎn)足以下條件：AAX)(HALL

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

5、路（交錯(cuò)軌）的概念n匈牙利算法：找增廣路n如何找？算法選擇？增廣路和匈牙利算法 實(shí)例11x5x4x3x2x1y2y3y4y5y增廣路和匈牙利算法 實(shí)例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)絡(luò)流的關(guān)系 例題4 攔截導(dǎo)彈n某國(guó)為了防御敵國(guó)的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截某國(guó)為了防御敵國(guó)的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng) 有一個(gè)缺陷：雖然它的有一個(gè)缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮第一發(fā)炮彈能夠到達(dá)

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

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

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