Fizzydavid 的讲课内容

概念引入

网络图

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

  1. ,其中

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

流与割

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

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

残量网络

残量定义为

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

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

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

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

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

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

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

  • ,有成立。

残量网络的 SQT 划分

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

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

证明

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

同理,割也是唯一的。

因此集合是不变的,则也不变。

最小割的 2-SAT 模型

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

维护两种标记:拥有标记记作

表示一定在割中,表示一定在中。

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

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

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

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

应用

A1

判断最小割是否唯一。

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

A2

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

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

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

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

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

A3

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

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

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

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

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

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