网络流总结



网络流基本手段

网络流基本概念

我们可以将网络流类比为一些单向通水的水管组成的网络。以下的概念都将这样类比。

  • 节点v:水管的交点(交点没有流量限制)。英文vertex的首字母。
  • 弧e:水管(具有流量限制)。英文edge的首字母。
  • 容量c(u,v):水管的最大流速。英文capacity的首字母。
  • 流量f(u,v):水管当前的流速。英文flow的首字母。
  • 流F(S,T):水管网络仅从S进水,从T出水,的一个合理的流量方案。

下面,我们又有几个公理:

  • 弧的流量限制:f(u,v)<=c(u,v)。
  • 流量平衡:节点v的进入流量等于流出流量。

然后根据这些概念,我们可以定义网络流中最重要的一个部分:

  • 最大流F(S,T)::所有流F(S,T)中S处流速最大的方案。

同时还有几个比较重要的概念:

  • 增广路P(S,T):指从S到T的一条经过的弧全部满足f0)$或$f(i,T)=|S_i|\ (S_i 先计算原图最大流,再添边计算流量变化,与先添边,再一起计算总流量相比,可以保证添的边上流量最小.

这样,我们就可以利用循环流求得最小流。

具体方法是:

先跑$MaxFlow(S,T)$,再添边$f(T,S)\in [0,\infty]$,再计算循环可行流。这样保证了新添的边的流量最小,即原图的$Flow(S,T)$最小。

2.最小(大)费用最大流问题

增广路的求解不在使用dinic算法,而是用SPFA每次寻找最短(长)的一条边。根据网络流的贪心原则,我们最终找到的一定也是最大流。如下是一个最小费用最大流的代码片段。

int q[MX],pre[MX],dis[MX],inq[MX];
int spfa(int *flow,int *cost)
{
    int h=0,t=1,x,y,now=pre[T],mxf=+oo,cst=0;
    memset(dis,0x3f,sizeof(dis));
    memset(inq,0,sizeof(inq));
    memset(pre,0,sizeof(pre));
    q[++h]=S;dis[S]=0;pre[S]--;
    while(h>=t)
    {
        x=q[(t++)%MX];
        inq[x]=0;
        for(int i=fst[x];i!=-1;i=nxt[i])
        {
            y=e[i].v;
            if(e[i].c&&dis[y]>dis[x]+e[i].w)
            {
                dis[y]=dis[x]+e[i].w;
                pre[y]=i;               //记录节点的前驱
                if(!inq[y])q[(++h)%MX]=y,inq[y]=1;
            }
        }
    }
    if(dis[T]>+oo)return 0;             //没有増广路
    while(now!=-1)                      //找到增广路上的最小权边权
    {
        mxf=min(mxf,e[now].c);
        cst+=e[now].w;
        now=pre[e[now].u];
    }
    now=pre[T];
    while(now!=-1)                      //增广后修改边的流量
    {
        e[now].c-=mxf;
        e[now^1].c+=mxf;
        now=pre[e[now].u];
    }
    *flow+=mxf,*cost+=cst*mxf;
    return 1;yi
}

int mcf()                               //minimum_cost_flow
{
    int flow=0,cost=0;
    while(spfa(&flow,&cost));
    return cost;
}

3.边权变化的费用流

这类费用流的通性是:费用与流量不成线性关系。但是这种函数我们依旧可以用线性函数拟合。
例如:

  • 一条边的边权在经过一次后改为0:这条边拆成两条边,第一条容量为1,权值不变;第二条容量为$+\infty$,权值为0
  • 一条边的权值与流量成二次函数关系(整数流量):这条边拆成多条边,每条容量为1,权值分别为1,3,5,…

等等等等,我们依旧不需要改变网络流算法,而是在图上做手脚。

4.动态添边的网络流

对于动态添边,动态求解的网络流,我们可以在原图添边后不重新进行所有的增广操作,而是直接在原残量网络上添边,增广。这样做并不会导致最终答案变化。我们可以这样理解:之前这条边其实一直存在,只是我们没有用它增广罢了。现在添边意味着我们可以通过它增广。这样依旧可以求出当前图的最大流、最值费用流等值。

5.二分图相关问题:

我们需要分析的是:最大匹配与最小顶点覆盖数、最小边覆盖数、最大点独立集之间的关系。

定义:

  • 最大匹配数:二分图中边集数目最大的匹配数
  • 最小顶点覆盖:用最少的点,让每条边都至少与其中一个点相连
  • 最小边覆盖:用尽量少的边,让每个点都至少与其中一个边相连
  • 最大独立集:选尽量多的点,让它们亮亮没有相连的边

a.最小顶点覆盖=最大匹配数(König定理)

设最大匹配数为n,最小顶点覆盖为m。
首先我们证明m>=n:如果从最大匹配看最小顶点覆盖,那么最大匹配中的每一条边都没有公共顶点,故覆盖它们至少需要n条边,即m>=n。
我们再证明m<=n:如果从最小顶点覆盖看最大匹配,那么一个最大顶点覆盖一定可以转化成一个最大匹配,这个最大匹配的每一条边都至少覆盖一个顶点覆盖中的顶点。所以m<=n。
那么,我们就推出了:m=n,也就是说二分图的最小顶点覆盖=最大匹配数。

当然,这只是比较感性的证明,更严谨的证明可以参考König定理

另外,根据König定理,我们可以得到输出最小顶点覆盖的方案的算法(如在UVa11419中的应用)。

b.最小边覆盖=顶点数-最大匹配数

设最大匹配数为n,最小边覆盖为k,图为联通图。
使用一点贪心的策略:由于一条边只能至多覆盖2个顶点,所以我们需要用尽量多的边覆盖两个顶点,尽量少的边覆盖剩下的点。这样得到的边覆盖一定是最小的。
由于最大匹配中的边可以覆盖两个点,且不存在别的方案比最大匹配中的边多,所以我们先用这些边覆盖两个点。余下的顶点每个顶点用一条边覆盖。如果剩下的点有a个,那么2n+a=|V|,所以我们总共使用的边数(n+a)=|V|-n。

c.最大独立集=顶点数-最大匹配数

设最大匹配数为n,最大独立集为d。
根据定理1:n=m我们可以知道,最大匹配的边对应的2n个顶点中有n个顶点最为最小顶点覆盖,那么剩下的|V|-n个点一定会两两独立,否则其中至少有一个顶点会出现在最小顶点覆盖中,与题设不符。因此这|V|-n个顶点就是最大独立集。

6.子图相关问题

a.最大权独立子图

最大权独立子图指的是求有向图的一个点权和最大的子图P(可以就是原图),使原图中不存在任何一条边$(u,v),(u\in P,v\not\in P)$。
也就是说“肥水不流外人田”,我们需要找到一个只能进来不能出去的子图。

怎么做呢?我们可以先把权值按正负分类,正权点在左,编号Xi,负权点在右,编号Yi。
如果我们选则了一个正权点X,为子图增加了Xi的贡献,那么X指向的负权点Y会为子图扣除|Yi|的贡献。为了利益最大化,如果我们选择的X的贡献可以弥补Y的损失,那么我们选择X,否则我们不选X。即:贡献随讨论的X的增多一定是单调不降的。换成数学语言,对于一组{Xi},{Yi},对原图的贡献一定是$|X|-min(|X|,|Y|)$。(表述有些含糊,但是我们需要意会)。这样一来,我们就可以利用最小割来解决了。

我们建立一个新图,图中左边的点对应原图每个正权点,右边的对应原图每个负权点。如果原图存在点Xi,那么原图左边也有Xi,同时建立边(S,Xi)=|Xi|,如果原图存在点Yi,那么原图右边也存在点Yi,同时建立边(Yi,T)=|Yi|。原图所有边也都加入到新图中,权值为正无穷。这样,新图最大流(即最小割)即是求出了min(|X|,|Y|)的值。我们拿所有正权点的权值和减去F(S,T)即是最大权独立子图的权值和。

与最小顶点覆盖问题一样,这个问题的数值答案和方案答案也是有一定距离的,下面要说明如何通过最大流求得具体的最大权独立子图。

对于一个求出了最小割的图,其S点可以通过正向边和反向边到达的点为原图中被选择的点。原因:无法访问的点为被割掉的边截断的点,故我们不需要选择。反之没有被截断的点就是我们要选择的点。而且可以知道这些点权值和的确为$(\sum |Xi|)-F(S,T)$。

b.最大密度子图

最大密度子图类似于最大权独立子图,是一个点集P和边集Q构成的子图,其中$Q={(u,v)|u\in P,v\in P}$,而且$\frac{|Q|}{|P|}$最大。
简单的理解就是边数/点数最大的图。每一条边都连接这这个图中的两个点。

此题的高效求解需要结合最大权闭合子图和分数规划的思想,故也出现在了这篇文章里。

设原图中密度($|E|/|V|$)大于等于x的子图的数量为num(x),那么num函数一定随x递增而递减。所以我们可以用二分法求这个函数值恰好不为0的x值。

如果我们需要判定是否存在密度为x的子图,我们可以用以下的方法:

由于每选择了一条边,与它相连的点必须被选择。那么如果我们设边权为1,点权为-x,若我们按照这种策略找到了权值和大于0的子图,则证明存在密度为x的子图,反之不存在。

所以我们可以建立二分图,通过求解最大权闭合子图获得答案。建立一个二分图,左边的顶点Xi对应原图的边,连边(S,Xi)=1,右边的顶点Yi对应原图的点,连边(Yi,T)=x。按照最大权闭合子图的算法,如果你得知最大权为0时(即最大权的子图就是屁都不选),你就要含泪调小二分上界继续查找更小的x,反之你可以自信地调大下界,尝试更大的x。这样,我们通过对x的二分+判定,找到了满足要求的x,使num(x)恰好不为0。由于这时的x可能为小数,所以我们需要对实数进行二分,在实数意义下跑网络流,此时需注意eps等的设定。

其他

a. Dilworth定理

图的最长反链长度等于最小链覆盖。

该定理是针对什么鬼偏序集上的。其具体内容是:反链是一种偏序集,其任意两个元素不可比;而链则是一种任意两个元素可比的偏序集。Dilworth定理说明,存在一个反链A与一个将序列划分为链族P的划分,使得划分中链的数量等于集合A的基数。

链,我们可以具象地理解为图上的一条有向边连成的路,因此反链就是图上的一组点,两两不可达。

证明:略

b.霍尔定理

二分图的完美匹配存在的充要条件是:二分图左部任意k个元素在右部共有k个以上的相邻元素。

证明:略

分类: 所有

5 条评论

litble · 2018年6月29日 9:19 下午

Dilworth定理有没有说人话的解释方法啊QAQ

泥萌说这种神仙语言我看不懂啊

    boshi · 2018年6月30日 4:25 下午

    就是有向图中{两两不可达的点}的最大点数={覆盖所有的点链}的最小链数

litble · 2018年6月29日 8:31 上午

图的最长反链是个什么东西

    victor · 2018年6月29日 9:14 下午

    就是一个点集,其中的点两两互不可达

litble · 2018年6月29日 8:23 上午

好文Orz

发表评论

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

你是机器人吗? =。= *