Ford-Fulkerson算法正确性证明

作者: 1m0nster | 来源:发表于2019-09-29 14:06 被阅读0次

Ford-Fulkerson算法正确性证明
网络流——Ford-Fulkerson 算法
大数据算法系列14:流网络
Network Flow - Max Flow, Min Cut
最大流问题和Edmonds-Karp算法
算法的正确性证明方法一: 循环不变量
Kruskal算法——正确性证明
[图论]Dijstra 算法的正确性证明
RSA算法过程以及正确性证明
算法的正确性证明方法二: 结构归纳法

问题描述

图论中有一类重要的问题就是流量问题。求一个流网络的最大流量。那么可以用的方法有很多，比较经典的是FF(Ford-Fulkerson)算法。本文主要描述FF算法正确性的证明。涉及到的知识点：

流网络
Fold-Fulkerson算法
割
最大流-最小割定理

其中我们用最大流-最小割定理来证明FF算法的正确性

预备知识

流网络

一个流网络的定义如下：

流网络 $G=(V, E)$ 是一个有向图。具有如下属性：

每条边 $(u,v) \in E$ 有一个非负的容量值 $c(u, v) \ge 0$
如果 $(u,v) \in E$ ，那么 $(v,u) \notin E$
如果 $(v,u) \notin E$ ，则有 $c(u,v) = 0$
不允许有自循环

流网络中有两个重要的顶点 $s,t \in V$ ，其中s叫做源点（source），t叫做汇点（sink）。流网络中的流是从源地点到汇点。流网络中的所有流都从源点出发，然后最终都流入汇点。

如图就是一个流网络的示意图：

流网络示意图

流

网络G的流是一个如下的一个函数：

$f: V \times V \rightarrow R$

流具有如下性质：

容量限制：

$f(u,v) \le c(u,v) for \space all \space u,v \in V$

也就是说，一个流的值是不能大于该流的容量
流量守恒：

$\sum_{v \in V}f(u,v) = \sum_{v \in V}f(v,u)，\forall u \in {V-\{s,t\}}$
也就是说，对于任意的非s，非t顶点，从这个顶点流出的流和流入的流是相等的

并且如果 $(u,v) \notin E, \space f(u,v) = 0$

流的值

一个流的值用 $\vert f \vert$ 表示

$|f| = \sum_{v \in V}f(s, v) - \sum_{v \in V}f(v,s)$
表示从 $s$ 流出的所有值减去流入 $s$ 的所有值

割

定义

我们定义一个流网络的割（cut）为：

$(S,T)$ 其中 $S \cap T = \emptyset，S \cup T = V$ $s \in S, t \in T$

就是将一个图分割为两个不相交的集合。s在其中一个集合中，t在另外一个集合中，并且两个集合中的点是不相连的

我们引入一些网络流割的属性：

割的净流量

$f(S, T) = \sum_{u \in S}\sum_{v \in T}f(u,v) - \sum_{u \in S}\sum_{v \in T}f(v,u)$

割的容量

$c(S, T) = \sum_{u \in S}\sum_{v \in T}c(u,v)$

证明

为了证明FF的正确性，我们需要引入一个引理来辅助证明过程

引理1

设 $f$ 为流网络中的一个流，横跨任何切割的净流量都相同，都为 $|f|$ ，即流的值。即证明 $|f| = f(S,T)$

证明引理1:

证明有两种方式，一种是严格的数学证明，另外一种是直观上的感受，如果对于数学证明没有兴趣的话，那么可以直接去看直观上的证明。

数学证明

对于流量守恒特性，我们有： $\forall u \in V - \{s,t\}$ ， $\sum_{v \in V}f(u,v) - \sum_{v \in V}f(v,u) = 0$

根据流的值的定义：

$|f| = \sum_{v \in V}f(s,v) - \sum_{v \in V}f(v,s)$ ，将上面的式子针对每一个 $u \in S - \{s\}$ 相加得到

$|f| = \sum_{v \in V}f(s,v) - \sum_{v \in V}f(v,s) + \sum_{u \in S-\{s\}}(\sum_{v \in V}f(u,v) - \sum_{v \in V}f(v,u))$

$|f| = \sum_{v \in V}f(s,v) - \sum_{v \in V}f(v,s) + \sum_{u \in S-\{s\}}\sum_{v \in V}f(u,v) - \sum_{u \in S-\{s\}}\sum_{v \in V}f(v,u)$

$|f| = \sum_{v \in V}(f(s,v) + \sum_{u \in S-\{s\}}f(u,v)) - \sum_{v \in V}(f(v,u) + \sum_{u \in S-\{s\}}f(v,u))$

$|f| = \sum_{v \in V}\sum_{u \in S}f(u,v) - \sum_{v \in V}\sum_{u \in S}f(v,u)$

$|f| = \sum_{v\in V-S}\sum_{u \in S}f(u,v) + \sum_{v\in S}\sum_{u\in S}f(u,v) - (\sum_{v\in V-S}\sum_{u\in S}f(v,u) + \sum_{v\in S}\sum_{u\in S}f(v,u))$

$|f| = (\sum_{v\in T}\sum_{u \in S}f(u,v) - \sum_{v\in T}\sum_{u\in S}f(v,u)) +( \sum_{v\in S}\sum_{u\in S}f(u,v) - \sum_{v\in S}\sum_{u\in S}f(v,u))$

我们可以看到，这个等式前面括号的一部分就是 $f(S,T)$ ，后面的一部分根据流量守恒知道为0

因此

$|f| = f(S,T) + 0 = f(S,T)$

证毕。

直观证明

根据流的定义，我们知道一个流网络 $G$ 的流 $f$ 的值是所有从 $s$ 流出的流的和，减去所有进入 $s$ 的流。那么从 $s$ 出去的流，最后都会进入到 $t$ 中。而我们任意的一个切割，都将这个网络分成了两个不相连的部分， $s$ 位于一部分 $t$ 位于一部分。如果流想要从 $s$ 到 $t$ 的话，那么必须经过这个切割。而流网络是没有损耗的，因此经过这个切割的流的值，一定等于从 $s$ 中流出的值和流入值的差，也就是整个网络的流的值。即 $|f| = f(S,T)$ 证毕。

推论1

有了引理1，我们就可以有推论1：网络的流小于或等于网络任意切割 $(S,T)$ 的切割容量，即 $f(S,T) \le c(S, T) ,\forall c(S,T)$

证明推论1:

根据引理1，我们知道。网络的流等于任意横跨切割的流，而再根据容量限制我们知道横跨任意切割的流小于等于切割的容量。传递过来，我们就有，网络的流小鱼等于任意切割的容量，即 $f(S,T) \le c(S,T) \forall c(S,T)$

证毕。

定理1

有了推论1，我们就可以很明显的得出。一个网络的最大流的值等于一个最小切割的容量。即最大流-最小切割定理。

最大流-最小割

设 $f$ 为流网络 $G=(V,E)$ 中的一个流，该流网络的源点为 $s$ ，汇点为 $t$ ，则下面的条件是等价的：

(1) $f$ 是 $G$ 的一个最大流
(2) 残存网络 $G_f$ 不包括任何增广路径
(3) $|f|=c(S,T)$ ，其中 $(S,T)$ 是流网络 $G$ 的某个切割

我们可以看到，FF算法在可以终止的前提下，终止的条件是（2），我们假设在（2）的前提下有（1），也就是 $(2) \Rightarrow (1)$ 我们就是需要证明 $(2) \Rightarrow (1)$

$(1) \Rightarrow (2)$ 我们使用反证法来证明。如果一个 $f$ 是最大流，但是 $G_f$ 中存在增广路径，那么根据FF算法就可以增加网络的流的大小，那么这个流就不是最大流了。与我们最初的假设矛盾，因此 $(1)\Rightarrow(2)$ 是正确的

$(2)\Rightarrow(3)$ $G_f$ 中不存在增广网络，那么我们就可以将 $G_f$ 切割为 $(S,T)$ 定义 $S=\{v \in V| 在G_f中存在一条s到v的路径\} \space T = V - S$ ，那么显然有 $s \in S, t \in T$ 。我们对于 $\forall u \in S, \forall v \in T$ 会有下面两个推论：

$f(u,v) = c(u,v)$ ；因为，如果 $f(u,v) \ne c（u,v）$ 那么在 $G_f$ 中必然有 $s$ 到 $v$ 的通路，那么 $v$ 跟据定义就属于 $S$ 中，与 $v \in T$ 矛盾，因此 $f(u,v) \in c(u,v) \forall u \in S, \forall v \in T$
$f(v,u) = 0$ ；因为如果 $(v,u) \notin E$ 那么显然 $f(v,u) = 0$ ，如果 $(v,u) \in E$ 并且 $f(v,u) \ne 0$ 那么在残存网络 $G_f$ 中就存在一条 $(u,v)$ 的路径，那么 $v \in S$ ，这于 $v \in T$ 矛盾。因此 $f(v,u) = 0$

有上面的两个推论，我们结合跨切割的流的定义有：

$f(S,T) = \sum_{u \in S}\sum_{v \in T}f(u,v) - \sum_{u \in S}\sum_{v \in T}f(v,u)$

$f(S,T) = \sum_{u \in S}\sum_{v \in T}f(u,v) - 0$

$f(S,T) = \sum_{u \in S}\sum_{v \in T}c(u,v) = c(S,T)$

根据引理1，我们有

$|f| = f(S,T) = c(S, T)$

因此 $(2) \Rightarrow (3)$ 正确

$(3) \Rightarrow (1)$ 根据推论1，我们知道 $|f| \le c(S,T)$ ，而 $(2)$ 中的等于前提，即 $|f| = c(S,T)$ 即表明了这是一个最大流。因此 $(3) \Rightarrow (1)$ 是正确的

经过上面的证明我们可以看到， $(2)$ 是一个独立的条件，那么就会有 $(2) \Rightarrow (3) \Rightarrow (1)$ 这样的证明链条，也就有 $(2) \Rightarrow (1)$ 也就是我们要证明的结论，即FF算法的正确性--在没有残差网络的情况下得到的流一定是最大流。事实上 $(1)\Longleftrightarrow (2) \space (1)、(2)$ 互为充要条件。

证毕。

Ford-Fulkerson算法正确性证明
问题描述图论中有一类重要的问题就是流量问题。求一个流网络的最大流量。那么可以用的方法有很多，比较经典的是FF(F...
网络流——Ford-Fulkerson 算法
最大流算法 Ford-Fulkerson 算法是用于计算容量网络 < V,E,c,s,t> 的最大流的算法。该算法...
大数据算法系列14:流网络
一. 流网络定义二. Ford-Fulkerson算法 FF算法的核心在于找增广路。何谓增广路？例如上图中我首先...
Network Flow - Max Flow, Min Cut
0 Ford-Fulkerson for Max Flow Min Cut Ford-Fulkerson for ...
最大流问题和Edmonds-Karp算法
内容概要：网络流与最大流 Ford-Fulkerson思想 Edmonds-Karp算法棒球比赛问题网络流和...
算法的正确性证明方法一: 循环不变量
在之前的一篇文章里写到算法的正确性的概念以及它的作用，下面就来写写循环不变量在算法的正确性证明中的用法。循环不变...
Kruskal算法——正确性证明
Kruskal算法可以帮助找到最小生成树(MST). 所谓的最小生成树一种简单的理解是在给定的约束条件下, 使目标...
[图论]Dijstra 算法的正确性证明
NOTE - dijstra算法的正确性非常依赖于边权值的非负。原因是: 设V为所有点集， S为确定最短路径的点...
RSA算法过程以及正确性证明
一、生成公钥、私钥寻找两个不相同的大质数随意寻找两个不相同的大质数，计算求 N 的欧拉函数值欧拉函数的定义：是...
算法的正确性证明方法二: 结构归纳法
在上一篇文章中谈到在使用循环的算法中，可以利用循环不变量证明算法的正确性，那如果是使用递归的算法呢。递归的算法在...

Ford-Fulkerson算法正确性证明

问题描述

预备知识

流网络

流

流的值

割

定义

割的净流量

割的容量

证明

引理1

证明引理1:

数学证明

直观证明

推论1

定理1

最大流-最小割

相关文章

Ford-Fulkerson算法正确性证明

网络流——Ford-Fulkerson 算法

大数据算法系列14:流网络

Network Flow - Max Flow, Min Cut

最大流问题和Edmonds-Karp算法

算法的正确性证明方法一: 循环不变量

Kruskal算法——正确性证明

[图论]Dijstra 算法的正确性证明

RSA算法过程以及正确性证明

算法的正确性证明方法二: 结构归纳法

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读