文档章节

最大流问题

fengsehng
 fengsehng
发布于 2016/11/09 09:11
字数 1117
阅读 7
收藏 0

举例描述

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

这里写图片描述

公式描述

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

那么最大流就可以表示为:
这里写图片描述

Ford-Fulkerson解法介绍

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

Ford-Fulkerson思想

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

增广路径

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

这里写图片描述

残留网络

顾名思义,残留网络是指给定网络和一个流,其对应还可以容纳的流组成的网络。具体说来,就是假定一个网络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个单位流量的压回去的能力。

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

这里写图片描述

对应的残留网络:

这里写图片描述

求解步骤举例

1.获得残留网络

2.穷举所有的增广路径

如下图所示:

这里写图片描述

计算最大流的标号法

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

这里写图片描述
上图
若给一个可行流{},称网络中 = 的弧为饱和弧,称 <的弧为非饱和弧,称 =0的弧为零流弧,称 >0的弧为非零流弧。
增广链:设{}是可行流, μ是 到 的一条链,若μ满足下列条件,则称μ为关于 f 的增广链。(注意: f ={})
1°对于任何( ,)∈μ+,0≤ < (前向弧为非饱和弧)
2°对于任何( ,)∈μ-,0 <≤ (后向弧为非零流弧)

博客参考:

smartxxyx的两篇博客:
http://blog.csdn.net/smartxxyx/article/details/9275177
http://blog.csdn.net/smartxxyx/article/details/9293665/
以及:
http://dec3.jlu.edu.cn/webcourse/t000048/yun/ch7_04.htm

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

这里写图片描述

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

微信订阅号二维码如下:

这里写图片描述

© 著作权归作者所有

共有 人打赏支持
fengsehng
粉丝 4
博文 284
码字总数 214494
作品 0
朝阳
程序员
Ford-Fulkerson 方法——最大流问题

最大流&&最小费用最大流&&最大二分匹配 Python 源码:https://github.com/edisonleolhl/DataStructure-Algorithm/blob/master/Graph/MaxFlow 最大流问题 比喻:有一个自来水管道运输系统,起...

廖少少
2017/09/08
0
0
用Ford和Fulkerson的增广路径算法,解决网络中的最大流(flow)以及其衍生问题。

管道网络中每条边的最大通过能力(容量)是有限的,实际流量不超过容量。 最大流问题(maximum flow problem),一种组合最优化问题,就是要讨论如何充分利用装置的能力,使得运输的流量最大,...

linuxer
2017/11/11
0
0
网络流——最大流问题例题

许多应用都包含了流量问题,例如,公路系统中有车辆流,控制系统中有信息流,供水系统中有水流,金融系统中有现金流等等。下面不讲原理、不讲概念,以一个例题,用通俗的语言,来说明最大流的...

x113773
2017/12/29
0
0
ZOJ ~ 3229 ~ Shoot the Bullet (有源汇上下界最大流)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/ZscDst/article/details/82695507 题意 你要给一些小姐姐拍照。第一行输入N,M表示总共要拍N天,共有M个小姐姐...

张松超
09/14
0
0
洛谷 ~ P3254 ~ 圆桌问题 (二分图多重匹配 + 方案输出)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/ZscDst/article/details/81990064 二分图多重匹配问题,建图方式如下: ①超级源点S往所有X集合的点建边,边权...

张松超
08/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Bash各类扩展详解

Bash各类扩展详解 Bash中主要包括大括号扩展、波浪号扩展、变量扩展、子命令扩展、文件名扩展和算数扩展。这些扩展组合在一起为Bash带来了极大的易用性。掌握这些扩展的用法和功能,能够为B...

小陶小陶
今天
1
0
EventBus原理深度解析

一、问题描述 在工作中,经常会遇见使用异步的方式来发送事件,或者触发另外一个动作:经常用到的框架是MQ(分布式方式通知)。如果是同一个jvm里面通知的话,就可以使用EventBus。由于Event...

yangjianzhou
今天
5
0
OpenCV图像处理实例:libuv+cvui显示摄像头视频

#include <iostream>#include <opencv2/opencv.hpp>#define CVUI_IMPLEMENTATION#include <cvui.h>extern "C"{#include <uv.h>}using namespace std;#define WINDOW_NAM......

IOTService
今天
3
0
openJDK之JDK9的String

1.openJDK8的String 先来看下openJDK8的String的底层,如下图1.1所示: 图1.1 底层上使用的是char[],即char数组 每个char占16个bit,Character.SIZE的值是16。 2.openJDK9中的String 图2.1...

克虏伯
今天
3
0
UEFI 模式下如何安装 Ubuntu 16.04

作者:知乎用户 链接:https://www.zhihu.com/question/52092661/answer/259583475 来源:知乎 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 针对UEFI模式下安装U...

寻知者
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部