计算机科学

首页 > 计算机科学

最大流最小割定理

2018-08-27 10:45:55     所属分类:组合优化

在最优化理论中,最大流最小割定理提供了对于一个网络流,从源点到目标点的最大的流量等于最小割的每一条边的和。即对于一个如果移除其中任何一边就会断开源点和目标点的边的集合的边的容量的总和。

最大流最小割定理是线性规划中的对偶问题的一种特殊情况,并且可以用来推导Menger定理和König–Egerváry定理。[1]

目录

  • 1 定义
    • 1.1 最大流
    • 1.2 最小割
  • 2 线性规划公式
  • 3 举例
  • 4 应用
    • 4.1 广义最大流最小割定理
    • 4.2 Menger 定理
    • 4.3 计划选择问题
    • 4.4 影像分割问题
  • 5 历史
  • 6 证明
  • 7 参见
  • 8 参考文献

定义

G = (V, E)为一个网络(有向图),并且N有一个起源点 s 和一个超汇点 t,代表所有 s 是所有流的源头,t 是所有流的终点。

最大流

定义: 一条边的容量是一个映射c : ER+,记做 cuv 或者 c(u, v),代表着能通过这条边的最大的流量。

定义: 一个是一个映射f : ER+,记做 fuv 或者 f (u, v)。每一条流有以下两个限定条件:

1. 流量限制:
2. 流量守恒:

定义: 流的流量的定义是

s 为 N 的源点,代表着从源点流向目标点的流量。

最大流问题:计算 | f | 的最大值。即从 s 到 t 的最大流量。

最小割

定义:一个 s-t 割 C = (S, T) 是一种 V 的划分使得 sS, tTC 割集是集合

因此如果 C 的割集是空集合,则 | f | = 0.

定义: 一个s-t割的容量

其中 如果 并且 , 0 反之。

最小 s-t 割问题: 计算 c(S, T) 的最小值。即找到 S 和 T 使 s-t 割的容量达到它的最小值。

线性规划公式

最大流最小割问题可以被看做为一对线性规划对偶问题。[2]

最大流问题

最小割问题

变数:

变数:

的最大值

的最小值

满足

满足

注意到在给定的 s-t 割  中,如果 那么 并且 0 反之。 所以 应该等于 1 并且 应该等于0。由线性规划中的强对偶定理推得最大流最小割问题中的等式,也就是说如果原问题有一个最优解 x*,则对应问题也有一个最优解 y* ,并且两个解相等。

举例

一个流量等于s-t 割的容量的流网络

上图是一个网络,上有流量为 7 的流。令 S 集合和 T 集合分别包含所有白色和灰色的点, 从而形成了一个割集包含图中虚线的 s-t 割,并且其容量为 7,与流量相同。故由大流最小割定理知,前述的流与 s-t 割皆达到流量及容量的极值。

应用

广义最大流最小割定理

额外规定映射 为点的容量,记做 c(v),使得一个流 f 不只要满足边的流量限制与流量守恒,还要满足点的流量限制,即

换句话说,流过 v 点的总流量不能超过 v 的容量 c(v)。一个 s-t 割 的定义为一个包含一些点和边的集合,满足与任一条由 s 到 t 的路径皆不互斥。并且 s-t 割的容量 定义成所有点和边的容量总和。

在此定义之下,广义最大流最小割定理的叙仍为流量的最大值等于所有 s-t 割的容量最小值。

Menger 定理

不共边路径问题为给定无向图 及两顶点 s、t,求从 s 到 t 彼此没有共同边的路径数量的最大值。

Menger 定理的叙述为从 s 到 t 彼此没有共同边的路径数量的最大值等于在所有 G 的 s-t 割(以原本的定义)中,顶点分别在不同集合的边数的最小值。

计划选择问题

计划选择问题的网络型态

计划选择问题叙述如下:当下有 n 个计划 可以被实施、m 种设备 可以被购买,要执行计划必须拥有该计划要求的设备,执行计划 可获得 的收益,但购买设备 要支付 的费用。如何选择执行计划并购买所需设备以获得净利的最大值?

设 P 为被执行的计划的集合,Q 为所购买的设备,则问题变成求最大值

注意到 与 P、Q 的选择无关,故只需求后两项和的最小值,即

现在考虑一个网络,起源点 s 连接到 n 个点 ,边的容量分别为 ,超汇点 t 连接到 m 个点 ,边的容量分别为 ,若执行任务 需购买设备 ,则在 之间连上一条容量为无限大的边,若不需购买设备,则不连上边。则 对应到一个 s-t 割的容量,其中的两个集合是要执行的计划与要购买的设备和它的余集,也就是

在此,。于是,原问题转成求该图的最大流问题,并且可以借由各种算法求得其极值。

以下给出一个计划选择问题的例子,右图是该问题对应到的网络。

计划收入 r(pi)

设备价格 c(qj)

备注
1 100 200

执行计划 p1 须购买设备 q1q2

2 200 100

执行计划 p2 须购买设备 q2

3 150 50

执行计划 p3 须购买设备 q3

该网络的最小 s-t 割是选择计划 p2p3 与设备 q2q3,容量为 250。三个计划的总收益是 450,因此最大净利为 450 − 250 = 200。

以上解法可以理解为将计划所给予的收益流过所需设备,如果无法流满设备至 t 的边,代表执行计划不合成本,最小割将选择穿过 s 到计划的边而非穿过设备到 t 的边。

影像分割问题

Each black node denotes a pixel.

设原图有 n 像素,想要把该图分割为前景和背景,并且将 i 像素归类为前景有效益  fi,归类为背景有效益  bi,但是若 i、j 像素相邻且被归类为不同块,则会减少 pij 的效益。求将该图分割为前后景的最有效益方法。

令 P 为前景的集合,Q 为背景的集合,于是问题转化成求最大值

因为  fi bi 的总合是与 P、Q的选取无关,因此等价于求以下最小值

以上的最小值问题可以被描述为一个网络的最小割问题,其中该网络如右图,以橘点为起源点;紫点为超汇点。各个像素被描述为网络的顶点,起源点至第 i 个像素连上一条容量为  fi 的有向边;第 i 个像素至超汇点连上一条容量为 bi 的有向边。相邻的像素 i、j 之间连上来回两条容量为 pij 的有像边。则一个 s-t 割代表一种将部分像素归类为前景 P、其余归类为背景 Q 的安排。

历史

最大流最小割问题最早在1956年被P. Elias, A. Feinstein,和 C.E. Shannon 证明[3], 并且L.R. Ford, Jr. 和 D.R. Fulkerson 也在同年证明了该定理[3]

证明

同之前的设定,G = (V, E) 是一个网络(有向图) ,s 点和 t 点分别为 G 的起源点和超汇点。

将所有流考虑成一个欧式空间的有界闭子集,满足流量限制与流量守恒,而流量是一个连续函数,因此有极大值 |f| 。

设 f 达到最大流,令 (Gf ) 是 f 的残留网络,定义

  1. A:在 (Gf ) 中可以从 s 出发到达的点
  2. Ac:A 以外的点,即 V − A

换句话说,v∈A 当且仅当 s 可以流出更多流量到 v。

声称 ,其中该 s-t 割的容量定义为

.

由于 的大小等于所有流出集合 A 的流量总和减所有流入集合 A 的流量总和,故 ,并且等号成立当且仅当

  • 所有从 A 流向 Ac 的边流量均已达饱和。
  • 所有从 Ac 流向 A 的边流量均为 0。

我们用反证法分别证明以上两点:

  • 假设存在从 A 流向 Ac 的边 并未达到饱和,即 。因此,可以从 x 流更的流量到 y,(x,y) 是 Gf 的一条边。由 x∈A 知 Gf 图中有一条中的路径从 s 到 x,其中只经过 A 中的的点, 所以 y∈A,产生矛盾。是故所有从 A 流向 Ac 的边流量均已达饱和。
  • 假设存在从 Ac 流向 A 的边 其流量不为 0,即 。因此,可以从 y 流更的流量到 x,(x,y) 是 Gf 的一条边。由 x∈A 知 Gf 图中有一条中的路径从 s 到 x,其中只经过 A 中的的点, 所以 y∈A,产生矛盾。是故所有从 Ac 流向 A 的边流量均为 0。

于是,声称得证。

由于流量恒不超过容量,|f| 是容量的下界,所以 是容量的最小值,由声称知,最大流最小割定理得证。

参见

  • 线性规划
  • 最大流
  • 最小割
  • 网络流
  • Edmonds–Karp 算法
  • Ford–Fulkerson 算法
  • 近似最大流最小割定理

参考文献

  1. ^ Dantzig, G.B.; Fulkerson, D.R. On the max-flow min-cut theorem of networks (PDF). RAND corporation. 9 September 1964: 13 [10 January 2018]. 
  2. ^ Trevisan, Luca. Lecture 15 from CS261: Optimization (PDF). 
  3. ^ 3.0 3.1 P. Elias, A. Feinstein, and C. E. Shannon, A note on the maximum flow through a network, IRE. Transactions on Information Theory, 2, 4 (1956), 117–119
  1. Eugene Lawler. 4.5. Combinatorial Implications of Max-Flow Min-Cut Theorem, 4.6. Linear Programming Interpretation of Max-Flow Min-Cut Theorem. Combinatorial Optimization: Networks and Matroids. Dover. 2001: 117–120. ISBN 0-486-41453-1. 
  2. Christos H. Papadimitriou, Kenneth Steiglitz. 6.1 The Max-Flow, Min-Cut Theorem. Combinatorial Optimization: Algorithms and Complexity. Dover. 1998: 120–128. ISBN 0-486-40258-4. 
  3. Vijay V. Vazirani. 12. Introduction to LP-Duality. Approximation Algorithms. Springer. 2004: 93–100. ISBN 3-540-65367-8. 
版权声明:本文由北城百科网创作,转载请联系管理获取授权,未经容许转载必究。https://www.beichengjiu.com/computerscience/339756.html

相关推荐