信息學(xué)競(jìng)賽算法分析與設(shè)計(jì)

1、1,信息學(xué)競(jìng)賽——算法分析與設(shè)計(jì),2,本節(jié)課程內(nèi)容,二分圖、匹配(bipartite graph、matching) 匈 牙 利 算 法 Kuhn-Munkras算法,3,二分圖的概念,二分圖又稱作二部圖，是圖論中的一種特殊模型。設(shè)G=(V,{R})是一個(gè)無(wú)向圖。如頂點(diǎn)集V可分割為兩個(gè)互不相交的子集，并且圖中每條邊依附的兩個(gè)頂點(diǎn)都分屬兩個(gè)不同的子集。則稱圖G為二分圖。,4,最大匹配,給定一個(gè)二分圖G，在G的一個(gè)子圖M中，M

2、的邊集{E}中的任意兩條邊都不依附于同一個(gè)頂點(diǎn)，則稱M是一個(gè)匹配。選擇這樣的邊數(shù)最大的子集稱為圖的最大匹配問(wèn)題(maximal matching problem)如果一個(gè)匹配子圖中，圖中的每個(gè)頂點(diǎn)都和匹配子圖中某條邊相關(guān)聯(lián)，則稱此匹配為完全匹配，也稱作完備匹配。,5,匈牙利算法,求最大匹配的一種顯而易見的算法是：先找出全部匹配，然后保留匹配數(shù)最多的。但是這個(gè)算法的復(fù)雜度為邊數(shù)的指數(shù)級(jí)函數(shù)。因此，需要尋求一種更加高效的算法。增廣路的

3、定義(也稱增廣軌或交錯(cuò)軌)： 若P是圖G中一條連通兩個(gè)未匹配頂點(diǎn)的路徑，并且屬M(fèi)的邊和不屬M(fèi)的邊(即已匹配和待匹配的邊)在P上交替出現(xiàn)，則稱P為相對(duì)于M的一條增廣路徑。,6,匈牙利算法,由增廣路的定義可以推出下述三個(gè)結(jié)論：1. P的路徑長(zhǎng)度必定為奇數(shù)，第一條邊和最后一條邊都不屬于M。2. P經(jīng)過(guò)取反操作可以得到一個(gè)更大的匹配M’。3. M為G的最大匹配當(dāng)且僅當(dāng)不存在相對(duì)于M的增廣路徑。,7,匈牙利算法,用增廣路

4、求最大匹配(稱作匈牙利算法，匈牙利數(shù)學(xué)家Edmonds于1965年提出)算法輪廓：(1)置M為空(2)找出一條增廣路徑P，通過(guò)取反操作獲得更大的匹配M’代替M(3)重復(fù)(2)操作直到找不出增廣路徑為止,8,9,設(shè)G是具有二部劃分(V1,V2)的二分圖.(1)任給初始匹配M;(2)若M飽和V1則結(jié)束.否則轉(zhuǎn)(3);(3)在V1中找一非M飽和點(diǎn)x,置S={x},T=?;(4)若N(S)=T,則停止,否則任選一點(diǎn)y?N(S)-

5、T;(5)若y為M飽和點(diǎn)轉(zhuǎn)(6),否則作求一條從x到y(tǒng)的M可增廣路P,置M=M?P,轉(zhuǎn)(2)(6)由于y是M飽和點(diǎn),故M中有一邊{y,u},置S=S?{u},T=T?{y},轉(zhuǎn)(4).,匈牙利算法步驟,10,匈牙利算法,程序清單： #include#includebool g[201][201];int n,m,ans;bool b[201];int link[201];,11,匈牙利算法,bool init(

6、){ int _x,_y; memset(g,0,sizeof(g)); memset(link,0,sizeof(link)); ans=0; if(scanf(“%d%d”,&n,&m)==EOF) return false; for(int i=1;i<=n;i++) { scanf(“%d”,&_x); for(int j=0;

7、j<_x;j++) { scanf(“%d”,&_y); g[ i ][_y]=true; } } return true;},12,匈牙利算法,bool find(int a){ for(int i=1;i<=m;i++) { if(g[a][ i ]==1&&!b[ i ])

8、 { b[ i ]=true; if(link[ i ]==0||find(link[ i ])) { link[ i ]=a; return true; } } } return false;},13,匈牙利算法,int main(){while(

9、init()){ for(int i=1;i<=n;i++) { memset(b,0,sizeof(b)); if(find(i)) ans++; }printf("%d\n",ans);}},14,求二部圖G = ( X, Y, E )的(匈牙利算法)迭代步驟:,從G的任意匹配M開始. ① 將X中M的所有非飽和點(diǎn)都給以標(biāo)號(hào)

10、0和標(biāo)記*, 轉(zhuǎn)向②. M的非飽和點(diǎn)即非M的某條邊的頂點(diǎn). ② 若X中所有有標(biāo)號(hào)的點(diǎn)都已去掉了標(biāo)記*, 則M是G的最大匹配. 否則任取X中一個(gè)既有標(biāo)號(hào)又有標(biāo)記*的點(diǎn)xi , 去掉xi的標(biāo)記*, 轉(zhuǎn)向③. ③ 找出在G中所有與xi鄰接的點(diǎn)yj , 若所有這樣的yj都已有標(biāo)號(hào), 則轉(zhuǎn)向②, 否則轉(zhuǎn)向④.,15,④ 對(duì)與xi鄰接且尚未給標(biāo)號(hào)的yj都給定標(biāo)號(hào)i.,若所有的 yj 都是M的飽和點(diǎn),則轉(zhuǎn)向⑤,否則逆向返回.

11、即由其中M的任一個(gè)非飽和點(diǎn) yj 的標(biāo)號(hào)i 找到xi ,再由 xi 的標(biāo)號(hào)k 找到 yk ,…,最后由 yt 的標(biāo)號(hào)s找到標(biāo)號(hào)為0的xs時(shí)結(jié)束,獲得M-增廣路xs yt … xi yj , 記P ={xs yt , … , xi yj },重新記M為M⊕P,轉(zhuǎn)向①. 不必理會(huì)M-增廣路的定義. M⊕P = M∪P \ M∩P, 是對(duì)稱差. ⑤ 將yj在M中與之鄰接的點(diǎn)xk ,給以標(biāo)號(hào) j 和標(biāo)記*, 轉(zhuǎn)向②.,

12、16,例 求下圖所示二部圖G的最大匹配.,解 ① 取初始匹配M0 ={x2 y2 , x3 y3 , x5 y5} (上圖粗線所示). ② 給X中M0的兩個(gè)非飽和點(diǎn)x1,x4都給以標(biāo)號(hào)0和標(biāo)記* (如下圖所示).,17,② 給X中M0的兩個(gè)非飽和點(diǎn)x1,x4都給以標(biāo)號(hào)0和標(biāo)記* (如下圖所示). ② 給X中M0的兩個(gè)非飽和點(diǎn)x1,x4都給以標(biāo)號(hào)0和標(biāo)記* (如下圖所示).,18,③ 去掉x1的標(biāo)記*, 將與x1鄰接的兩個(gè)點(diǎn)y

13、2, y3都給以標(biāo)號(hào)1. 因?yàn)閥2, y3都是M0的兩個(gè)飽和點(diǎn),所以將它們?cè)贛0中鄰接的兩個(gè)點(diǎn)x2, x3都給以相應(yīng)的標(biāo)號(hào)和標(biāo)記* (如下圖所示).,19,,④ 去掉x2的標(biāo)記*, 將與x2鄰接且尚未給標(biāo)號(hào)的三個(gè)點(diǎn)y1, y4, y5都給以標(biāo)號(hào)2 (如下圖所示).,20,⑤ 因?yàn)閥1是M0的非飽和點(diǎn), 所以順著標(biāo)號(hào)逆向返回依次得到x2, y2, 直到x1為0為止.于是得到M0的增廣路x1 y2x2 y1, 記P = {x1 y2 , y

14、2x2 , x2 y1}. 取M1 = M0⊕P = {x1 y2 , x2 y1 , x3 y3 , x5 y5}, 則M1是比M多一邊的匹配(如下圖所示).,21,⑥ 再給X中M1的非飽和點(diǎn)x4給以標(biāo)號(hào)0和標(biāo)記*, 然后去掉x4的標(biāo)記*, 將與x4鄰接的兩個(gè)點(diǎn)y2, y3都給以標(biāo)號(hào)4.,因?yàn)閥2, y3都是M1的兩個(gè)飽和點(diǎn), 所以將它們?cè)贛1中鄰接的兩個(gè)點(diǎn)x1, x3都給以相應(yīng)的標(biāo)號(hào)和標(biāo)記* (如下圖所示).,22,⑦ 去掉x1的標(biāo)

15、記*, 因?yàn)榕cx1鄰接的兩個(gè)點(diǎn)y2, y3都有標(biāo)號(hào)4, 所以去掉x3的標(biāo)記*.,而與x3鄰接的兩個(gè)點(diǎn)y2, y3也都有標(biāo)號(hào)4, 此時(shí)X中所有有標(biāo)號(hào)的點(diǎn)都已去掉了標(biāo)記*(如下圖所示), 因此M1是G的最大匹配.,G不存在飽和X的每個(gè)點(diǎn)的匹配, 當(dāng)然也不存在完美匹配.,23,最佳匹配,如果邊上帶權(quán)的話，找出權(quán)和最大的匹配叫做求最佳匹配。實(shí)際模型：某公司有職員x1,x2,…,xn,他們?nèi)プ龉ぷ鱵1,y2,…,yn,每個(gè)職員做各項(xiàng)工作的效益未

16、必一致，需要制定一個(gè)分工方案，使得人盡其才，讓公司獲得的總效益最大。數(shù)學(xué)模型：G是加權(quán)完全二分圖，求總權(quán)值最大的完備匹配。,24,KM算法,窮舉的效率－n！，需要更加優(yōu)秀的算法。定理： 設(shè)M是一個(gè)帶權(quán)完全二分圖G的一個(gè)完備匹配，給每個(gè)頂點(diǎn)一個(gè)可行頂標(biāo)(第i個(gè)x頂點(diǎn)的可行標(biāo)用lx[i]表示，第j個(gè)y頂點(diǎn)的可行標(biāo)用ly[j]表示)，如果對(duì)所有的邊(i,j) in G,都有l(wèi)x[i]+ly[j]>=w[i,j]

17、成立(w[i,j]表示邊的權(quán))，且對(duì)所有的邊(i,j) in M,都有l(wèi)x[i]+ly[j]=w[i,j]成立，則M是圖G的一個(gè)最佳匹配。,25,KM算法,對(duì)于任意的G和M，可行頂標(biāo)都是存在的：l(x) = maxw(x,y)l(y) = 0欲求完全二分圖的最佳匹配，只要用匈牙利算法求其相等子圖的完備匹配；問(wèn)題是當(dāng)標(biāo)號(hào)之后的Gl無(wú)完備匹配時(shí)怎么辦？1957年Kuhn和Munkras 給出了一個(gè)解決該問(wèn)題的有效算法，用逐次修改可行頂

18、標(biāo)l(v)的辦法使對(duì)應(yīng)的相等子圖之最大匹配逐次增廣，最后出現(xiàn)完備匹配。,26,KM算法,修改方法如下：先將一個(gè)未被匹配的頂點(diǎn)u(u in {x})做一次增廣路，記下哪些結(jié)點(diǎn)被訪問(wèn)那些結(jié)點(diǎn)沒(méi)有被訪問(wèn)。求出d=min{lx[i]+ly[j]-w[i,j]}其中i結(jié)點(diǎn)被訪問(wèn)，j結(jié)點(diǎn)沒(méi)有被訪問(wèn)。然后調(diào)整lx和ly：對(duì)于訪問(wèn)過(guò)的x頂點(diǎn)，將它的可行標(biāo)減去d，對(duì)于所有訪問(wèn)過(guò)的y頂點(diǎn)，將它的可行標(biāo)增加d。修改后的頂標(biāo)仍是可行頂標(biāo)，原來(lái)的匹配M仍然存在

19、，相等子圖中至少出現(xiàn)了一條不屬于M的邊，所以造成M的逐漸增廣。,27,KM算法,上述算法的證明也很容易Kuhn－Munkras算法流程：(1)初始化可行頂標(biāo)的值(2)用匈牙利算法尋找完備匹配(3)若未找到完備匹配則修改可行頂標(biāo)的值(4)重復(fù)(2)(3)直到找到相等子圖的完備匹配為止,28,作業(yè)：,1325 Machine Schedule 2062 Card Game Cheater 2195 Going Home 22

20、26 Muddy Fields,29,附錄：,1 Place the Robots（ZOJ） 2 救護(hù)傷員（TOJ1148）3 打獵4 最小路徑覆蓋5 一些例子6 二部圖相關(guān)的定義、定理,30,例題1 Place the Robots（ZOJ1654）,問(wèn)題描述 有一個(gè)N*M(N,M<=50)的棋盤，棋盤的每一格是三種類型之一：空地、草地、墻。機(jī)器人只能放在空地上。在同一行或同一列的兩個(gè)機(jī)器

21、人，若它們之間沒(méi)有墻，則它們可以互相攻擊。問(wèn)給定的棋盤，最多可以放置多少個(gè)機(jī)器人，使它們不能互相攻擊。,31,例題1 Place the Robots（ZOJ）,模型一,于是，問(wèn)題轉(zhuǎn)化為求圖的最大獨(dú)立集問(wèn)題。,在問(wèn)題的原型中，草地，墻這些信息不是我們所關(guān)心的，我們關(guān)心的只是空地和空地之間的聯(lián)系。因此，我們很自然想到了下面這種簡(jiǎn)單的模型：以空地為頂點(diǎn)，有沖突的空地間連邊，我們可以得到右邊的這個(gè)圖：,32,例題1 Place the

22、Robots（ZOJ）,模型一,在問(wèn)題的原型中，草地，墻這些信息不是我們所關(guān)心的，我們關(guān)心的只是空地和空地之間的聯(lián)系。因此，我們很自然想到了下面這種簡(jiǎn)單的模型：以空地為頂點(diǎn)，有沖突的空地間連邊，我們可以得到右邊的這個(gè)圖：,這是NP問(wèn)題！,33,我們將每一行，每一列被墻隔開，且包含空地的連續(xù)區(qū)域稱作“塊”。顯然，在一個(gè)塊之中，最多只能放一個(gè)機(jī)器人。我們把這些塊編上號(hào)。,同樣，把豎直方向的塊也編上號(hào)。,例題1 Place the Rob

23、ots（ZOJ）,模型二,1,2,3,4,5,34,例題1 Place the Robots（ZOJ）,模型二,1,2,3,4,5,把每個(gè)橫向塊看作X部的點(diǎn)，豎向塊看作Y部的點(diǎn)，若兩個(gè)塊有公共的空地，則在它們之間連邊。,于是，問(wèn)題轉(zhuǎn)化成這樣的一個(gè)二部圖：,35,由于每條邊表示一個(gè)空地，有沖突的空地之間必有公共頂點(diǎn)，所以問(wèn)題轉(zhuǎn)化為二部圖的最大匹配問(wèn)題。,例題1 Place the Robots（ZOJ）,模型二,1,2,3,5,4,3

24、6,比較前面的兩個(gè)模型：模型一過(guò)于簡(jiǎn)單，沒(méi)有給問(wèn)題的求解帶來(lái)任何便利；模型二則充分抓住了問(wèn)題的內(nèi)在聯(lián)系，巧妙地建立了二部圖模型。為什么會(huì)產(chǎn)生這種截然不同的結(jié)果呢？其一是由于對(duì)問(wèn)題分析的角度不同：模型一以空地為點(diǎn)，模型二以空地為邊；其二是由于對(duì)原型中要素的選取有差異：模型一對(duì)要素的選取不充分，模型二則保留了原型中“棋盤”這個(gè)重要的性質(zhì)。由此可見，對(duì)要素的選取，是圖論建模中至關(guān)重要的一步。,例題1 Place the Robots（ZOJ

25、）,小結(jié),37,例題2 救護(hù)傷員（TOJ1148）,無(wú)情的海嘯奪取了無(wú)數(shù)人的生命.很多的醫(yī)療隊(duì)被派往災(zāi)區(qū)拯救傷員.就在此時(shí),醫(yī)療隊(duì)突然發(fā)現(xiàn)自己帶的藥品已經(jīng)不夠用了,只剩下了N種。(1 < n <= 20)，隨著病人病情的發(fā)展，每種藥在每天能獲得的效果是不一樣的。同時(shí)，每天病人只能服用一種藥。也就是說(shuō)，這些藥還夠支持N天?，F(xiàn)在，給出你每種藥在每天使用的效果，請(qǐng)你判斷當(dāng)每種藥都用完后所有藥達(dá)到的效果之和最大可以是多少。,38,

26、例題3 打獵,獵人要在n*n的格子里打鳥，他可以在某一行中打一槍，這樣此行中的所有鳥都被打掉，也可以在某一列中打，這樣此列中的所有鳥都打掉。問(wèn)至少打幾槍，才能打光所有的鳥？建圖：二分圖的X部為每一行，Y部為每一列，如果(i,j)有一只鳥，那么連接X(jué)部的i與Y部的j。該二分圖的最大匹配數(shù)則是最少要打的槍數(shù)。,39,例題4 最小路徑覆蓋,一個(gè)不含圈的有向圖G中，G的一個(gè)路徑覆蓋是一個(gè)其結(jié)點(diǎn)不相交的路徑集合P，圖中的每一個(gè)結(jié)點(diǎn)僅包含于P

27、中的某一條路徑。路徑可以從任意結(jié)點(diǎn)開始和結(jié)束，且長(zhǎng)度也為任意值，包括0。請(qǐng)你求任意一個(gè)不含圈的有向圖G的最小路徑覆蓋數(shù)。理清一個(gè)關(guān)系：最小路徑覆蓋數(shù)＝G的結(jié)點(diǎn)數(shù)－最小路徑覆蓋中的邊數(shù),40,例題4 最小路徑覆蓋,試想我們應(yīng)該使得最小路徑覆蓋中的邊數(shù)盡量多，但是又不能讓兩條邊在同一個(gè)頂點(diǎn)相交。拆點(diǎn)：將每一個(gè)頂點(diǎn)i拆成兩個(gè)頂點(diǎn)Xi和Yi。然后根據(jù)原圖中邊的信息，從X部往Y部引邊。所有邊的方向都是由X部到Y(jié)部。,41,例題4 最小路徑覆蓋

28、,因此，所轉(zhuǎn)化出的二分圖的最大匹配數(shù)則是原圖G中最小路徑覆蓋上的邊數(shù)。因此由最小路徑覆蓋數(shù)＝原圖G的頂點(diǎn)數(shù)－二分圖的最大匹配數(shù)便可以得解。,42,例1 m項(xiàng)工作準(zhǔn)備分給n個(gè)人去做，如圖，其中邊（xi,yj)表示xi,可以從事yj ，如果每個(gè)人最多從事其中一項(xiàng)，且每項(xiàng)工作只能由一人擔(dān)任。問(wèn)怎樣才能使盡可能多的人安派上任務(wù)。,,,二分圖，如xj從事了yi就不能從事yk,同時(shí)yi也不允許其它人擔(dān)任。相當(dāng)于用一種顏色，例如紅色，對(duì)G的邊著色，

29、保證每個(gè)結(jié)點(diǎn)最多與一條紅色邊相聯(lián)，這種紅色邊的集合記為M它是圖G的一個(gè)匹配。計(jì)算G中邊數(shù)最多的匹配。,43,例2 二次大站期間，許多盟軍飛行員到英國(guó)參加對(duì)法西斯的空襲，當(dāng)時(shí)每架飛機(jī)需領(lǐng)航員和飛行員各一名。其中有些只能領(lǐng)航，有些只能駕駛，也有人二者均會(huì)。加之二人語(yǔ)言要求相通，如果以結(jié)點(diǎn)表示人，邊表示二人語(yǔ)言相通并且一人可領(lǐng)航，另一人可駕駛一可得一圖，這是一簡(jiǎn)單圖那么最多的編隊(duì)方案就是求成過(guò)急G的一個(gè)最大匹配。,44,例.有n張紙牌,每張

30、紙牌的正反兩面都寫上1,2,…n的某一個(gè)數(shù),證明:如果每個(gè)數(shù)字恰好出現(xiàn)兩次,則這些紙牌一定可以這樣攤開,使朝上的面中1,2,…n都出現(xiàn).,45,例 某工廠生產(chǎn)由6種不同顏色的紗織成的布，由這個(gè)工廠生產(chǎn)的雙色布中每一種顏色至少和其它三種顏色搭配。證明可以挑選出三種不同的雙色布，他們含有所有的6種顏色。,46,二部圖： 一些例子,作者-文章(author-literature)演員-電影(actor-film)基因-疾病(gene

31、-disease)藥物-靶標(biāo)(drug-protein target)基礎(chǔ)醫(yī)學(xué)和臨床中的數(shù)據(jù)？。。。。。。。。,47,相關(guān)定義、定理,定理1： 簡(jiǎn)單圖G為二部圖?G中所有基本回路的長(zhǎng)度為偶數(shù)。定義1：設(shè)無(wú)向圖G＝，M?E，若M中任意兩條邊都不相鄰，則稱M為G的一個(gè)匹配，并把M中的邊所關(guān)聯(lián)的兩個(gè)結(jié)點(diǎn)稱為在M下是匹配的。若在M中再加入任何一條邊就不是匹配了，稱M為極大匹配。邊數(shù)最多的極大匹配稱為G的最大匹配。最大匹配中的邊的個(gè)數(shù)稱為

32、G的匹配數(shù)。 M是G中的一個(gè)匹配，若結(jié)點(diǎn)v與M中的邊關(guān)聯(lián)，稱v為M飽和點(diǎn)，否則稱v為M非飽和點(diǎn)。若G中每個(gè)結(jié)點(diǎn)都是M飽和點(diǎn)，稱M是完全匹配。,48,,定義2 ：設(shè)G＝為二部圖，M是G中一個(gè)最大匹配，若|M|＝min{|V1|，|V2|}，稱M為G中的一個(gè)完備匹配。若此時(shí)|V1|?|V2|，稱M為V1到V2的一個(gè)完備匹配。若|V1|＝|V2|，稱M為G的完全匹配。定理3(Hall定理)：設(shè)G＝，|V1|?|V2|，G中存

33、在從V1到V2的完備匹配?V1中任意k個(gè)結(jié)點(diǎn)(k＝1，2，…，|V1|)至少鄰接V2中的k個(gè)結(jié)點(diǎn)。,49,,定理4 (t條件)：設(shè)G＝，若V1中每個(gè)結(jié)點(diǎn)至少關(guān)聯(lián)t(t＞0)條邊，而V2中每個(gè)結(jié)點(diǎn)至多關(guān)聯(lián)t條邊，則G中存在V1到V2的完備匹配。推論：G＝，對(duì)任意v∈V1或V2有d(v)＝k＞0，則G有一個(gè)完全匹配。,50,例：某大學(xué)計(jì)算機(jī)系有3個(gè)課外學(xué)習(xí)小組：網(wǎng)絡(luò)組、網(wǎng)頁(yè)制作組和數(shù)據(jù)庫(kù)組。今有張、王、李、趙、陳5名同學(xué)。若已知：

34、 (1)張、王為網(wǎng)絡(luò)組成員，張、李、趙為網(wǎng)頁(yè)制作組成員，李、趙、陳為數(shù)據(jù)庫(kù)組成員； (2)張為網(wǎng)絡(luò)組成員，王、李、趙為網(wǎng)頁(yè)制作組成員，王、李、趙、陳為數(shù)據(jù)庫(kù)組成員； (3)張為網(wǎng)絡(luò)組和網(wǎng)頁(yè)制作組成員，王、李、趙、陳為數(shù)據(jù)庫(kù)組成員。 問(wèn)以上3種情況下能否各選出3名不兼職的組長(zhǎng)？,51,例 某中學(xué)有3個(gè)課外小組:物理組、化學(xué)組、生物組.今有張、王、李、趙、陳5名同學(xué).若已知: (1)

35、張、王為物理組成員,張、李、趙為化學(xué)組成員,李、趙、陳為生物組成員; (2)張為物理組成員,王、李、趙為化學(xué)組成員,王、李、趙、陳為生物組成員; (3)張為物理組和化學(xué)組成員,王、李、趙、陳為生物組成員. 問(wèn)在以上3種情況下能否各選出3名不兼職的組長(zhǎng)？,52,解：設(shè)v1，v2，v3，v4，v5分別表示張、王、李、趙、陳，u1，u2，u3分別表示網(wǎng)絡(luò)組、網(wǎng)頁(yè)制作組、數(shù)據(jù)庫(kù)組，則根據(jù)上述三種情況得到的二部圖如圖10-26所示。,53,

36、G1滿足t=2的t條件,所以,存在從V1={u1,u2,u3}到V2={v1,v2,v3,v4,v5}的完備匹配,圖中粗邊所示的匹配就是其中的一個(gè),即選張為物理組組長(zhǎng)、李為化學(xué)組組長(zhǎng)、趙為生物組組長(zhǎng).G2不滿足t條件,但滿足相異性條件,因而也存在完備匹配,圖中粗邊所示匹配就是其中的一個(gè)完備匹配. G3不滿足t條件,也不滿足相異性條件,因而不存在完備匹配,故選不出3名不兼職的組長(zhǎng)來(lái).,54,因?yàn)閳D(a)滿足t＝2的t條件，所以圖(a)