《《网络流基础》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《网络流基础》PPT课件.ppt（21页珍藏版）》请在三一办公上搜索。
1、网络流基础,6-4 秦政,基本概念,一个 流 网 络(flow network)G=(V,E)是一个有向图，每条边(u,v)有一个非负容量(capacity)c(u,v)=0，对于不在E中的(u,v)，规定c(u,v)=0。有两个特殊结点：源点(source)s和汇点(sink)t。假设对于任意其他点v，存在通路s-v-t。,基本概念,可以这样抽象的理解流网络：可以把这样的流网络看作是运送物资的交通网络，我们希望从s往t运送物品。由于对于任意点v都存在s-v-t通路，因此不用担心物品运丢。但这个过程仍然是有限制的。,基本概念,流量的性质定义在每条边上运送物品的数量f(u,v)，则：容量限制：f
2、(u,v)=c(u,v)对称性：f(u,v)=-f(v,u)收支平衡：对于不是s或t的其他点u，有sigmaf(u,v)=0,(u,v)in E,基本概念,定义整个网络的流量f为从s流出的流量，它也等于从t收集到的流量。,基本概念,理论上弧的两个方向可以同时有流量，但实际上这是没有必要的，我们可以用所谓的流取消(flow cancelling)方法只保留其中的一边。残量网络(residual network)。我们常常使用残量网络来设计算法，它的基本思想是：把已有的流看作网络本身的一部分，把有流的网络转化成无流的网络。根据这个想法，定义弧(u,v)的残量容量为cf(u,v)=c(u,v)-f(
3、u,v)，它的含义是该弧的最大流增量。,基本概念,所有大于0的残量弧所构成的网络称为残量网络，由于每条弧最多可以从两边增加流量，因此|Ef|2|E|。残量网络的每条s-t路称为增广路，因为沿着它进行增广可以增加网络的流量。定义增广路总残量容量最小值d为该路的残量容量，则把路上每条弧的流量增加d，反向流量减少d（由对称性）后，所得的流仍然是可行的，且流量增加了d。残量网络的好处是我们不用考虑流和真实容量。,最大流问题,求流网络中最大流量的问题叫做最大流问题。,基本定理,增广路定理：流量f是最大流当且仅当残量网络中不存在可增广路。整流定理：如果网络中所有容量是整数，则最大流也是整数。,最大流算法,
4、增广路算法：Ford-Fulkerson方法，Edmonds-Karp(EK)(NM2)，SAP(N2M)，Dinic(N2M)预流推进算法：Preflow-Push(PP)(N2M)，FIFOPP(N3)，HLPP(N2M1/2),增广路算法,每次找一条增广路进行增广(Ford-Fulkerson方法)每次用BFS找到一条增广路进行增广(Edmonds-Karp算法)每次找到最短增广路进行增广(SAP算法)每次找到最短路图进行增广(Dinic算法),增广路算法,路径标号：残量网络中以s为起点的最短路径长度d(i)如果一条弧(i,j)满足d(i)=d(j)+1，我们说该弧是允许弧，全由允许弧组
5、成的s-t路径称为允许路径。允许路径的重要性质是：任何s-t允许路径都是s-t最短路Dinic算法：每次求一次最短路，然后对所有的允许路径进行增广While(lab()aug();,切割,给定网络G=(V,E)，取C为E的一个子集，当删去C后，点A和点B不在联通，则称C为G的一个A-B切割。C中容量之和称为切割C的容量。最小割问题：求最小容量的切割C。,基本定理,最大流最小割定理：最大流等于最小切割的容量。特别的，平面图的最小割等于对偶图上的最短路。,费用流问题,流网络中的每条边除了容量c还有一个参数w表示每单位流量产生的费用，一个流的费用W=sigmaf(e)*w(e),e in E在最大流
6、的基础上求最小费用的问题：最小费用最大流在最大流的基础上求最大费用的问题：最大费用最大流,费用流算法,每次求最短路，然后增广while(spfa()aug();,拓展问题,多源汇的流问题 附加超级源超级汇顶点有容量限制的流问题 拆点无向图变有向图 拆边有上下界的流问题,上下界的流问题,对于每条边除了有上界c(u,v)，还有下界b(u,v)，既满足：b(u,v)0，则连边S-v容量为d(v)，若d(v)T容量为-d(v)从原图的汇t向原图的源s连边容量为无穷,Drainage Ditches,在农夫约翰的农场上，每逢下雨，贝茜最喜欢的三叶草地就积聚了一潭水。这意味着草地被水淹没了，并且小草要继续
7、生长还要花相当长一段时间。因此，农夫约翰修建了一套排水系统来使贝茜的草地免除被大水淹没的烦恼（不用担心，雨水会流向附近的一条小溪）。作为一名一流的技师，农夫约翰已经在每条排水沟的一端安上了控制器，这样他可以控制流入排水沟的水流量。农夫约翰知道每一条排水沟每分钟可以流过的水量，和排水系统的准确布局（起点为水潭而终点为小溪的一张网）。需要注意的是，有些时候从一处到另一处不只有一条排水沟。根据这些信息，计算从水潭排水到小溪的最大流量。对于给出的每条排水沟，雨水只能沿着一个方向流动，注意可能会出现雨水环形流动的情形。,Profit,新的技术正冲击着手机通讯市场，对于各大运营商来说，这既是机遇，更是挑战
8、。THU集团旗下的CS&T通讯公司在新一代通讯技术血战的前夜，需要做太多的准备工作，仅就站址选择一项，就需要完成前期市场研究、站址勘测、最优化等项目。在前期市场调查和站址勘测之后，公司得到了一共N个可以作为通讯信号中转站的地址，而由于这些地址的地理位置差异，在不同的地方建造通讯中转站需要投入的成本也是不一样的，所幸在前期调查之后这些都是已知数据：建立第i个通讯中转站需要的成本为Pi（1iN）。另外公司调查得出了所有期望中的用户群，一共M个。关于第i个用户群的信息概括为Ai,Bi和Ci：这些用户会使用中转站Ai和中转站Bi进行通讯，公司可以获益Ci。（1iM,1Ai,BiN）THU集团的CS&T
9、公司可以有选择的建立一些中转站（投入成本），为一些用户提供服务并获得收益（获益之和）。那么如何选择最终建立的中转站才能让公司的净获利最大呢？（净获利=获益之和 投入成本之和）,The Best Picture in the Galaxy,Professor Valentin Vladimirovich,member of the Galaxy Academy,tomorrow takes part in voting for nomination“The Best Picture”.But professor havent watched any ofnnominee movies yet a
10、nd he doesnt in fact have time today.He decided to ask help from hiskstudents,who still havent got credit for his subjects.If the students watch all the movies and then tell professor briefly about their impressions,this information will be enough to make a choice.Each of the nominee movies is shown
11、 in the movie halls only once,theith movie starts at timeaiand finishes at timebi.A student can watch any number of movies through the day,but he must watch each one from start to finish.A student cant watch two movies simultaneously.It is also known thatcibeautiful actresses star in theith movie.A
12、student wont go for a movie if less actresses star in it than in the previous movie he watched.Valentin Vladimirovich gave students detailed instructions in case they cant watch all the movies in one day.The movies are numbered in descending order according to descending popularity of their director
13、s.If students can see either setAof movies or setBof movies,the setAis more preferable if there is suchithat:the movies with numbers from 1 toi 1 are either present in both setsAandB,or not present in neitherAnorB;theith movie is present in the setAand is not present in the setB.Find the most preferable set of movies for Valentin Vladimirovich and his students.,
