资源描述：
《数据结构和网络算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、1最大流1.1定义Tarjan:数据结构和网络算法Ford和Fulkerson,网络的流，1962（论文1956）Ahuja,Maganti,Orlin网络流。问题：在一个图中，找到一个灵活的流，并且有最大值。有向图，边的容量u(e)或u(v,w)为什么不是c?为了将来为花费保留。源s，汇t目标：为每条边分配一个流值：（剩余/总的流形式）ò守恒：∑wg(v,w)−g(w,v)=0除非v=s,tò容量：0≤g(e)≤u(e)ò流值f=∑wg(s,w)−g(w,s)水管的例子。也是行程安排，所传递的信息要在最大容量以内
2、，等。通常来说，”每一单位时间”流/容量。最大流问题：找到最大的流值。可供选择的公式：（网络流形式）ò注意f(v,w)−f(w,v)的差别ò在两个方向上都增加是没有影响的ò斜对称：f(v,w)=f(w,v)ò守恒：∑wf(v,w)=0除非v=s,tò容量：f(e)≤u(e)（流是可行的/合法的）同等：第一个公式有“总的流”g,第一有“网流”f(v,w)=g(v,w)−g(w,v).换句话说，f标志了g中流的“方向”。从直觉来说，总的流很好。但是对于分析来说，我们将专注于网络流模型。路径分解：ò任何s−t流都能被分解
3、成有数量的路径ò证明：引入非零流变的数目ò如果s有一个向外的流，找到一条s−t路径并切断它ò如果一些向量有向外的流，找到一个圆，并切断它ò推论：进入t的流等于流出s的流（整体守恒）点A.15分钟到此处割：1ò将向量分成两个组ò如s−t割，如一个是s，其它属于tò表示成(S,S)或是S.òf(s)=离开S的网络流。ò引理：对任意的s−t切割，f(s)=f–假设v从S移到S–将f(v,S)假如跨流值–也加入f(v,S)–总变化：f(v,S∪S)=0流向量切ò推论：f≤u(S)=∑e∈S×Su(e)ò换而言之：最大值≤s
4、=t切割的最小值ò马上，我们会看见是相等的ò总之，需要更多机器剩余网络ò给定图中的流f'ò定义Gf的容量ue=ue−feò如果f是灵活的，所有容量都是正的ò因为fe可以是负的，一些剩余容量增加'ò假设f是在Gf中的一个灵活流''ò那么f=f是图G中的灵活流，值为f=fò流ò灵活'ò假设f是G中的灵活流''ò那么f−f是G中的灵活流（值f−f)ò推论：G中的最大流相应于中的最大流Gfò许多最大流的算法2–找到一些流f–在Gf上反复我们怎么知道一个流是最大流？ò检查剩余网络有0最大流ò增广路径：在Gf中的s−t路径正值
5、ò如果一个存在，不是最大流最大流最小割ò等同于–f是最大流–在Gf中没有增广路径–对于一些S来说，f=u(S)证明:ò如果增广路径，可以增加fò令S为Gf中可以到达S的向量，所有出去的边有f(e)=u(e)ò因为f≤u(S)，即为最大值1.2算法1.2.1增广路径总是可以找到一个如果容量是整数，总可以找到一个整数ò因此终止ò运行时间O(mf)ò引理：流的整数性ò为单位容量图多项式ò若是实数的话，可能不会终止注意：复数贪心算法ò总是有增光路径ò但增光路径可能相互矛盾，为边加入流然后移动位ò菱形例子(s,x),(s,y
6、),(y,t),(x,t),(x,y).1.2.2最大容量增广路径如何找出？3运行时间ò回忆流分解边界ò每次处理流的1/mò所以mlogf流足够整数f弱势对强势多项式边界有理容量1.3尺度最大容量增广是贪心的ò尽快找到最多的解决ò尽快减少剩余流ò另一个方法：尺度Gabow’85òAlso[Dintiz‘73]，butappearedonlyinRussianso，asoftenthecaseinthiserea，theAmericandiscoverywasmuchlaterbutindependent。基本理论是
7、对“总的数值例子”应用“单位例子”想法：数是位；位是单位例子尺度是一致的反向ò从圆的下面的值开始ò按逆序排列最大好处：不管尺度停顿，一般与单位例子一样简单ò容量是logU位数ò所有容量从0开始ò每移动容量的一位，从高序开始并且向低走ò通过在剩余网络中找到最大流来更新最大流ò作用–将所有的容量和流值变成双倍–使剩余容量变为双倍–为一些剩余容量加1ò在进行了logU，所有的数是正确的。因此流是最大流算法：反复ò每次一动一位ò运行增光路径分析：ò在位移动之前，一些割的容量是0ò在位移动之后，割的容量至多为mò因此m增广是
8、充足的运行时间：O(m2logU)讨论与最大容量算法的关系4多项式，但不是许多的多项式点B：从点A到这1.4问题变化多个源边的低的边界匹配向量容量1.5应用矩阵旋转Prj,pmtnCmax1.5.1最短增光路径强多项式取而代之贪心算法，通过一个双重函数解决ò思想：如果s,t离得很远，网络中没有许多流能适合ò因此试图推入s,t剩余距离引理：对于最短增广，(s,
