最大权闭合子图的相关概念

闭合子图： 给定一个有向图 $G(V, E)$，图中的某一个点集，这个点集满足内部的所有边不能从点集里面指向点集外面，则将这个点集和点集里面的边统称为原图的 闭合子图

最大权闭合子图： 给定一个有向图 $G(V, E)$，每个点上有一个权值，图中存在若干个闭合子图，若其中一个闭合子图的点集权值和最大，则这个闭合子图称为 最大权闭合子图

如何求最大权闭合子图：

求最大权闭合子图是最小割问题的一个应用，因此我们其实只需要证明原问题的任意一个闭合子图都能对应到流网络中任意一个割的集合。这样我们想求原问题的最值就能对应去求割的最值。

首先我们需要先将原问题的有向图变成一个流网络，假设原问题的有向图是 $G = (V, E)$，转化成的流网络是 $G_N = (V_N, E_N)$。

流网络需要一个源点一个汇点，然后我们需要表现出每个点的权值，每个点的权值有正有负，我们可以从源点向所有权值为正的点连一条边，容量是点的权值；从所有权值为负的点向汇点连一条边，容量是点的权值的绝对值；原图中间的所有边都不变，容量是 $+\infty$。

通过以上的方式，我们构造出了一个流网络 $G_N = (V_N, E_N), V_N = V + \lbrace s, t \rbrace, E_N = \lbrace (s, u), w_u>0 \rbrace \cup \lbrace (u, t), w_u<0 \rbrace \cup E$。

然后需要证明对应关系，我们设定一个特殊的割，将所有割边和源点或汇点相连的割称为简单割（只针对本问题），显然，简单割是所有割的一个子集。

可以发现，最小割一定是一个简单割，因为最小割就是最大流，而从源点出发的所有边都是有限容量，所以最大流是有限值，对应的最小割也是有限值，因此最小割一定不包含中间那些容量是 $+\infty$ 的边，所以最小割一定是简单割

我们接下来要证明原问题的闭合子图能和所有简单割一一对应。

对于原图的任何一个闭合子图的点集 $V’$，我们构造一个割集 $[S, T]$，由于构造的割集只需要满足源点在 $S$，汇点在 $T$ 即可，因此我们规定 $S = V’ + \lbrace s \rbrace, T = V_N - S$。那么构造出的这个割集是不是一个简单割呢，可以发现 $S$ 中除了源点，其他所有点构成一个闭合子图，因此这些点都不可能走到汇点，且这些点和其他子图外的点之间都不存在边，所以就能保证这样割集中的割边只可能是和源点或汇点相连的割边，因此这就是一个简单割。

反过来，对于任意一个简单割 $[S, T]$，构造一个闭合子图 $G’$，这个闭合子图的点集 $V’ = S - \lbrace s \rbrace$，由于简单割保证了两个集合之间不存在相连的边，所以从 $S$ 的任何一个点出发，都必然会走回到 $S$，不可能走到 $T$，因此 $V’$ 就是一个闭合点集，$G’$ 就是一个闭合子图。

综上所述，我们证明了原问题的任何一个闭合点集和流网络中的任何一个简单割都是一一对应的。

由于求的是闭合子图的最大权值，所以我们还需要确定它们之间的数量关系。对于流网络的任何一个简单割 $[S, T]$，对应的闭合子图的点集是 $V’ = S - \lbrace s \rbrace$，我们规定 $V’‘ = V - V’$可以发现，这个割的左集合中是 $V’, \lbrace s \rbrace$，右集合中是 $V’‘, \lbrace t \rbrace$，所有割边只可能是左边两部分和右边两部分之间的边，而 $V’$ 和 $V’‘$ 之间不存在边，$\lbrace s \rbrace$ 和 $\lbrace t \rbrace$ 之间也不存在边，因此这个简单割的容量就是 $C[S, T] = C[V’, \lbrace t \rbrace] + C[\lbrace s \rbrace, V’‘] = \sum_{v \in V’‘} w_v + \sum_{v \in V’} -w_v$。

若设定 $V^+$ 是 $V$ 中所有权值为正的点，$V^-$ 是 $V$ 中所有权值为负的点。因此进一步具体 $C[S, T] = \sum_{v \in V’‘^+} w_v + \sum_{v \in V’^-} (-w_v)$，而闭合子图的权值和 $w(V’) = \sum_{v \in V’^+} w_v + \sum_{v \in V’^-} w_v = \sum_{v \in V’^+} w_v - \sum_{v \in V’^-} (-w_v)$。

可以发现 $C[S, T] + w(V’) = w(V^+)$，所以我们要求的最大权闭合子图 $w(V’) = w(V^+) - C[S, T]$，$w(V^+)$ 是固定值，所以我们要让 $C[S, T]$ 最小，即最小简单割的容量，而流网络的最小割就是简单割，因此等价于流网络的最小割，再用所有正权值的点的权值和减去最小割的容量就是最大权闭合子图的权值和。

经过以上的一系列分析，我们通过最小割求出了最大权闭合子图，推导比较复杂，但是实际操作就是建图求最小割再计算一下。