【算法】最大流

概述

• 在最大流问题中，我们希望在不违反任何容量限制的情况下，计算出从源节点运送物料到汇点的最大速率

流网络

流网络和流

• 流网络是一个有向图
• 流网络有源结点和汇点，所有的流量都由源结点出发，流向汇点
• 每条边有一个非负的容量值 c，代表边上能通过的最大流量
• 边的流 f，代表整个流网络经过最大化计算后，边上实际通过的流量
• 容量限制：f < c，即一条边上的实际流量不能超过其最大流量
• 流量守恒：进入一个结点的流必须与流出此结点的流相等
• 整个网络的流，定义为由源结点出发的流的总和

流的一个例子

• 举了一个途径多个城市的货运问题作为流网络的例子

使用反平行边来模拟问题

• 反平行边是指网络中互为反向的两条边
• 实际问题中是存在反平行边的，而流网络的定义中禁止反平行边的存在，那么我们可以通过将反平行边中的一条分解为两段（中间插入一个新结点）的方法消除反平行边，两段新的边容量设置为与原来的边容量相等
• 可以证明上述转换后的网络与原网络等价（等价的意思我理解为，计算出的最大流相等）

具有多个源结点和多个汇点的网络

• 此种问题可以转换为单源结点单汇点的问题，方法是增加超级源结点，增加超级源结点到所有源结点的边，并将其容量设置为无穷大，同样地，增加超级汇点，增加所有汇点到超级汇点的边，并将其容量设置为无穷大
• 可以证明上述转换后的网络与原网络等价

Ford-Fulkerson 方法

• 几个重要概念：残存网络、增广路径、切割
• 最大流问题的思路大致为：在残存网络中寻找增广路径，操作增广路径的边以增加流的值，迭代进行操作，直到残存网络中不再存在增广路径为止。

残存网络

• 残存网络是由那些仍有空间对流量进行调整的边构成，通俗的解释一下调整，意思是对一条边上的流量增大或减小（减小或许有助于整个网络的流增加）
• 残存网络可能包含原图中不存在的边，举例说明：有一条边 u ~ v 的容量为 c，当前的流量为 f（假设 0 < f < c），那么相应的残存网络中会有两条相关的边，一条是 u ~ v，容量为 c - f，另一条边是 v ~ u，容量为 f。这两条边是反平行边。
• 将残存网络也当做一个流网络来处理（当然得解决其中的反平行边问题），计算出残存网络的流 f'，将 f' 称为原网络的流 f 的递增。将 f' 叠加到 f 上，即可得到一个更大的流。那么再重新计算残存网络，迭代的增加 f，直到最后的残存网络中的 f' 等于 0 为止。
• 引理 26.1 给出了将 f' 叠加到 f 上的理论依据，可以证明叠加后的流依然是原图 G 的一个流，且其值为 f + f'

增广路径

• 增广路径是残存网络中一条由源结点 s 到汇点 t 的简单路径
• 增广路径的残存容量为其路径上所有边的残存容量的最小值
• 引理 26.2 形式化的描述了增广路径的流表现（以流的形式描述增广路径），即路径上边的流量皆为路径的残存容量，其余边的流量为 0
• 推论 26.3 指出可以将增广路径的流叠加到原来流上形成一个更接近最大流的流

流网络的切割

• 一个切割定义为两个结点集 S（包含 s）和 T（包含 t）
• 横跨切割的净流量 f 定义为，所有 S -> T 的边的流量，减去所有 T -> S 的边的流量
• 切割的容量定义为所有 S -> T 的边的容量之和
• 引理 26.4 指出了横跨切割的净流量等于网络的流 f
• 推论 26.5 指出任意流 f 不能超过任意切割的容量
• 定理 26.6 最大流最小切割定理，指出网络的最大流等于某个切割的容量（最小切割）

基本的 Ford-Fulkerson 算法

• 算法的基本思路如上文所述：迭代的寻找增广路径，将增广路径叠加到原来的流上形成一个更大的流，直到残存网络中不存在增广路径为止
• 没有给出寻找增广路径的方法，算法中一句话带过了。个人思考可以对残存网络使用深度优先遍历来寻找增广路径。

Ford-Fulkerson 算法的分析

• 算法的运行时间取决于如何寻找增广路径
• 一个基本的方法是，用深度优先搜索或广度优先搜索找到一条路径，然后路径上的流量都设为 1，以这条路径作为增广路径，如此操作算法的运行时间为 O(E|f|)
• 这种操作在最大流 f 的值较小时性能很好，f 数值比较大就不够理想了

Edmonds-Karp 算法

• 算法的核心思路是通过广度优先搜索寻找增广路径，与上一小段不同的是，不再将路径上的流量设为 1，而是寻找路径上能容纳的最大的流量，将其作为路径的流量
• 引理 26.7 残存网络中的最短路径距离随着每次流量的递增而单调递增。单纯的理解这个引理非常疑惑，让人怀疑这和流 & 增广路径有什么关系。通俗的理解，这里想表达的是，通过 Edmonds-Karp 算法的执行找到一条增广路径（最短路径）后，设置其流量并叠加到图中，新的残存网络中此增广路径必定不存在了，再次寻找的最短路径一定更长。原因是增广路径的流量值设置为路径的最大流量，这样叠加后的图的残存网络一定有某条边消失（即下文中的关建边）
• 定理 26.8 给出了算法执行的流量递增操作的总次数为 O(VE)
• Edmonds-Karp 算法的总运行时间为 O(VE²)

最大二分匹配

• 这一节的内容是利用最大流算法解决图的最大二分匹配问题

最大二分匹配问题

• 首先需要明确什么是最大二分匹配问题
• 二分图是指，将一个图的结点集划分为 L 和 R 两部分，且满足边集合 E 中的所有边都横跨 L 和 R
• 匹配是指，E 的一个子集 M，对于所有结点 v，满足 M 中最多有一条边与结点 v 相连
• 最大匹配是指，拥有边数量最多的匹配（或者称最大基数的匹配）
• 那么最大二分匹配问题可以通俗的描述为，在一个二分图中，寻找一个最大匹配的问题

寻找最大二分匹配

• 这一段的主题是利用最大流算法来解决最大二分匹配问题
• 首先是将二分图转换成一个新的流网络，再来证明此流网络的最大流即是二分图的最大匹配
• 转换方法为，增加源结点 s 和汇点 t，增加 s 到 L 所有结点的边，增加 R 所有结点到 t 的边，并将所有边的容量设置为 1
• 引理 26.9 指出了二分图的一个匹配对应流网络的一个流（流的值为整数），匹配的基数与流的值相等
• 定理 26.10 指出如果边的容量都为整数，那么最大流算法生成的最大流的值也是整数值。这里解决了引理 26.9 中要求流的值为整数的问题
• 推论 26.11 指出二分图的最大匹配基数等于对应的流网络中某一最大流的值
• 至此，就可以通过将二分图转换为流网络，计算流网络的最大流，推出二分图的最大匹配
• 方法的运行时间为 O(VE)

推送-重贴标签算法

• 预流是一种特殊的流（不满足流量守恒），进入一个结点的流可以超过流出该结点的流，进入与流出的差额成为超额流
• 推送、重贴标签是两种基本操作
• 本算法的思路是，先在图上建立预流，然后通过推送和重贴标签的反复执行，最终得到一个最大流

直观思想

• 将图设想为一个由给定容量的管道组成的系统，其中的结点为高度不同的蓄水池，流只能由较高或等高的结点流向另一个结点

基本操作

• 基本操作即，推送操作（从一个结点将超额流推送到一个邻结点）、重贴标签操作（改变结点的高度）
• 高度函数 h 的定义为，对所有的边（u，v），有 h(u)<=h(v)+1
• 引理 26.12 指出，残存网络中的边其高度满足上述函数 h 的定义

推送操作

• 推送操作的适用条件为，u 是一个溢出结点，边（u，v）的残存容量大于 0，并且 h(u)=h(v)+1
• 推送操作的原理为，若边（u，v）满足适用条件，则为其增加一个流量，增加幅度为取结点 u 的超额流与边（u，v）的残存容量的较小者
• 饱和推送，意思是推送操作后，边的残存容量变为 0
• 引理 26.13 指出，对边（u，v）进行一个非饱和推送后，u 将不再溢出

重贴标签操作

• 重贴标签操作的适用条件为，结点 u 溢出，且 u 的高度不高于其所有相邻结点（有边从 u 出发到达的结点）
• 重贴标签的做法是，对满足适用条件的结点 u，将 u 的高度变为，其相邻结点中的最小高度加 1

通用算法

• 首先给出建立预流的方法，将所有结点的高度和超额流初始化为零，所有边的流量初始化为零，再将所有由 s 出发的边都充满流，这样 s 的邻结点的超额流为 s 到该结点的边的容量
• 通用算法的过程为，初始化预流，对满足上述两个操作条件的边和结点迭代执行上述两个操作，直到没有满足条件的边和结点为止
• 引理 26.14 指出，如果 u 是一个溢出结点，则要么可以对其执行推送操作，要么可以执行重贴标签操作

推送-重贴标签方法的正确性

• 引理 26.15 指出，执行算法的过程中，结点高度从来不会降低
• 引理 26.16 指出，执行算法的过程中，结点的高度 h 始终能维持高度函数的性质
• 引理 26.17 指出，执行算法的过程中，残存网络中不存在一条从 s 到 t 的路径。这里是与 Edmonds-Karp 算法明显不同的地方，Edmonds-Karp 算法依赖于从残存网络中寻找增广路径（s 到 t 的路径）来完成算法。
• 定理 26.18 指出，在 Generic-Push-Relabel 算法终止时，预留 f 即为一个最大流。证明方法是用循环不变式证明法，很经典。

推送-重贴标签方法的分析

• 通过给出执行操作的次数界，来证明算法确实会终止
• 引理 26.19 指出，对于任意溢出结点 x，残存网络中存在一条从 x 到 s 的简单路径
• 引理 26.20 指出，算法执行过程中，结点的高度 h 小于等于 2V-1，显而易见
• 推论 26.21 给出了重贴标签操作次数的界为，2V²
• 引理 26.22 给出了饱和推送操作次数的界为，2VE
• 引理 26.23 给出了非饱和推送操作次数的上界为，4V²(V+E)
• 定理 26.24 指出，Generic-Push-Relabel 算法执行基本操作的总次数为 O(V²E)
• 推论 26.25 指出，可以证明对于任意流网络 G，都存在一种通用 Generic-Push-Relabel 算法，其运行时间为 O(V²E)

前置重贴标签算法

• 释放操作：对一个结点进行释放是指，对该结点进行推送或者重贴标签操作，直到该结点不再有正值的超额流量为止
• 前置：含义是在释放操作时，可能会对结点进行重贴标签，在重贴标签后将该结点移动到链表的最前面
• 基本思路：以邻接链表的形式存放结点，从头到尾对链表进行扫描，每次选一个结点进行释放，释放可能引起前置，若有前置，则以前置后的下一个结点继续扫描，直至扫描完整个列表

许可边和网络

• 许可边是指，残存容量大于零，且满足 h(u)=h(v)+1 的边
• 由许可边组成的图成为许可网络
• 引理 26.26 指出，许可网络是无环的
• 引理 26.27 指出，推送操作不会创建新的许可边，但可能会使推送经过的边变为非许可边（饱和推送时）
• 引理 26.28 指出，重贴标签操作后，至少存在一条从 u 出发的许可边，但不存在进入 u 的许可边

邻接链表

• 本节详细说明了如何以邻接链表的方式存储结点网络，并维护额外的一些属性

释放溢出结点

• 本节详细说明了释放操作的过程
• 基本思路为，选择一个结点 u 进行释放操作，取 u 的邻接结点链表进行遍历，如果 u 的邻接结点 v 满足推送操作的条件则执行推送操作，不满足则继续遍历，遍历到链表尾部则对 u 执行重贴标签操作。重复以上过程直至 u 不再有超额流。
• 通俗的说明一下就是，尽可能的将 u 的超额流推送给邻接结点，若无法推送则通过对 u 重贴标签增加其高度，再进行推送
• 引理 26.29 证明了释放操作中进行的推送和重贴标签是合乎条件的

前置重贴标签算法

• 算法的基本思路上文已经给出
• 具体步骤是，初始化预流，初始化邻接链表及其属性，对结点的主链表进行遍历，依次对每个结点执行释放操作。执行释放操作后，如果发现其中执行了重贴标签（通过记录高度进行比较），则将该结点前置。前置后继续从该结点的下一个结点（也就是当前主列表中的第二个结点）继续遍历，直至遍历完毕
• 书中给出了算法的证明，证明了算法执行后确实得到了一个最大流

前置重贴标签算法的分析

• 定理 26.30 指出，前置重贴标签算法的运行时间为 O(V³)