最大权闭合图

据说这玩意算图论?

学,我学还不行么….

Maximum Weight Closure of a Graph

最大权闭合图

闭合图是什么?

在一个图中,我们选一些点构成一个集合,如果这个点的所有出边指向的点也在这个集合中.

那么我们可以称这个集合为闭合图.


比如这个图

闭合图有

{5},{4,5},{2,5},
{1,2,4,5},{1,2,3,4,5},
{2,4,5},{3,4,5}

最大权闭合图是{3,4,5},权和为4.

在许多实际应用中,给出的图为\(DAG\)有向无环图,闭合图的性质就反应了事件间的必要条件的关系:一个事情发生,其所需要的所有前提也要发生.

也就是依赖.

比如指定大学的选课计划,一些课程需要以另一些课程为基础,相当于给出了一个\(DAG\).

如果需要给所有课程打分,我们上文提到的最大圈闭合图就对应了受益最大或者是效率最高的选课计划.

当然不全是给定的类\(DAG\)图,如果一旦存在环,也就是我们说的相互依赖的操作.

当然这并不影响我们用最大权闭合图来解决问题.


我们需要把之前的那个图转换成网络\(N=(V_N,E_N)\),这样才可以利用已知的最小割的模型.

我们需要增加一个源点\(s\)和汇点\(t\),将原图中的所有的有向图的边\(u,v\)替换成容量为\(c(u,v)=\infty\)的有向边\(u,v\).

连接源点\(s\)到原图的每一个正权点\(v\)的有向边,容量记为\(w\),对于题中说的负权点\(v\),需要连接至汇点.容量记为\(-w\).


首先我们需要申明一个新的定义

简单割

即若一个\(s-t\)的割满足割集中满足每一条边都只与源\(s\)或者汇\(t\)关联,那么这个割就是简单割.

但是在上面说的网络\(N\)中,简单割就是最小割.

wft?为什么

首先我们在建立网络的时候就说到了.

与源点汇点相连的边的容量是有限的.其他都是正无限的边.

那么与源或汇关联的边组成的割集也一定是有限的.就是所有点权的绝对值的和.

最小割容量也最大就是这个所有点权的绝对值的和.

最小割不可能取任意一条容量为正无穷的边,那么最小割集的所有边一定在这个网络\(N\)中与源点汇点相连

那么也就是说最小割就是简单割.

这个和最大权闭合图有什么关系么?


最大权闭合图的权值=正权值总和-最小割容量

证明?

给个机会让我研究一下,先口胡了

规定一下符号.设简单割\([S,T]\)将网络\(N\)的点集\(V_N\)划分成点集\(S\)和补集\(T\),\(T=V_N-S\),满足\(s\in S\),\(t\in T\).\(c[S,T]\)表示的是\([S,T]\)的容量和.设闭合图为\(V_1\),在\(V\)中的补集为\(\bar V_1\)或者是\(V_2,(V_2=V-V_1)\).记\(V^+\)为\(V\)中的点权为正的点集,\(V^-\)为\(V\)中点权为负的点集.

首先是闭合图的权值和是正权点的权的绝对值减去负权点的权的绝对值的和.

\[W(V_1)=\sum _{v\in V_1^+}W_v\ -\ \sum_{v\in V_1^-}(-W_v)\]

同时

\[c[S,T]=\sum_{v\in V_2^+}W_v\ +\ \sum_{v\in V_1^-}(-W_v)\]

其实就是最小割\([S,T]\)是简单割的另一种表示.

把上面的式子划到最简就是\([S,T]=[{s},V_2^+]\bigcup[V_1^-,{t}]\)

和上面一个意思.

我们将后面推出来的这两个式子相加.

\[W(V_1)+c[S,T]=\sum _{v\in V_1^+}W_v\ -\ \sum_{v\in V_1^-}(-W_v)+\sum_{v\in V_2^+}W_v\ +\ \sum_{v\in V_1^-}(-W_v)\]

\[W(V_1)+c[S,T]=\sum _{v\in V_1^+}W_v+\sum_{v\in V_2^+}W_v\]

\[W(V_1)+c[S,T]=\sum _{v\in V^+}W_v\]

再整理一下就是

\[W(V_1)=\sum _{v\in V^+}W_v-c[S,T]\]

左边\(W(V_1)\)就是我们说的最大权闭合图的权和.右边\(\sum _{v\in V^+}\)是一个定值.所以我们只需要最小化简单割\([S,T]\)的容量\(c\)就可得到最大的权和.

那么又回到了最开始的要最小化一个简单割.

在这种网络中.简单割就是这个最小的简单割啊.

所以最后算法的时间复杂度就简化到了求最小割的时间复杂度.

最小割又可以根据定理最小割=最大流转化

最后要求一个最大权闭合图的权值和不就是求一个最大流了么QAQ

是不是说明我默的20遍最大流的板子还有的救???

以上。


By:Wahacer

感谢资料来源:
胡伯涛《最小割模型在信息学竞赛中的应用》
最大权闭合图 – Because Of You – 博客园

2017.12.22

22:45

最大权闭合图》有1个想法

发表评论

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