Fizzydavid 的讲课内容

概念引入

网络图

对于有向图，定义其中的两个点分别为源点和汇点。中的边，定义其容量为，流量，满足

  1. 。
  2. 。
  3. ，其中。

注意：如果中同时存在和的边，我们可以拆点将其转化为不存在反平行边。实际上在实现的过程中大部分算法对于存在反平行边的也适用。只不过在本文描述的过程中我们只考虑不含反平行边的图。

流与割

对于一个流函数，定义其流量为。使得最大的流函数被称为最大流。

割是的一个划分，使得。割的容量定义为。最小化的割被称为最小割。

残量网络

残量定义为。

考虑流对应的残量。我们将的边与构成的子图称为残量网络。

最大流的残量网络中，不连通。

令为残量网络上出发能到达的点集，，则恰是最小割。

因此我们证明了最大流最小割定理。

对于任意最大流形成的残量网络，割是最小割的充要条件是对于任意割边有。

最大流的方案不唯一，因此不同的最大流对应的残量网络是不同的。不同最大流的残量网络可以用循环流相互转化（循环流不会影响最大流）。

对于残量函数，其上的最小割的充要条件：

  • ，。
  • ，有成立。

残量网络的 SQT 划分

对于任意一个最大流对应的残量网络，设出发能到达的点集是，设能到达的点的点集是，设表示既不在也不在中的点的点集。

首先，划分只和有关，与最大流的方案无关。也就是说这样的划分是唯一的。

证明

考虑的边，即割。首先一定有。如果割发生变化，一定伴随最大流的变化。而最大流是不变的，因此割是唯一的。

同理，割也是唯一的。

因此和集合是不变的，则也不变。

最小割的 2-SAT 模型

考虑原图上的边，我们要询问与最小割相关的问题。考虑建立 2-SAT 模型。

维护两种标记：。拥有标记记作。

表示一定在割的中，表示一定在中。

在残量网络上，对于任意结点，我们可以添加两种限制：

  • 若，则我们将能到达的点标记为。即。
  • 若，则我们将能到达的点标记为。即。

由于我们考虑的是 s-t 割，因此一定有。

要判断是否在最小割中，则我们令，然后加入上述限制，跑一个 2-SAT 看是否有解。如果一个结点被同时标记为就矛盾了，就无解。

应用

A1

判断最小割是否唯一。

最小割唯一等价于不存在未被标记的点。

A2

判断原图上是否可能在最小割中。

考虑其逆命题：不可能在最小割中。

我们强制，看 2-SAT 是否矛盾。如果矛盾，则说明不可能在最小割中。

出现矛盾，等价于：能到达，或者能到达。也就等价于到存在増广路。

从 2-SAT 角度思考问题与从网络流角度思考问题只是思路的不同，但实现可能是一样的。

A3

判断原图上是否一定在最小割中。

考虑其逆命题：存在一个最小割方案使得不在最小割中。

对于某个 2-SAT 解，如果有相同的标记，或者两者中存在没有标记的结点，则不在最小割中。

因此等价于：存在一个 2-SAT 解使得有相同的标记，或者两者中存在没有标记的结点。

我们先利用跑一次 2-SAT。若和都有了标记，就可以判断是否成立。

若或者存在未标记的点，那么这恰好就是个满足的 2-SAT 解。