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

二部图&网络流二部图2024/7/43

of220点覆盖集与点独立集的关系

0+

0=n

点覆盖数+点独立数=点数2024/7/44

of220关于匹配中的其他概念定义

设M为G中一个匹配.(1)匹配边——(vi,vj)

M(2)v为M饱和点——有M中边与v关联(3)v为M非饱和点——无M中边与v关联(4)M的交错路径——由匹配边和非匹配边交替构成的路径(5)M的增广路径——起、终点都是M非饱和点的交错路径2024/7/45

of220最大匹配判别定理定理

M为G中最大匹配当且仅当G中不含M的可增广交错路径.二部图匹配匈牙利算法2024/7/47

of220增广路径匹配M={{x1,y1},{x2,y3},{x3,y4}}有一条增广路径

x1x2y1y2x3x4y3y4x1x2y1y2x3x4y3y4x1x2y1y2x3x4y3y4由M增广路径可构造比M大的匹配存在M增广路径

M非最大匹配用(M-

)(

-M)代替Mx1x2y1y2x3x4y3y42024/7/48

of220匈牙利算法由增广路径的定义可以推出下述三个结论：1、

的路径长度必定为奇数，第一条边和最后一条边都不属于M。2、

经过取对称差操作可以得到一个更大的匹配M

。3、M为G的最大匹配当且仅当不存在关于M的增广路径。2024/7/49

of220匈牙利算法用增广路径求最大匹配(称作匈牙利算法)算法：(1)置M为空(2)找出一条增广路

，通过取对称差操作获得更大的匹配M

代替M(3)重复(2)操作直到找不出增广路径为止2024/7/410

of220匈牙利算法示例

图1图22024/7/411

of220匈牙利算法核心代码#defineN202intuseif[N];//记录y中结点是否使用intlink[N];//记录当前与y结点相连的x的结点intmat[N][N];//记录连接x和y的边，如果i和j之间有边则为1，否则为0intgn,gm;//二分图中x和y中点的数目2024/7/412

of220intcan(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中点的数目2024/7/413

of220二部图的最小点覆盖定理:G是二部图,则

0=1.即二部图的最大匹配数=最小点覆盖数

注:定理对一般图不成立.2024/7/414

of220二部图的最大独立集定理：二部图中:最大独立集数＝顶点总数－最小点覆盖数

也＝顶点总数－最大匹配数2024/7/415

of220例题1

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

WallGrass

Empty2024/7/416

of220例题1

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

of220例题1

PlacetheRobots模型一5467832112346578这是NP问题！2024/7/418

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

PlacetheRobots（ZOJ）模型二1234512342024/7/419

of220例题1

PlacetheRobots模型二123451234把每个横向块看作X部的点，竖向块看作Y部的点，若两个块有公共的空地，则在它们之间连边。于是，问题转化成这样的一个二部图：1122334452024/7/420

of220由于每条边表示一个空地，有冲突的空地之间必有公共顶点，所以问题转化为二部图的最大匹配问题。例题1

PlacetheRobots模型二1234123541122334452024/7/421

of220例题2

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

of220GirlsandBoys

Thesecondyearoftheuniversitysomebodystarteda

studyontheromanticrelationsbetweenthestudents.

Therelation“romanticallyinvolved”isdefinedbetween

onegirlandoneboy.Forthestudyreasonsitisnecessary

tofindoutthemaximumsetsatisfyingthecondition:

therearenotwostudentsinthesetwhohavebeen

“romanticallyinvolved”.Theresultoftheprogramisthe

numberofstudentsinsuchaset.

Theinputcontainsseveraldatasetsintextformat.

Eachdatasetrepresentsonesetofsubjectsofthestudy,

withthefollowingdescription:

thenumberofstudents

thedescriptionofeachstudent,inthefollowingformat2024/7/423

of220GirlsandBoysstudent_identifier:(number_of_romantic_relations)

student_identifier1student_identifier2...

or

student_identifier:(0)

Thestudent_identifierisanintegernumberbetween0

andn-1,fornsubjects.

Foreachgivendataset,theprogramshouldwritetostandardoutputalinecontainingtheresult.

2024/7/424

of220GirlsandBoysSampleInput

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

Output501YE456网络流简介

2024/7/426

of220流,流量,最大流sv1v3v2v4t11/168/13101/412/1215/204/47/74/911/14称f:V

V

R为流,若f满足：(1)容量限制,f(u,v)

c(u,v)(2)反对称性,f(u,v)=-f(v,u)(3)流守恒性,任意u

V\{s,t},

v

Vf(u,v)=0流量|f|=

v

Vf(s,v).

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

max{|f|:f是G的流}2024/7/427

of220流网络的割割(S,T):(1)T=V-S(2)sS,t

T.f(S,T)=

u

S,v

Tf(u,v):f穿过割(S,T)的净流c(S,T)=

u

S,v

Tc(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.2024/7/429

of2202024/7/430

of220最大流最小割定理

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的增广路径,增大流,无则停止,得最大流2024/7/431

of220sadbct16,1113,810,4,112,1220,157,79,414,114,4sadbct551131257534811411152024/7/432

of220剩余图增广之后的新流sadbct161310412207914420,sadbct16,413,10,4,12,47,9,414,44,4sadbct124482075104104413420,7sadbct16,1113,10,74,12,47,79,414,114,42024/7/433

of220剩余图增广之后的新流20,7sadbct16,1113,10,74,12,47,79,414,114,4134sadbct51111875334111347sadbct16,1113,810,4,112,1220,157,79,414,114,42024/7/434

of220剩余图增广之后的新流sadbct16,1113,810,4,112,1220,157,79,414,114,4sadbct55113125753481141115sadbct16,1113,1210,4,112,1220,197,79,14,114,411sadbct5111312179341211192024/7/435

of22022134222221342222,21342,22,22,02,022134222222,21342,02,22,22,21234222222024/7/436

of22022134222212342222212342222a2b22c2d22024/7/437

of220剩余图sabt10001000110001000解决方法：(1)EK算法:在剩余图中找最短增广路径(2)最大容量增广算法:找最大瓶颈容量2024/7/438

of220练习1:无向图的网络流下图为某地区运输网.边上的数字表示运输能力（单位：万吨/小时），则从顶点1到顶点5的最大运输能力可以达到_____万吨/小时.12042410106853242024/7/439

of220练习2《算法导论》P40026.1-9ProfessorAdamhastwochildrenwho,unfortunately,dislikeeachother.Theproblemissoseverethatnotonlydotheyrefusetowalktoschooltogether,butinfacteachonerefusestowalkonanyblockthattheotherchildhassteppedonthatday.Thechildrenhavenoproblemwiththeirpathscrossingatacorner.Fortunatelyboththeprofessor'shouseandtheschoolareoncorners,butbeyondthatheisnotsureifitisgoingtobepossibletosendbothofhischildrentothesameschool.Theprofessorhasamapofhistown.Showhowtoformulatetheproblemofdeterminingifbothhischildrencangotothesameschoolasamaximum-flowproblem.2024/7/440

of220最大流题目选讲1.DinningFarmerJohn的牛饿了，到了午餐时间需要吃饭和喝饮料，现在已知有n头牛，a种食物和b种饮料，每头牛都有一些食物和饮料是喜欢的，牛们只会吃喜欢的食物和喜欢的饮料，每种食物和饮料只有一份，现在请问最多有多少头牛能够吃到喜欢的食物和饮料。2024/7/441

of220最大流题目选讲增加源点src与汇点dst，src到每种食物连一条容量为1的边，保证每种食物只用一次，同理每种饮料到汇点连一条容量为1的边，保证每种饮料只用一次。将每头牛拆成两个点，中间连一条容量为1的边，保证每头牛只用一次，每种食物到喜欢他的牛左侧的点连容量为INF的边，每头牛右侧的点到每种饮料连容量为INF的边，求最大流即可。2024/7/442

of220最大流题目选讲2.喜羊羊与灰太狼在一个M*N的方格形地图上，有一些格子中有羊，有一些格子中有狼，还有一些格子是空地，每个格子内最多只能有一只狼或羊，先要沿着格子边沿修建围墙，请问最少修建多长的围墙能够将狼和羊隔开。2024/7/443

of220最大流题目选讲实际上是一个多源汇最小割问题，我们把地图中每个方格作为网络中的一个节点，任意相邻两个方格建立双向容量为1的边。此时我们假设有狼的格子为源点，有羊的格子为汇点，显然只要有从任意源点到达任意汇点的一个流，则说明狼可以通过这条路径吃到羊，所以只要割断这个图就可以隔开狼和羊，而每割断一条边正好对应修建一段墙，原问题也就成功转化为多源汇最小割问题。为解决问题，我们添加超级源点src和超级汇点dst，src到每个狼的格子有容量为INF的边，每个羊的格子到dst有容量为INF的边，在此网络中由最大流最小割定理，求出最大流即为答案2024/7/444

of220最大流题目选讲3.越狱现有一囚犯越狱，需要通过一块长为l宽为w的空地，先已知这块空地上有n个守卫，每个守卫的坐标已知，同时每个守卫都有一个监控范围r，也就是说囚犯进入以某个守卫为中心半径为r的圆内就会被发现，越狱行动失败，现在为了成功越狱，此人决定干掉一些守卫，请问最少干掉多少个守卫就能够成功越狱而不被发现。2024/7/445

of220

阿P与阿Q都是四驱车好手，他们各有N辆四驱车。为了一比高下，他们约好进行一场比赛。这次比赛共有M个分站赛，赢得分站赛场次多的获得总冠军。每个分站赛中，两人各选一辆自己的赛车比赛。分站赛的胜负大部分取决于两车的性能，但由于种种原因（如相互之间的干扰），性能并不是决定胜负的唯一指标，有时会出现A赢B、B赢C、C赢D、D又赢A的局面。幸好有一种高智能机器，只要给定两辆四驱车，就能立刻判断谁会赢，在总比赛前它就已经把阿p的每辆车与阿q的每辆车都两两测试过了，并且还把输赢表输入了电脑。

2024/7/446

of220

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

of220

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

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

3、如果阿P的第I辆车能够跑赢阿Q的第J辆车，则加一条弧I

N+J，容量为1，表示两辆四驱车最多只能交手一次；

4、增加一个源点S，S与1到N中的每一个结点I都连一条弧S

I，容量为阿P的第I辆车的寿命；

5、增加一个汇点T，N+1到2N中的每一个结点N+J到T都连一条弧N+J

T，容量为阿Q的第J辆车的寿命；

6、再增加一个源点S2，加一条弧S2

S，容量为M，表示最多M场分站赛。2024/7/448

of220线性规划简介

2024/7/450

of220线性规划(LinearProgramming)线性规划问题线性规划的图解法2024/7/451

of220一、线性规划问题

设备产品ABCD利润（万元）

Ⅰ21402

Ⅱ22043

有效台时1281612

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

x1≥0,x2≥0s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12此为带约束的极值问题2024/7/452

of220目标函数：约束条件：①②③2、线性规划数学模型的一般形式2024/7/453

of220一般有两种方法图解法单纯形法两个变量、直角坐标三个变量、立体坐标