最大流问题

落日映苍穹つ 2022-04-11 07:25 362阅读 0赞

# 举例描述 #

最大流问题是一个很经典的问题，很多人对此也很熟悉，它能够等同于一个线性规划问题。下面给出最大流问题的一个基本描述：如下图所示，s是源点，t为汇点，每条边上数字的含义是边能够允许流过的最大流量。可以将边看成管道，0/3代表该管道每秒最多能通过3个单位的流量，0代表当前流量。最大流问题即是说，从s点到t点，最大允许流量是多少？

![这里写图片描述][20160906163124911]

# 公式描述 #

![这里写图片描述][20160906163217411]  
的流量等于流出该点的流量。这个可以理解为流量守恒，就如同电流一样，流入一个电阻的电流必然等于流出的电流。

那么最大流就可以表示为：  
![这里写图片描述][20160906163251710]

# Ford-Fulkerson解法介绍 #

## 该方法依赖于三种重要思想：残留网络，增广路径和割 ##

# Ford-Fulkerson思想 #

Ford-Fulkerson是一种迭代的方法。开始时，对所有的u,v属于V，f(u,v)=0(这里f(u,v)代表u到v的边当前流量)，即初始状态时流的值为0。在每次迭代中，可以通过寻找一个“增广路径”来增加流值。增广路径可以看做是从源点s到汇点t之间的一条路径，沿该路径可以压入更多的流，从而增加流的值。反复进行这一过程，直到增广路径都被找出为止。

# 增广路径 #

举个例子来说明下，如图所示，每条红线就代表了一条增广路径，当前s到t的流量为3。当然这并不是该网络的最大流，根据寻找增广路径的算法我们其实还可以继续寻找增广路径。

![这里写图片描述][20160906163553272]

# 残留网络 #

顾名思义，残留网络是指给定网络和一个流，其对应还可以容纳的流组成的网络。具体说来，就是假定一个网络G=（V，E），其源点s，汇点t。设f为G中的一个流，对应顶点u到顶点v的流。在不超过C（u，v）的条件下（C代表边容量），从u到v之间可以压入的额外网络流量，就是边（u，v）的残余容量（residual capacity），定义如下：

r（u，v）=c（u，v）-f（u，v）

举个例子，假设（u，v）当前流量为3/4，那么就是说c（u，v）=4，f（u，v）=3，那么r（u，v）=1。

我们知道，在网络流中还有这么一条规律。从u到v已经有了3个单位流量，那么从反方向上看，也就是从v到u就有了3个单位的残留网络，这时r（v，u）=3。可以这样理解，从u到v有3个单位流量，那么从v到u就有了将这3个单位流量的压回去的能力。

我们来具体看一个例子，如下图所示一个流网络

![这里写图片描述][20160906163801570]

## 对应的残留网络： ##

![这里写图片描述][20160906163826953]

# 求解步骤举例 #

# 1.获得残留网络 #

# 2.穷举所有的增广路径 #

# 如下图所示： #

![这里写图片描述][20160906164042540]

# 计算最大流的标号法 #

这里介绍计算网络最大流的简便方法—标号法，此方法是Ford—Fulkerson 于1956年提出来的，它的原理是利用寻找增广链来不断改善可行流。  
设μ是网络中 到 的一条链，规定 到 的方向为μ的方向。 μ上与μ的方向一致的弧称为前向弧，前向弧的集合记为μ＋， μ上与μ的方向相反的弧称为后向弧，后向弧的集合记为μ-。

![这里写图片描述][20160906164335227]  
上图  
若给一个可行流｛｝，称网络中 = 的弧为饱和弧，称 ＜的弧为非饱和弧，称 =0的弧为零流弧，称 ＞0的弧为非零流弧。  
增广链：设｛｝是可行流， μ是 到 的一条链，若μ满足下列条件，则称μ为关于 f 的增广链。（注意： f =｛｝）  
1°对于任何（ ,）∈μ＋，0≤ ＜ （前向弧为非饱和弧）  
2°对于任何（ ,）∈μ-，0 ＜≤ （后向弧为非零流弧）

博客参考：

smartxxyx的两篇博客：  
[http://blog.csdn.net/smartxxyx/article/details/9275177][http_blog.csdn.net_smartxxyx_article_details_9275177]  
[http://blog.csdn.net/smartxxyx/article/details/9293665/][http_blog.csdn.net_smartxxyx_article_details_9293665]  
以及：  
[http://dec3.jlu.edu.cn/webcourse/t000048/yun/ch7\_04.htm][http_dec3.jlu.edu.cn_webcourse_t000048_yun_ch7_04.htm]

## 我的微信二维码如下，欢迎交流讨论 ##

![这里写图片描述][20160805162827934]

# 欢迎关注《IT面试题汇总》微信订阅号。每天推送经典面试题和面试心得技巧 #

## 微信订阅号二维码如下： ##

![这里写图片描述][20160805162844330]

[20160906163124911]: /images/20220411/48a511b1ee794329bd986709810c6b3b.png
[20160906163217411]: /images/20220411/012a9589a4d1454ab30eec01d1152aa3.png
[20160906163251710]: /images/20220411/cae8d767c3994531a8eb5bca206385fb.png
[20160906163553272]: /images/20220411/3ddcc47f4bb54718b8d0fa15a7daa7de.png
[20160906163801570]: /images/20220411/6608d7b4853e444ba1ea88d7f451337d.png
[20160906163826953]: /images/20220411/f4f1d552b5224bf88c3538f5f7d41fe0.png
[20160906164042540]: /images/20220411/63f3f92287e942f495a4413ae2f0e1e1.png
[20160906164335227]: /images/20220411/153da46a79c54f6d810a6d75512d193c.png
[http_blog.csdn.net_smartxxyx_article_details_9275177]: http://blog.csdn.net/smartxxyx/article/details/9275177
[http_blog.csdn.net_smartxxyx_article_details_9293665]: http://blog.csdn.net/smartxxyx/article/details/9293665/
[http_dec3.jlu.edu.cn_webcourse_t000048_yun_ch7_04.htm]: http://dec3.jlu.edu.cn/webcourse/t000048/yun/ch7_04.htm
[20160805162827934]: /images/20220411/85acd1575df740e5a13feb201fc7a671.png
[20160805162844330]: /images/20220411/66318ef28280488f8215955ad9981100.png