网络流基础之最大权闭合图

Terms
¶

对于有向图 $G = (V, E)$ ，其中 $V$ 为 $G$ 的点集， $E$ 为 $G$ 的边集。

割集: 一个 $s - t$ 割 $[S, T]$ 是 $V$ 的一种划分，使得 $s \in S$ 、 $t \in T$
最小割: 一个 $s - t$ 割的容量是 $c (S, T) = \sum_{(μ, ν) \in (S \times T) ⋂ E} c (μ, ν)$ ；容量最小的割集称为最小割
简单割：若一个 $s - t$ 割满足割中的每条边都只与源点 $s$ 或汇点 $t$ 相连，则称该割为简单割
闭合图：若点集 $V^{'} \in V$ 是一个闭合图，那么对于 $\forall ⟨ μ, ν ⟩ \in E$ ，若 $μ \in V^{'}$ 则必有 $ν \in V^{'}$
最大权闭合图：一个点权和最大的闭合图
如下图所示，图中有 9 个闭合图（含空集）： $\emptyset$ ， ${3, 4, 5}$ ， ${4, 5}$ ， ${5}$ ， ${1, 2, 4, 5}$ ， ${2, 5}$ ， ${2, 4, 5}$ ， ${2, 3, 4, 5}$ ， ${1, 2, 3, 4, 5}$ 。其中，惟一的最大权闭合图为 ${3, 4, 5}$ ，且权和为 $4$

最大流最小割定理
¶

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

$f$ 是 $G$ 的一个最大流
残流网络 $G_{f}$ 不包含任何增广路径
$| f | = c (S, T)$ , 其中 $[S, T]$ 是流网络 $G$ 的最小割

网络流与最大权闭合图
¶

将原图转化为网络 $N = (V_{N}, E_{N})$ ：

将原图中的所有有向边 $⟨ μ, ν ⟩ \in E$ 替换为容量为 $c (μ, ν) = \infty$ 的有向边 $⟨ μ, ν ⟩$ ，并将其纳入边集 $E_{N}$
增加源点 $s$ 和汇点 $t$
由源点向原图中的所有正权点 $ν (ω_{ν} > 0)$ 连接一条容量为 $c (s, ν) = ω_{ν}$ 的有向边 $⟨ s, ν ⟩$ ，并将其纳入边集 $E_{N}$
由原图中的所有负权点 $ν (ω_{ν} < 0)$ 连接一条容量为 $c (ν, t) = - ω_{ν}$ 的有向边 $⟨ ν, t ⟩$ ，并将其纳入边集 $E_{N}$

也就是

\begin{aligned} (1) & V_{N} = V ⋃ {s, t} \\ (2) \\ (3) & E_{N} = E ⋃ {⟨ s, ν ⟩ | ν \in V, ω_{ν} > 0} ⋃ {⟨ ν, t ⟩ | ν \in V, ω_{ν} < 0} \\ (4) \\ (5) & 其中， {\begin{aligned} c (μ, ν) = \infty & ⟨ μ, ν ⟩ \in E \\ c (s, ν) = ω_{ν} & ω_{ν} > 0 \\ c (ν, t) = - ω_{ν} & ω_{ν} < 0 \end{aligned} \end{aligned}

上式中的 $\infty$ 取一个大于 $\sum_{ν \in V} | W_{ν} |$ 即可。则原图 $G$ 构成的网络 $N$ 如下图

若原图所有正权点的点权和为 $R_{v}$ ，对该网络跑最大流，且最大流为 $R_{f}$ ，所得到的最小割为 $[S, T]$ ，则有：

原图的最大权闭合图的权和为 $R_{v} - R_{f}$
$S - {s}$ 为原图点数最少的最大权闭合图

证明由下述几个引理构成。

引理1
¶

本问题的网络 $N$ 中，最小割是简单割。

由于除与源点 $s$ 或汇点 $t$ 直接相连的边的容量是有限的，其它边是无限的，那么最小割中显然不会出现容量为无限的边（因为强行割断所有与源点相连的边可以构成一个割集，且割的容量是有限的，最小割的容量不会比这个大），所以该最小割是简单割。

引理2
¶

记 $G_{1}$ 是原图 $G$ 的一个闭合子图， $V_{1}$ 为 $G_{1}$ 的点集； $\overset{―}{V_{1}}$ 为点集 $V_{1}$ 在原图 $G$ 中的补集，即 $V_{1} ⋃ \overset{―}{V_{1}} = V$ 。则网络 $N$ 的简单割 $[S, T]$ 与图 $G$ 的闭合子图 $G_{1}$ 存在一个一一对应关系：

V_{1} ⋃ {s} = S

其中

闭合图对应简单割：即 $S = V_{1} ⋃ {s}$ ， $T = \overset{―}{V_{1}} ⋃ {t}$
因为 $V_{1}$ 是一个闭合图，所以不存在 $⟨ μ, ν ⟩ \in E$ ，其中 $μ \in S - {s}$ ， $ν \in T - {t}$ 。也就是不存在不与源汇有关联的边，其两个端点分别在 $V_{1}$ 和 $\overset{―}{V_{1}}$ 中，所以 $[S, T]$ 是一个割集。
由引理1 可知， $[S, T]$ 是一个简单割。
简单割对应闭合图：即 $V_{1} = S - {s}$ 是一个闭合图。
若 $μ \in S - {s}$ ， $ν \in T - {t}$ ；显然不存在边 $⟨ μ, ν ⟩ \in E$ ，否则与 $[S, T]$ 是割集矛盾（因为 $c (μ, ν) = \infty$ ）。

引理3
¶

记 $V^{+}$ 为 $V$ 中点权为正的最大点集， $V^{-}$ 为 $V$ 中点权为负的最大点集；类似地，定义 $V_{1}^{+}$ 、 $V_{1}^{-}$ 、 ${\overset{―}{V_{1}}}^{+}$ 、 ${\overset{―}{V_{1}}}^{-}$ . 则在引理2 的一一对应关系下（即 $V_{1} ⋃ {s} = S$ 、 $\overset{―}{V_{1}} ⋃ {t} = T$ ），有：

\begin{matrix} (1) & c [S, T] = \sum_{ν \in {\overset{―}{V_{1}}}^{+}} ω_{ν} + \sum_{ν \in V_{1}^{-}} (- ω_{ν}) \end{matrix}

显然， $[S, T] = [{s}, \overset{―}{V_{1}}] ⋃ [{t}, V_{1}] ⋃ [\overset{―}{V_{1}}, V_{1}]$ （分析构造图的源汇关联情况不难得出结论）
因为 $[S, T]$ 是简单割，故 $[\overset{―}{V_{1}}, V_{1}] = \emptyset$
又因为 $s$ 只与正权点连边，故 $[{s}, \overset{―}{V_{1}}] = [{s}, {\overset{―}{V_{1}}}^{+}]$
而 $t$ 只与负权点连边，故 $[{t}, V_{1}] = [{t}, V_{1}^{-}]$ 因此， $[S, T] = [{s}, {\overset{―}{V_{1}}}^{+}] ⋃ [{t}, V_{1}^{-}]$ ，即可证明了式 $(1)$ 的正确性

引理4
¶

当网络 $N$ 取得最小割时，其对应的图 $G$ 的闭合图（ $V_{1} = S - s$ ）将取得最大权（最优性）：

按照定义，闭合图的权值为正权点的权的绝对值和 - 负权点的权的绝对值和，即
$\begin{matrix} (2) & ω (V_{1}) = \sum_{ν \in V_{1}^{+}} ω_{ν} - \sum_{ν \in V_{1}^{-}} (- ω_{ν}) \end{matrix}$
由式 $(1)$ 和式 $(2)$ ，可得：
$\begin{aligned} (6) & ω (V_{1}) + c [S, T] & = \sum_{ν \in V_{1}^{+}} ω_{ν} - \sum_{ν \in V_{1}^{-}} (- ω_{ν}) + \sum_{ν \in {\overset{―}{V_{1}}}^{+}} ω_{ν} + \sum_{ν \in V_{1}^{-}} (- ω_{ν}) \\ (7) & = \sum_{ν \in V_{1}^{+}} ω_{ν} + \sum_{ν \in {\overset{―}{V_{1}}}^{+}} ω_{ν} \\ (8) & = \sum_{ν \in V^{+}} ω_{ν} \end{aligned}$
整理得 $ω (V_{1}) = \sum_{ν \in V^{+}} ω_{ν} - c [S, T]$

《最小割模型在信息学竞赛中的应用》--by 胡伯涛

Terms¶

最大流最小割定理¶

网络流与最大权闭合图¶

引理1¶

引理2¶

引理3¶

引理4¶

Related¶