首页 > 笔记 > 网络流模型总结

网络流模型总结

对网络流各种姿势的总结

前言

我们可以看一下网络流24题的各种模型

images

可以看到,除了几道最短路还有一个恶心的IDA*/n6的DP,别的都可以转化成最大流或最小费用最大流的模型

下面就一个一个开讲吧。。

1.二分图匹配类问题

何为二分图

“二分”指中国人民银行以前发行的面值为两分的纸币和硬币

设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B),则称图G为一个二分图。

无向图G为二分图的充分必要条件是,G至少有两个顶点,且其所有回路的长度均为偶数。

简单来说就是一个图可以分成两侧,两侧的节点之间没有连边,可以形象的理解一下

images

 

何为二分图匹配

给定一个二分图G,在G的一个子图M中,M的边集{E}中的任意两条边都不依附于同一个顶点,则称M是一个匹配。

简单的说就是选一个边的集合,使边两边连的点不相同

①二分图最大匹配

何为二分图最大匹配

极大匹配(Maximal Matching)是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。最大匹配(maximum matching)是所有极大匹配当中边数最大的一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。

最大匹配就是尽量多的选边,但要求是个匹配

二分图最大匹配问题可以用网络流和匈牙利算法解。。

网络流的话,我们可以在二分图的基础上增加源S和汇T。

1.S向U集合中每个顶点连一条容量为1的有向边。

2.V集合中每个顶点向T连一条容量为1的有向边。

3.UV集合之间的边连容量为1的有向边。

求网络最大流,流量就是匹配数,所有满流边是一组可行解。

images

 

但是这为什么是正确的呢?因为每次当选出一个匹配的时候,就相当于S到T有了一条路径满流了,也就相当于U和V中都选了一个点,而且S和T连的边都满流了,所以一个点也保证了不能被选两次。因为是最大流,所以尽量选多的边流量最大,复合了最大匹配的性质。

例题:T1

②二分图多重匹配

何为二分图多重匹配

就是匹配中一个点可以有多个匹配边相连,但是有一个上限

这个模型可以直接把上一个改一下就行了,

1.S向U集合中每个顶点连一条容量为能匹配的数量的有向边。

2.V集合中每个顶点向T连一条容量为能匹配的数量的有向边。

3.UV集合之间的边连容量为1的有向边。

*4.根据边是否满流判断可行性//不一定需要

images

我们可以这样理解,中间的流量为1限制了每一个匹配只能匹配两个点,到汇点和原点的连边保证了一个点可以被匹配多次。

例题 T5T7

③二分图最佳匹配

何为二分图最佳匹配

如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配。

权值和最大的完备匹配称为最佳匹配.

这个的做法也比较好理解

1.从S向每个U连一条容量为1,费用为0的有向边。

2.从每个V向T连一条容量为1,费用为0的有向边。

3.从有连边的Ui向Vi连接一条容量为无穷大,费用为权值的有向边。

求最大费用最大流,最大费用流值就是最佳匹配。

images

因为每个点都要选,所以源点汇点直接连1就行了,这样流量就限制了,中间就不用管了。然后因为是最大费用最大流,所以会跑最大的权值,满足最佳匹配的性质。

例题 T18

④二分图问题引申

最小覆盖:选出最少的点,使得每一条边都至少有一个点被选中

最大独立集:选出最多的点,使得点之间两两没有边

最大匹配=最小覆盖=总点数-最大独立集

下文会讲。。

2.最大权闭合图

何为闭合图

定义一个有向图的闭合图G是该有向图的一个点集,且该点集的所有出边都还指向该点集。即闭合图内的任意点的任意后继也一定在闭合图中。

简单的说,就是闭合图是一个点的集合,集合中任意点引出的边,那头的点也在这个集合中。也可以说,它可以是一个或多个连通块。

给每一个点一个点权,最大权闭合图是一个点权之和最大的闭合图。很好理解

下面是一个例子

images

这个图中,有9个闭合图(含空集):∅,{3,4,5},{4,5},{5},{2,4,5},{2,5},{2,3,4,5},{1,2,4,5},{1,2,3,4,5}

其中有最大权和的闭合图是{3,4,5},权和为4。

那么该如何求解呢?

我们构造一个源点S,汇点T。

我们将S与所有权值为正的点连一条容量为其权值的边,将所有权值为负的点与T连一条容量为其权值的绝对值的边,原来的边将其容量定为正无穷。

images

跑一下最大流,则最大权=正权和-最大流。

接下来就证明一下。

证明需要三个步骤【证明写得有点长和辣鸡,实在不想看就跳过吧

1.最小割为简单割

    先引入一下简单割的概念

    若一个 S−T 割满足割中的每条边只都与源或汇关联,称该割为简单割。

    所以,我们可以看出,本网络中的最小割为简单割:

    因为除S和T之外的点间的边的容量是正无穷,最小割的容量不可能为正无穷。所以,得证。

2.证明网络中的简单割与原图中闭合图存在一一对应的关系。(简单的说就是所有闭合图都是简单割,简单割也必定是一个闭合图)。

    证明闭合图是简单割:如果闭合图不是简单割(反证法)。那么说明有一条边是容量为正无穷的边,则说明闭合图中有一条出边的终点不在闭合图中,矛盾。

    证明简单割是闭合图:因为简单割不含正无穷的边,所以不含有连向另一个集合(除T)的点,所以其出边的终点都在简单割中,满足闭合图定义。得证。

3.证明最小割所产生的两个集合中,其源点S所在集合(除去S)为最大权闭合图。

首先我们记一个简单割的容量为C,且S所在集合为N,T所在集合为M。

则C=M中所有权值为正的点的权值(即S与M中点相连的边的容量)+N中所有权值为负的点权值的绝对值(即N中点与T中点相连边的容量)。记(C=x1+y1);(很好理解,不理解看上一个图或想象一下就明白了)。

我们记N这个闭合图的权值和为W。

则W=N中权值为正的点的权值-N中权值为负的点的权值的绝对值。记(W=x2-y2);

则W+C=x1+y1+x2-y2。

因为y1=y2,所以W+C=x1+x2;

x1为M中所有权值为正的点的权值,x2为N中权值为正的点的权值。

所以x1+x2=所有权值为正的点的权值之和(记为TOT).

所以我们得到W+C=TOT.整理一下W=TOT-C.

到这里我们就得到了闭合图的权值与简单割的容量的关系。

因为TOT为定值,所以我们欲使W最大,即C最小,即此时这个简单割为最小割,此时闭合图为其源点S所在集合(除去S)。得证。

所以,最大权=正权和-最大流。

例题 T2

3.最小路径覆盖

何为路径覆盖

路径覆盖:在图中找一些路径,这些路径覆盖图中所有的顶点,每个顶点都只与一条路径相关联。

何为最小路径覆盖

最小路径覆盖:在所有的路径覆盖中,路径个数最小的就是最小路径覆盖了。

由上面可以得出:

1.一个单独的顶点可以是一条路径;
2.如果存在一路径p1,p2,……pk,其中p1 为起点,pk为终点,那么在覆盖图中,顶点p1,p2,……pk不再与其它的顶点之间存在有向边.

对于一个路径覆盖,有如下性质:

1、每个顶点属于且只属于一个路径。
2、路径上除终点外,从每个顶点出发只有一条边指向路径上的另一顶点。

images

路径覆盖与二分图匹配的关系(必须是有向无环图):

最小路径覆盖=|G|-最大匹配数

其中最大匹配数的求法是

构造二分图,把原图每个顶点i拆分成二分图U,V集合中的两个顶点Ui和Vi。对于原图中存在的每条边(i,j),在二分图中连接边(Ui,Vj)。

然后把二分图最大匹配模型转化为网络流模型,求网络最大流。

最小路径覆盖的条数,就是原图顶点数,减去二分图最大匹配数。

images

这为什么是正确的呢

所以我们可以把每个顶点理解成两个顶点,一个是出发,一个是目标,建立二分图模型。该二分图的任何一个匹配方案,都对应了一个路径覆盖方案。

如果匹配数为0,那么显然路径数=顶点数。每增加一条匹配边,那么路径覆盖数就减少一个,所以路径数=顶点数 – 匹配数。要想使路径数最少,则应最大化匹配数,所以要求二分图的最大匹配。

注意,此建模方法求最小路径覆盖仅适用于有向无环图,如果有环或是无向图,那么有可能求出的一些环覆盖,而不是路径覆盖。

例题 T3 T4

4.不相交路径

何为不相交路径

定义一个有向图G的不相交路径是该有向图的一个路径集,且该路径集的所有的每条路径没有公共点。

其实根据字面意思理解就行了。。

这种题几种类型,有比较水的,直接求最大不相交路径数,还有的有点权,要求点权最大。

images

如何解这种题呢

为了限制经过次数,将每个点i拆成xi,yi.

1、从yi向xi连一条容量为INF的有向边(1<i<N),
2、从S向x1连一条容量为1的有向边,
3、从yN向T连一条容量为INF的有向边,
4、如果存在边(i,j)从xi向yj连一条容量为1的有向边.

求x1到yN的最大流.为最大的路径数

images

正确性如何证明呢?

中间连回的边限制了一个点只能选一次,因为是最大流,所以可以直接跑就行了。。。

如何记录路径长度?

可以直接在残量网络上跑。

如何让路径长度最长?

把连回的边加上1的费用,跑最大费用。

如果限制了路径个数?

限制S连的边的流量啊

如何有多个起点或终点?

和S或T多连几条边啊。。。

有点权?

把连回的边加上费用。

路径能在点上相交?

这就更简单了,直接在原图上,起点上加S,终点加上T,终点的加边流量为INF,原图的边流量为1。有点权的话,直接落到点的出边上。

正确性?

为了保证路径没有重叠,需要在相邻的两个点上限制流量为1,由于顶层的每个点只能用1次,S向顶层点流量限制也为1。

路径能在点和边上相交?

直接把原图边的流量改成INF即可。

例题 T6 T11 T16 T21 T22

4.最大独立集

何为独立集

独立集:在所有的顶点中选取一些顶点,这些顶点两两之间没有连线,这些点就叫独立集

何为最大独立集

最大独立集:在所有的独立集中,顶点数最多的那个集合

要求最大独立集的话,我们要先学一下最小顶点覆盖集,因为它们是互补的

何为最小顶点覆盖集

假如选了一个点就相当于覆盖了以它为端点的所有边。最小顶点覆盖就是选择最少的点来覆盖所有的边。

images

对于上面这个二分图,顶点分为左右两个集合,U集合包含1,2,3,4,V集合包含5,6,7,8,9。跑一下最大匹配

images

现在我们已经找到一个最大匹配M,就是上面的红线所标注的M={(1,7),(2,5),(4,8)}。

我们作如下定义:

(1)定义1、2、4、5、7、8为已经匹配过的点,其他点为未匹配的点;

(2)定义(4,8)、(1,7)、(2,5)为已匹配的边,其他边为未匹配的边。

下面我们从V集合中找出未匹配的点,就是上面标记的6和9。每次我们从右边选出一个未匹配的点,从该点出发, 做一条未匹配边->匹配边->未匹配边->……->匹配边(注意最后以匹配边结尾),并且标记用到的点,得到下图:

images

其中蓝色的边为我们刚才画的边,其中标记的点有2、4、5、6、8、9。 上图的两条路为:(1)9->4->8->2->5 (2)6->2->5。

这两条路都是未匹配边->匹配边->未匹配边->……->匹配边。(注意如果一个右侧未匹配点有多条边,那么这样的从该点开始的路径就有多条,上面的6和9都只有一条边,所以从每个点开始的这样的路径只有一条)。

现在我们将左侧标记的点2、4和右侧未标记的点7选出组成集合S, 那个S就是一个最小顶点覆盖集,就是S集合可以覆盖所有的边。下面证明:

(1)|S|=M,即最小顶点覆盖等于二分图最大匹配:左边标记的点全都为匹配边的顶点,因为我们构造路径的时候左边的点向右找的边都是最大匹配的边;右边未标记的点也为二分图最大匹配边的顶点。而且左边标记的加上有边未标记的正好是最大匹配的数目。

(2)S能覆盖所有的边。所有的边可以分为下面三种情况:

a、左端点标记、右端点标记;这些边一定被左侧标记的点覆盖,比如上面的2,4;
b、右端点未标记;这些边一定被右侧未标记的点覆盖,比如上面的7;
c、左端点未标记、右端点标记。

下面我们证明c这种边不会存在:若c是最大匹配中的边,由于右端点不可能是一条路径的起点(因为我们的起点都是从V集合中未匹配的点开始的),于是右端点的标记只能是在构造中从左边连过来,这是左端点必定被标记了,这时c就转化成了a;若c属于未匹配边,那么左端点必定是一个匹配点,那么c的右端点必定是一条路径的起始点,因此c的左端点也会成为一条路径的第二个点而被标记,这时c也就成了a。所以c这种边肯定是不存在的。

(3)S是最小的顶点集:因为最大匹配为M,而|S|=M,所以如果S中的点再少,那么连M个匹配的边都不能覆盖。

证明完毕。

我们可以回归正题了。如何求最大独立集?

images

最大独立集=所有顶点数-最小顶点覆盖

在上面这个图中最小顶点覆盖=3,即2,4,7构成最小顶点覆盖,则其他点6个构成最大独立集。且其他点不可能相连。

假设其他点相连则这条边必定没有被2,4,7 覆盖,与2,4,7是最小顶点覆盖矛盾。因此其他点之间必定没有边。而2,4,7是最小顶点覆盖,所谓最小就是不能再小了,因此我们的独立集就是最大了。非常好理解。

例题 T9 T24

后记

网络流是一种简介、明了的算法,非常的实用。

正如某神说的——当你看所有题都像网络流的时候,你就学成功了。


2 COMMENTS

  1. thchuan20012017-04-20 上午8:59

    你好,请问你这篇博客里的图片是怎么制作的呢?谢谢

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×