Maximum Weight Closure of a Graph

/ 0评 / 0

今天做题遇到了这个经典问题,拜读了《最小割模型在信息学竞赛中的应用》也顺便回顾下网络流的相关知识。全文当作是对论文的回顾,同时感谢作者的辛勤付出。

Introduction

最大权闭合图指的是一个有向图$G=(V,E)$的点集$V$,且该点集满足如果$u$在$V$中,那么$u$指向的后继$v$也在$V$中,给每个点分配一个权值(可正可负),那么最大的权闭合子图就是点权最大的闭合图。

construction:

在原图的基础上增加源$ S$,汇$ T$ 对于节点$i$如果点权为正,建立$S->i$的边,边边权为 $w$,如果点权为负建立$i->T$的边,边权为$-w$, 对于原图的所有有向边$u->v$建$u->v$边,边权设为$inf$ 。

Proof:

【最大权闭合图的权值==正权值之和-最小割】的简单证明

1) 首先最小割一定是简单割($s-t$割),因为和$s$及$t$相连的边集本身就可以构成一个割且这个割肯定不是无穷大,
而最小割一定小于这个割,因此最小割一定不含边权未无穷的边,故最小割必是简单割(所有割边与$ s$或$ t$相连)
参考论文符号$[S,T]$将网络$N$的点集$V_N$划分为点集$S$及其补集$T(T=V_N-S)$。
$V^{-}$为点权为负的点集,$V^{+}$为点权为正的点集。

2) 其次简单割一定也对应一个闭合子图 $(V_1 \cup {s}=S)$证明:由1)我们可设闭合子图$V$ 和 $s$ 构成 $S$ 集,和 $t$ 构成 $T$ 集$(T=\overline{S})$。
证明闭合子图是简单割:若闭合子图不是简单割,则存在一条边$(u,v), u \in S, v\in T $且$c(u,v)=\infty $而边权为$\infty $的边是不可能出现在简单割里的,故闭合图存在一个后继不在闭合图内。
证明简单割是闭合子图:对于子图$V$中的任意一点$ u$,$ u \in S $,而$u$的任意一条出边$ c(u,v) \neq \infty $,
所以V中的所有点均在S中,故$ V=S-{s}$是闭合子图。
有了上面的引理下面我们来证明最大权闭合图为$ s$所在的最小割$ [S,T]$的$ S$集合。
记一个简单割的容量为$ C$,且s所在的集合为S,t所在的集合为T,
则$\displaystyle w(V_{1})= \sum_{v \in V_{1}^{+}}w_{v} - \sum_{v\in V_{1}^{-}}(-w_v) $
而在一个割[S,T]中割的容量 $\displaystyle c[S,T]=\sum_{v\in V_{2}^{+}}w_v + \sum_{v\in V_{1}^{-}}(-w_v) $
即是 $\displaystyle [S,T]=[{s},V_{2}^{+}]\cup [V_{1}^{-},{t}]$ 故上式成立

将上式相加得 $\displaystyle w(v_{1})+c[S,T]=\sum_{v\in v_{1}^{+}}w_{v}-\sum_{v\in V_{1}^{-}}(-w_{v})+\sum_{V_{2}^{+}}w_v + \sum_{v\in V_{1}^{-}}(-w_{v})$
$ \displaystyle w(v_{1})+c[S,T]= \sum_{v\in V_{1}^{+}}w_v + \sum_{v\in V_{2}^{+}}w_v$
$ \displaystyle w(v_{1})+c[S,T]= \sum_{v\in V^{+}}w_v$
整理得:$\displaystyle w(V_1)=\sum_{v\in V^{+}}w_v-c[S,T]$
故最大化$\displaystyle w(V_1)$即是最小化简单割的容量,即是求得最小割,问题转换为最小割/最大流模型。
此外通过最小割模型得出的最大权闭合图还满足该闭合图的点数量最少。

发表评论

电子邮件地址不会被公开。 必填项已用*标注