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

1、11.09.20221ACM 程序設(shè)計信息學(xué)院計算機應(yīng)用系 余臘生.11.09.20222今天，請個假,下周調(diào)課(西安).11.09.20223每周一星（8）：05072120.11.09.20224第九講二分圖及其應(yīng)用（Bipartite Graph & Applications）.11.09.20225主要內(nèi)容什么是二分圖二分圖的最大匹配匈牙利算法二分圖的最小頂點覆蓋DAG圖的最小路徑覆蓋二分圖的最大獨立集處理技巧.11.09.20226什么是二分圖？如果一個圖的頂點可以分為兩個集合X和Y，圖的所有邊一定是有一個頂點屬于集合X，另一個頂點屬于集合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定理：對于二分圖G，存在一個匹配M，使得X的所有頂點關(guān)于M飽和的充要條件是：對于X的任意一個子集A，和A鄰接的點集為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é)束，否則進行第3步； 3在X中找到一個非飽和頂點x0， 作V1 x0, V2 ； 4若T(V1) = V2則因為無法匹配而停止，否則任選一點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：二分圖的最小頂點覆蓋在二分圖中求最少的點，讓每條邊都至少和其中的一個點關(guān)聯(lián)，這就是“二分圖的最小頂點覆蓋”。.11.09.202219實 例 分 析.11.

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

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

10、做限制。hdoj_1151 .11.09.202226Sample input:433 41 32 3Output: 2.11.09.202227“空襲”示意圖123443211324.11.09.202228結(jié)論：DAG圖的最小路徑覆蓋數(shù)=節(jié)點數(shù)（n）- 最大匹配數(shù)（m）關(guān)鍵：求二分圖的最大匹配數(shù).11.09.202229變種3:二分圖的最大獨立集Girls and Boys 大學(xué)二年級的時候，一些同學(xué)開始研究男女同學(xué)之間的緣分。研究者試圖找出沒有緣分同學(xué)的最大集。程序的結(jié)果就是要輸出這個集合中學(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é)論：二分圖的最大獨立集數(shù)=節(jié)點數(shù)（n） 最大匹配數(shù)（m）關(guān)鍵：求二分圖的最大匹配數(shù).11.09.202233Any Questions?.11.09.2022