图论与算法第八讲 最大流问题.ppt

《算法艺术与信息学竞赛》算法图论第八讲最大流问题声明本系列教学幻灯片属于刘汝佳、黄亮著《算法艺术与信息学竞赛》配套幻灯片本幻灯片可从本书blog上免费下载,,欢迎和作者联系以取得技术支持,也欢迎提供有不同针对性的修改版本,方便更多人使用有任何意见,欢迎在blog上评论Blog地址:、最大流问题二、Ford-Fulkerson方法三、Edmond-Karp算法四、预流推进算法五、应用举例一、最大流问题流网络定义一个流网络(work)G=(V,E)是一个有向图,每个边(u,v)有一个非负容量(capacity)c(u,v)>=(u,v),规定c(u,v)=0有两个特殊结点:源(source)s和汇(sink),存在通路svt流的定义流(flow)是一个边的函数f(u,v),满足:容量限制:f(u,v)<=c(u,v)对称性:f(u,v)=-f(u,v)收支平衡:对于不是s或t的其他点u,有把整个网络的流量定义为(即从s流出的流量):最大流问题:寻找流函数f,使得网络流最大记号X和Y为结点集,定义记号f(X,Y)引理:在以f为流函数的流网络中,以下三个等式成立f(X,X)=0F(X,Y)=-f(X,Y)若X和Y不相交,f(XUY,Z)=f(X,Z)+f(Y,Z)可以定义流的加法和标量积(注意容量限制)可以证明:可行流集合是凸的,即如果f1和f2都是流,对于所有0<=α<=1,αf1+(1-α)?可以进行流取消(cancelling)只保留一边附加s和t,则s-t流变为循环流流分解定理:任意循环流可以分解为不超过E个有向环的并二、Ford-Fulkerson方法基本思想从零流开始迭代,每次沿着增广路(augmentingpath)调整流量,直到不存在增广路,算法停止算法梗概