《最小割模型在信息学竞赛中的应用》学习笔记

基础

流网络的定义,容量限制,反对称性,流守恒性...

我们约定对于点集\(X,Y\) ,令 \(f(X,Y)=\sum_{u \in X}\sum_{v \in Y} f(u,v)\) \[ \forall X,\quad f(X,X)=0 \\ \forall X,Y,\quad f(X,Y)=-f(Y,X) \\ \forall X,Y,Z,\ X \cap Y=\emptyset,\quad f(X \cup Y,Z)=f(X,Z)+f(Y,Z) \] 增广路,最大流,最小割...

需要注意的是通过割的净流是把反向边算在内的,而割的容量是不算的。

最小割的边都是满流边。满流边不一定都是最小割中的边。

最大流最小割定理:

\(f\)\(G\) 的最大流 \(\Leftrightarrow\) 残量网络不含增广路 \(\Leftrightarrow\)\(G\) 的割 \([S,T]\)\(|f|=c[S,T]\)

分数规划

形式化的定义: \[ Minimize \quad \lambda = f(x)= \frac {a(x)} {b(x)} (x \in S) \\ s.t. \ \forall x\in S,\ b(x)>0 \\ \] 其中的 \(x\) 是向量,\(S\) 是解空间。

\(\lambda\) 为当前猜测最优值,构造函数 \[ g(\lambda)=\min_{x \in S}\{ a(x)- \lambda b(x)\} \] \(Dinkelbach\) 定理: 设 \(\lambda^*=f(x^*)\) 为最优解,有 \[ g( \lambda)<0 \Leftrightarrow \lambda>\lambda^* \\ g( \lambda)=0 \Leftrightarrow \lambda=\lambda^* \\g( \lambda)>0 \Leftrightarrow \lambda<\lambda^* \] 大概就是,若 \(a(x)-\lambda b(x)<0\) ,则 \(\frac {a(x)}{b(x)}< \lambda\) ... 通过 \(g(\lambda)\) 符号验证,二分求答案。

0-1 分数规划是一个特例,比较常见。

就是解向量满足只有 \(01\) ,可以表示为: \[ Minimize \quad \lambda=f(x)=\frac{\sum_{i} a_i x_i}{ \sum_i b_ix_i} \\ s.t. \quad \sum_i b_ix_i>0 \]

最大权闭合图

定义一个有向图的闭合图是该有向图的一个点集,且该点集的所 有出边都还指向该点集。闭合图不一定是一个连通块。

给每个点分配一个权值,权值和最大的闭合图被称为最大权闭合图。

它体现的是一种从属,前提,顺序关系。

最大权闭合图的求法是转化成最小割模型:

原图每条有向边 \((u,v)\) 替换为 \(c(u,v)=+\infty\) 。 对于所有 \(w_x>0\) 加边 \(c(S,x)=w_x\)。 对于所有 \(w_x<0\) 加边 \(c(x,T)=-w_x\)

正确性:

为方便叙述,设 \(V\) 表示原图点集,设 \(V_1\) 表示选的闭合图,\(V_2=V-V_1\) , \(V^+\) 表示 \(V\) 点集中权为正的点集,\(V^-\) 是负的。 \[ c[S,T]=\sum_{v \in V_2^+ } w_v+\sum_{v \in V_1^-}w_v \\ w(V_1)=\sum_{v \in V_1} w_v \\ w(V_1)=\sum_{v \in V^+} w_v - c[S,T] \] 要最大化 \(w(V_1)\) ,即要最小化 \(c[S,T]\) ,所以就能转化为最小割了。

最大密度子图

无向图的子图的密度:$ D = $

看成是分数规划问题,二分答案 \(\lambda\) ,需要求 \[ g(\lambda)=\max\{ |E|- \lambda |V| \} \] 先看二分的范围:显然有 $ m < ans< 1 n$ ,而且对于两个子图,其密度差不小于 \(\frac 1 {n^2}\) 。所以二分的次数是 \(O(\log n)\) 级别的,有点常数。

\(g( \lambda)\) 一般有两种做法:

直接转化为最大闭合权图,一个点贡献 \(-\lambda\) ,一条边贡献 \(1\) ,取一条边的条件是其两个端点都取了。所以对原图每个点每条边建点,连一连就好了。这样图的规模是 \((n+m,n+m)\)

上面的做法比较直接,一般比较好的是这个方法, \[ \max\{ {|E'|-\lambda|V'|} \} = -\min\{\lambda|V'|-|E'|\}\\ =-\min\{ \sum_{v \in V'}\lambda- \Big( \frac {\sum_{v \in V'} d_v -c[V',\overline{V'}]}{2} \Big)\} \\ = -\frac 1 2 \min\{ \sum_{v \in V'}( 2\lambda-d_v)+c[V',\overline{V'}] \}\\ \] 相当与选一个点集 ,其中每个点贡献 \(2\lambda-d_v\) ,剩余点贡献 \(0\), 再加上一个割。

然后就可以转化为最小割问题啦。建图:

对于原图每条无向边 \(u,v\),连 \(c(u,v)=1,c(v,u)=1\)

对于每个点 \(v\) ,连 \(c(s,v)=U+0,c(v,t)=U+2\lambda-d_v\) ,这里加上一个较大数 \(U\) 是为了保证权非负,一般取 \(U=m\)

这样图的规模就变小很多: \((n,n+m)\)

最大密度子图带边权的推广

\[ D=\frac{\sum_{e \in E} w_e}{|V|} \]

只需把 \(d_v\) 换定义为关联边的权值和,把最小割建图中边的容量由 \(1\) 换成 \(w_e\) ,并调整 \(U\), 可以取 \(\sum_{e \in E} w_e\)

注意二分次数 \(O(\log n)\) 就不成立了,而和边权大小有关,不过影响不大。

最大密度子图点与边均带权的推广

\[ D=\frac{\sum_{v \in V}p_v+\sum_{e\in E}w_e }{|V|} \]

也是类似的: \[ \max\{ { \sum_{v \in V}p_v+\sum_{e\in E}w_e-\lambda|V'|} \} = -\min\{\sum_{v \in V'} (\lambda-p_v)-\Big( \frac {\sum_{v \in V'} d_v -c[V',\overline{V'}]}{2} \Big)\} \\ = - \frac 1 2 \min\{ \sum_{v \in V'}(2\lambda-2p_v-d_v)+c[V',\overline{V'}] \} \] 用上面的方法建图即可。

二分图最小点权覆盖集与最大点独立集

点覆盖集:是无向图 的一个点集,使得该图中所有边都至少有一个端点在该集合内。 ' VV ∈ (,) u v E∀ ∈,满足对于 ,都有 或 成立,即 ,'uV ∈ ' vV ∈ ' uV ∈ ' vV ∈ 至少一个成立。形象地说是若干个点“覆盖”住了 与它们邻接的边,这些边恰好组成了原边集。

点独立集:是无向图的一个点集,使得任两个在该集合中的点在原图中都不相邻。或者说是导出子图为零图的点集。

最小点覆盖集:是在无向图中,点数少的点覆盖集。

最大点独立集:是在无向图 中,点数多的点独立集。

最小点权覆盖集,最大点权独立集,就是加了点权的。

以上两个问题在一般无向图中都是经典的NPC问题。

二分图的最小点权覆盖集求法:

就是转化成最小割,对于左边的点连 \(c(s,v)=w_v\) 右边 \(c(v,t)=w_v\) 。对于原无向边 \((u,v)\) ,连 \(c(u,v)=+\infty\)

二分图的最小点权独立集求法: \[ !(u \in V' \text{ and }v \in V' ) \Leftrightarrow u\in \overline{V'} \text{ or } v\in \overline{V'} \] 可见点覆盖集与点独立集是互补的,若 \(V\) 为点覆盖集,则 \(V'\) 一定满足是点独立集,反之亦然。

所以最大化点覆盖集的权值和,就能最小化点独立集的权值和。