计算理论与算法分析设计：二部图 网络流

二部图&网络流11/6/20221二部图11/6/20222点覆盖集与点独立集的关系0+0=n

点覆盖数+点独立数=点数11/6/20223关于匹配中的其他概念定义

设M为G中一个匹配.(1)匹配边——(vi,vj)M(2)v为M饱和点——有M中边与v关联(3)v为M非饱和点——无M中边与v关联(4)M的交错路径——由匹配边和非匹配边交替构成的路径(5)M的增广路径——起、终点都是M非饱和点的交错路径11/6/20224最大匹配判别定理定理

M为G中最大匹配当且仅当G中不含M的可增广交错路径.11/6/20225二部图匹配匈牙利算法11/6/20226增广路径匹配M={{x1,y1},{x2,y3},{x3,y4}}有一条增广路径x1x2y1y2x3x4y3y4x1x2y1y2x3x4y3y4x1x2y1y2x3x4y3y4由M增广路径可构造比M大的匹配存在M增广路径M非最大匹配用(M-)(

-M)代替Mx1x2y1y2x3x4y3y411/6/20227匈牙利算法由增广路径的定义可以推出下述三个结论：1、的路径长度必定为奇数，第一条边和最后一条边都不属于M。2、经过取对称差操作可以得到一个更大的匹配M。3、M为G的最大匹配当且仅当不存在关于M的增广路径。11/6/20228匈牙利算法用增广路径求最大匹配(称作匈牙利算法)算法：(1)置M为空(2)找出一条增广路

，通过取对称差操作获得更大的匹配M代替M(3)重复(2)操作直到找不出增广路径为止11/6/20229匈牙利算法示例

图1图2

11/6/202210匈牙利算法核心代码#defineN202intuseif[N];//记录y中结点是否使用intlink[N];//记录当前与y结点相连的x的结点intmat[N][N];//记录连接x和y的边，如果i和j之间有边则为1，否则为0intgn,gm;//二分图中x和y中点的数目11/6/202211intcan(intt){inti;for(i=1;i<=gm;i++){if(useif[i]==0&&mat[t][i]){useif[i]=1;if(link[i]==-1||can(link[i])){link[i]=t;return1;}}}return0;}intMaxMatch(){inti,num;num=0;memset(link,0xff,sizeof(link));for(i=1;i<=gn;i++){

memset(useif,0,sizeof(useif));if(can(i))num++;}returnnum;}intuseif[N];//记录y中结点是否使用intlink[N];//记录当前与y结点相连的x的结点intmat[N][N];//记录连接x和y的边intgn,gm;//二分图中x和y中点的数目11/6/202212二部图的最小点覆盖定理:G是二部图,则0=1.即二部图的最大匹配数=最小点覆盖数

注:定理对一般图不成立.11/6/202213二部图的最大独立集定理：二部图中:最大独立集数＝顶点总数－最小点覆盖数

也＝顶点总数－最大匹配数11/6/202214例题1

PlacetheRobots问题描述有一个N*M(N,M<=50)的棋盘，棋盘的每一格是三种类型之一：空地、草地、墙。机器人只能放在空地上。在同一行或同一列的两个机器人，若它们之间没有墙，则它们可以互相攻击。问给定的棋盘，最多可以放置多少个机器人，使它们不能互相攻击。

WallGrass

Empty11/6/202215例题1

PlacetheRobots（ZOJ）模型一5467832112346578于是，问题转化为求图的最大独立集问题。以空地为顶点，有冲突的空地之间连边，可以得到右边的这个图：11/6/202216例题1

PlacetheRobots模型一5467832112346578这是NP问题！11/6/202217将每一行，每一列被墙隔开且包含空地的连续区域称作“块”。显然，在一个块之中，最多只能放一个机器人。把这些块编上号。同样，把竖直方向的块也编上号。例题1

PlacetheRobots（ZOJ）模型二12345123411/6/202218例题1

PlacetheRobots模型二123451234把每个横向块看作X部的点，竖向块看作Y部的点，若两个块有公共的空地，则在它们之间连边。于是，问题转化成这样的一个二部图：11223344511/6/202219由于每条边表示一个空地，有冲突的空地之间必有公共顶点，所以问题转化为二部图的最大匹配问题。例题1

PlacetheRobots模型二12341235411223344511/6/202220例题2

打猎猎人要在n*n的格子里打鸟,他可以在某一行中打一枪,这样此行中的所有鸟都被打掉，也可以在某一列中打,这样此列中的所有鸟都打掉.问至少打几枪,才能打光所有的鸟？建图：二部图的X部为每一行，Y部为每一列，如果(i,j)有一只鸟，那么连接X部的i与Y部的j。该二部图最小点覆盖数即是最少要打的枪数。@@@@@11/6/202221GirlsandBoys

Thesecondyearoftheuniversitysomebodystarteda

studyontheromanticrelationsbetweenthestudents.

Therelation“romanticallyinvolved”isdefinedbetween

onegirlandoneboy.Forthestudyreasonsitisnecessary

tofindoutthemaximumsetsatisfyingthecondition:

therearenotwostudentsinthesetwhohavebeen

“romanticallyinvolved”.Theresultoftheprogramisthe

numberofstudentsinsuchaset.

Theinputcontainsseveraldatasetsintextformat.

Eachdatasetrepresentsonesetofsubjectsofthestudy,

withthefollowingdescription:

thenumberofstudents

thedescriptionofeachstudent,inthefollowingformat11/6/202222GirlsandBoysstudent_identifier:(number_of_romantic_relations)

student_identifier1student_identifier2...

or

student_identifier:(0)

Thestudent_identifierisanintegernumberbetween0

andn-1,fornsubjects.

Foreachgivendataset,theprogramshouldwritetostandardoutputalinecontainingtheresult.

11/6/202223GirlsandBoysSampleInput

70:(3)4561:(2)46Y:(0)E:(0)4:(2)015:(1)06:(2)01

Output501YE45611/6/202224网络流简介

11/6/202225流,流量,最大流sv1v3v2v4t11/168/13101/412/1215/204/47/74/911/14称f:VVR为流,若f满足：(1)容量限制,f(u,v)c(u,v)(2)反对称性,f(u,v)=-f(v,u)(3)流守恒性,任意uV\{s,t},vVf(u,v)=0流量|f|=vVf(s,v).

最大流:给定流网络G,s,t,c,求

max{|f|:f是G的流}11/6/20222611/6/202227流网络的割割(S,T):(1)T=V-S(2)sS,tT.f(S,T)=uS,vTf(u,v):f穿过割(S,T)的净流c(S,T)=uS,vTc(u,v):割(S,T)的容量sv1v3v2v4t11/168/13101/412/1215/204/47/74/911/14←ST→例.下图中的割(S,T),S={s,v1,v2},T={v3,v4,t}.

f(S,T)=19,

c(S,T)=26.11/6/202229最大流最小割定理

f(S,T)=|f|,|f|min{c(S,T)|割(S,T)}.

定理(最大流最小割)下列条件等价

(1)f是G的一个最大流;

(2)Gf不包含增广路径;

(3)存在割(S,T)使得|f|=c(S,T).

最大流算法基本思想:

找从s到t的增广路径,增大流,无则停止,得最大流11/6/202230sadbct16,1113,810,4,112,1220,157,79,414,114,4sadbct5511312575348114111511/6/202231剩余图增广之后的新流sadbct161310412207914420,sadbct16,413,10,4,12,47,9,414,44,4sadbct124482075104104413420,7sadbct16,1113,10,74,12,47,79,414,114,411/6/202232剩余图增广之后的新流20,7sadbct16,1113,10,74,12,47,79,414,114,4134sadbct51111875334111347sadbct16,1113,810,4,112,1220,157,79,414,114,411/6/202233剩余图增广之后的新流sadbct16,1113,810,4,112,1220,157,79,414,114,4sadbct55113125753481141115sadbct16,1113,1210,4,112,1220,197,79,14,114,411sadbct51113121793412111911/6/20223422134222221342222,21342,22,22,02,022134222222,21342,02,22,22,212342222211/6/20223522134222212342222212342222a2b22c2d211/6/202236剩余图sabt10001000110001000解决方法：(1)EK算法:在剩余图中找最短增广路径(2)最大容量增广算法:找最大瓶颈容量11/6/202237练习1:无向图的网络流下图为某地区运输网.边上的数字表示运输能力（单位：万吨/小时），则从顶点1到顶点5的最大运输能力可以达到_____万吨/小时.120424101068532411/6/202238练习2《算法导论》P40026.1-9ProfessorAdamhastwochildrenwho,unfortunately,dislikeeachother.Theproblemissoseverethatnotonlydotheyrefusetowalktoschooltogether,butinfacteachonerefusestowalkonanyblockthattheotherchildhassteppedonthatday.Thechildrenhavenoproblemwiththeirpathscrossingatacorner.Fortunatelyboththeprofessor'shouseandtheschoolareoncorners,butbeyondthatheisnotsureifitisgoingtobepossibletosendbothofhischildrentothesameschool.Theprofessorhasamapofhistown.Showhowtoformulatetheproblemofdeterminingifbothhischildrencangotothesameschoolasamaximum-flowproblem.11/6/202239最大流题目选讲1.DinningFarmerJohn的牛饿了，到了午餐时间需要吃饭和喝饮料，现在已知有n头牛，a种食物和b种饮料，每头牛都有一些食物和饮料是喜欢的，牛们只会吃喜欢的食物和喜欢的饮料，每种食物和饮料只有一份，现在请问最多有多少头牛能够吃到喜欢的食物和饮料。11/6/202240最大流题目选讲增加源点src与汇点dst，src到每种食物连一条容量为1的边，保证每种食物只用一次，同理每种饮料到汇点连一条容量为1的边，保证每种饮料只用一次。将每头牛拆成两个点，中间连一条容量为1的边，保证每头牛只用一次，每种食物到喜欢他的牛左侧的点连容量为INF的边，每头牛右侧的点到每种饮料连容量为INF的边，求最大流即可。11/6/202241最大流题目选讲2.喜羊羊与灰太狼在一个M*N的方格形地图上，有一些格子中有羊，有一些格子中有狼，还有一些格子是空地，每个格子内最多只能有一只狼或羊，先要沿着格子边沿修建围墙，请问最少修建多长的围墙能够将狼和羊隔开。11/6/202242最大流题目选讲实际上是一个多源汇最小割问题，我们把地图中每个方格作为网络中的一个节点，任意相邻两个方格建立双向容量为1的边。此时我们假设有狼的格子为源点，有羊的格子为汇点，显然只要有从任意源点到达任意汇点的一个流，则说明狼可以通过这条路径吃到羊，所以只要割断这个图就可以隔开狼和羊，而每割断一条边正好对应修建一段墙，原问题也就成功转化为多源汇最小割问题。为解决问题，我们添加超级源点src和超级汇点dst，src到每个狼的格子有容量为INF的边，每个羊的格子到dst有容量为INF的边，在此网络中由最大流最小割定理，求出最大流即为答案11/6/202243最大流题目选讲3.越狱现有一囚犯越狱，需要通过一块长为l宽为w的空地，先已知这块空地上有n个守卫，每个守卫的坐标已知，同时每个守卫都有一个监控范围r，也就是说囚犯进入以某个守卫为中心半径为r的圆内就会被发现，越狱行动失败，现在为了成功越狱，此人决定干掉一些守卫，请问最少干掉多少个守卫就能够成功越狱而不被发现。11/6/202244阿P与阿Q都是四驱车好手，他们各有N辆四驱车。为了一比高下，他们约好进行一场比赛。这次比赛共有M个分站赛，赢得分站赛场次多的获得总冠军。每个分站赛中，两人各选一辆自己的赛车比赛。分站赛的胜负大部分取决于两车的性能，但由于种种原因（如相互之间的干扰），性能并不是决定胜负的唯一指标，有时会出现A赢B、B赢C、C赢D、D又赢A的局面。幸好有一种高智能机器，只要给定两辆四驱车，就能立刻判断谁会赢，在总比赛前它就已经把阿p的每辆车与阿q的每辆车都两两测试过了，并且还把输赢表输入了电脑。

11/6/202245

另外，由于比赛的磨损，每辆四驱车都有自己的寿命（即它们能参加分站赛的场次），不同的四驱车寿命可能不同，但最多不会超过50场。两辆四驱车最多只能交手一次。现给定N、M（1<=N<=100，1<=M<=1000）、N*N的一个输赢表、每辆四驱车的寿命，并假设每次分站赛两人都有可选的赛车，请你计算一下阿P最多能够赢得多少个分站赛。11/6/202246

1、建立N个点代表阿P的N辆车，分别以1到N标号；

2、建立N个点代表阿Q的N辆车，分别以N+1到2N标号；

3、如果阿P的第I辆车能够跑赢阿Q的第J辆车，则加一条弧IN+J，容量为1，表示两辆四驱车最多只能交手一次；

4、增加一个源点S，S与1到N中的每一个结点I都连一条弧SI，容量为阿P的第I辆车的寿命；

5、增加一个汇点T，N+1到2N中的每一个结点N+J到T都连一条弧N+JT，容量为阿Q的第J辆车的寿命；

6、再增加一个源点S2，加一条弧S2S，容量为M，表示最多M场分站赛。11/6/20224711/6/202248线性规划简介

11/6/202249线性规划(LinearProgramming)线性规划问题线性规划的图解法11/6/202250一、线性规划问题

设备产品ABCD利润（万元）

Ⅰ21402

Ⅱ22043

有效台时1281612

例、已知资料如右表所示，问如何安排生产才能使利润最大？模型maxZ=2x1+3x2

x1≥0,x2≥0s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12此为带约束的极值问题11/6/202251目标函数：约束条件：①②③2、线性规划数学模型的一般形式11/6/202252一般有两种方法图解法单纯形法两个变量、直角