文档介绍：该【最大流算法及其应用公开课获奖课件赛课一等奖课件 】是由【读书之乐】上传分享，文档一共【45】页，该文档可以免费在线阅读，需要了解更多关于【最大流算法及其应用公开课获奖课件赛课一等奖课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。最大流算法及其应用
提要
网络流有关的某些概念
最大流和最小割问题
最大流算法的应用
总结
一、网络流有关的某些概念
流网络 (Flow Network)
流网络是一种有向图G=(V,E)，其中每条边(u,v)∈E均有一非负容量c(u,v)≥0。假如(u,v)∈E，则假定c(u,v)=0。流网络中有两个尤其的顶点：源点s和汇点t。
图1 一种流网络的例子
s
t
v1
v4
v5
v2
v3
v6
3
5
2
2
1
6
4
2
3
1
4
流 (Flow)
G的流是一种实值函数f，f(u,v)表达顶点u到顶点v的流，它可以为正，为零，也可以为负，且满足下列三个性质：
容量限制：对所有u,v∈V，规定f(u,v)≤c(u,v)。
反对称性：对所有u,v∈V ，规定f(u,v)=-f(v,u)。
流守恒性：对所有u,v∈V-{s,t}，规定
流量
整个流网络G的流量：
割 (Cut)
流网络G=(V,E)的割(S,T)将划提成S和T=V-S两部分，使得s∈S，t∈T。定义割(S,T)的容量为c(S,T)，则：
残留网络 (Residual Network)
给定一种流网络G=(V,E)和流f，由f压得的G的残留网络Gf=(V,Ef)，定义cf(u,v)为残留网络Gf中边(u,v)的容量。假如弧(u,v)∈E或弧(v,u)∈E，则(u,v)∈Ef，且cf(u,v) =c(u,v)-f(u,v)。在下面的多种概念和措施中，我们只考虑残留网络中容量不小于0的弧，不过编程时为了以便还是保留了。
增广途径 (Augmenting Path)
对于残留网络Gf中的一条s-t途径p称其为增广途径，定义增广途径p的残留容量为p上弧容量的最小值。背面求最大流要用到增广途径这个概念。