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

1、11.09.20221ACM 程序設(shè)計(jì)信息學(xué)院計(jì)算機(jī)應(yīng)用系 余臘生.11.09.20222今天，請(qǐng)個(gè)假,下周調(diào)課(西安).11.09.20223每周一星（8）：05072120.11.09.20224第九講二分圖及其應(yīng)用（Bipartite Graph & Applications）.11.09.20225主要內(nèi)容什么是二分圖二分圖的最大匹配匈牙利算法二分圖的最小頂點(diǎn)覆蓋DAG圖的最小路徑覆蓋二分圖的最大獨(dú)立集處理技巧.11.09.20226什么是二分圖？如果一個(gè)圖的頂點(diǎn)可以分為兩個(gè)集合X和Y，圖的所有邊一定是有一個(gè)頂點(diǎn)屬于集合X，另一個(gè)頂點(diǎn)屬于集合Y，則稱該圖為“二分圖”（ Bipartit

2、e Graph ）.11.09.20227例：婚配問題男女.11.09.20228二分圖的最大匹配 在二分圖的應(yīng)用中，最常見的就是最大匹配問題，很多其他的問題都可以通過轉(zhuǎn)化為匹配問題來解決。.11.09.20229如何求二分圖的最大匹配呢？.11.09.202210經(jīng)典算法：匈牙利算法.11.09.202211/*hdoj_1150匈牙利算法 月下版 */#include#include#includeusing namespace std;bool mark1100,mark2100;int list100;int n,m,edge,num;vectorvector v;bool dfs(i

3、nt to)register int i,point,s = listto;for(i=0;ivs.size();i+)point = vsi;if(!mark2point)continue;mark2point = false;if(listpoint=-1 | dfs(point)listpoint = s;return true;return false; void Solve()int i,j,point;bool flog = false;memset(mark1,true,sizeof(mark1);memset(list,-1,sizeof(list);num=0;for(i=0

4、;in;i+)for(j=0;jvi.size();j+)if(listvij = -1)mark1i = false;listvij = i;num+;if(i=0) flog = true;break; for(i=0;in;i+)if(mark1i)if(!vi.empty()memset(mark2,true,sizeof(mark2);for(j=0;jvi.size();j+)point = vij;if(!mark2point) continue;mark2point = false;if(listpoint = -1 | dfs(point)listpoint = i;num+

5、;break; mark1i = false; if(flog | list0 != -1)cout num-1 endl;else cout num n)if(n = 0)break;v.clear();v.resize(n);cin m edge;for(i=0;i j s d;vs.push_back(d); Solve(); return 0; .11.09.202212匈牙利算法(求二分圖最大匹配)談匈牙利算法自然避不開Hall定理Hall定理：對(duì)于二分圖G，存在一個(gè)匹配M，使得X的所有頂點(diǎn)關(guān)于M飽和的充要條件是：對(duì)于X的任意一個(gè)子集A，和A鄰接的點(diǎn)集為T(A)，恒有： |T(A)|

6、 = |A| .11.09.202213圖示（1）：男1男2女1女2女3返回.11.09.202214圖示（2）：男1男2女1女2女3返回X0=男2V1=男2V2 = T(V1)=女1Y=女1V1=男2，男1V2 =女1Y=女2MME(P)( 其中，P是從x0 y的可增廣道路 ).11.09.202215匈牙利算法是基于Hall定理中充分性證明的思想，其基本步驟為：1任給初始匹配M； 2若X已飽和則結(jié)束，否則進(jìn)行第3步； 3在X中找到一個(gè)非飽和頂點(diǎn)x0， 作V1 x0, V2 ； 4若T(V1) = V2則因?yàn)闊o法匹配而停止，否則任選一點(diǎn)y T(V1)V2； 5若y已飽和則轉(zhuǎn)6，否則做一條從x

7、0 y的可增廣道路P，MME(P)，轉(zhuǎn)2； 6由于y已飽和，所以M中有一條邊(y,z)，作 V1 V1 z, V2 V2 y， 轉(zhuǎn)4； .11.09.202216圖示（3）：男1男2女1女2返回X0=男2V1=男2V2 = T(V1)=女1T(V1) != V2Y=女1V1=男2，男1V2 =女1T(V1)=V2.11.09.202217NOTE:真正求二分圖的最大匹配的題目很少，往往做一些簡單的變化，比如.11.09.202218變種1：二分圖的最小頂點(diǎn)覆蓋在二分圖中求最少的點(diǎn)，讓每條邊都至少和其中的一個(gè)點(diǎn)關(guān)聯(lián)，這就是“二分圖的最小頂點(diǎn)覆蓋”。.11.09.202219實(shí) 例 分 析.11.

8、09.202220例：嚴(yán)禁早戀，違者開除！男生女生.11.09.202221例：任務(wù)安排有兩臺(tái)機(jī)器A和B以及N個(gè)需要運(yùn)行的任務(wù)。每臺(tái)機(jī)器有M種不同的模式，而每個(gè)任務(wù)都恰好在一臺(tái)機(jī)器上運(yùn)行。如果它在機(jī)器A上運(yùn)行，則機(jī)器A需要設(shè)置為模式ai,如果它在機(jī)器B上運(yùn)行，則機(jī)器A需要設(shè)置為模式bi。每臺(tái)機(jī)器上的任務(wù)可以按照任意順序執(zhí)行，但是每臺(tái)機(jī)器每轉(zhuǎn)換一次模式需要重啟一次。請(qǐng)合理為每個(gè)任務(wù)安排一臺(tái)機(jī)器并合理安排順序，使得機(jī)器重啟次數(shù)盡量少。hdoj_1150（LRJ_p331）ACM/ICPC Beijing 2002.11.09.202222圖示：結(jié)論： 二分圖的最小頂點(diǎn)覆蓋數(shù) = 二分圖的最大匹配數(shù)

9、a0a1a2a3a4b0b1b2b3b4.11.09.202223特別說明:此題需要注意的一點(diǎn)，具體參見： /forum/read.php?tid=61&keyword=%B6%FE%B7%D6.11.09.202224變種2： DAG圖的最小路徑覆蓋用盡量少的不相交簡單路徑覆蓋有向無環(huán)圖(DAG)G的所有頂點(diǎn)，這就是DAG圖的最小路徑覆蓋問題。.11.09.202225例：空襲（Air Raid） 有一個(gè)城鎮(zhèn)，它的所有街道都是單行的，并且每條街道都是和兩個(gè)路口相連。同時(shí)已知街道不會(huì)形成回路。 你的任務(wù)是編寫程序求最小數(shù)量的傘兵，這些傘兵可以訪問（visit）所有的路口。對(duì)于傘兵的起始降落點(diǎn)不

10、做限制。hdoj_1151 .11.09.202226Sample input:433 41 32 3Output: 2.11.09.202227“空襲”示意圖123443211324.11.09.202228結(jié)論：DAG圖的最小路徑覆蓋數(shù)=節(jié)點(diǎn)數(shù)（n）- 最大匹配數(shù)（m）關(guān)鍵：求二分圖的最大匹配數(shù).11.09.202229變種3:二分圖的最大獨(dú)立集Girls and Boys 大學(xué)二年級(jí)的時(shí)候，一些同學(xué)開始研究男女同學(xué)之間的緣分。研究者試圖找出沒有緣分同學(xué)的最大集。程序的結(jié)果就是要輸出這個(gè)集合中學(xué)生的數(shù)量。hdoj_1068 .11.09.202230輸入數(shù)據(jù)格式： 70: (3) 4 5 61: (2) 4 62: (0)3: (0)4: (2) 0 15: (1) 06: (2) 0 1輸出：5 .11.09.20223100154326543216“Girls and Boys”示意圖.11.09.202232結(jié)論：二分圖的最大獨(dú)立集數(shù)=節(jié)點(diǎn)數(shù)（n） 最大匹配數(shù)（m）關(guān)鍵：求二分圖的最大匹配數(shù).11.09.202233Any Questions?.11.09.2022