图论7-Network flows

Posted on

图论7-Network Flows

Matching

图$G$中的**极大匹配(**maximal matching)是指不能添加更多的边的匹配；最大匹配(maximum matching)是指图$G$中拥有最多边数的匹配；

  • 显然每个最大匹配都是极大的，反之未必；

给定匹配$M$，一个$M$-交替路径是指一个交替选择$M$中的边和不在$M$中的边的路径；一个$M$-增广路径是指其两个端点不被$M$浸润的$M$-交替路径；

  • 给定$M$-增广路径$P$，我们可以替换$M$中的边形成多一条的边的新的匹配$M’$;

对于定义在顶点集$V$上的图$G,H$,其对称差(symmetric difference)$G\triangle H$定义为顶点集为$V$，边集中的边只属于$G$和$H$其中之一的图,通常具有异或(exclusive-or)性质；

对于两个匹配$M,M’$，$M\triangle M’=(M-M’)\cup(M’-M)$;

对于二部图$G(V_1;V_2)$，一个完美匹配是指一个从$V_1$到$V_2$的一对一的对应关系使得每个具有对应关系的顶点都相邻；

结婚条件(Marriage condition)形象来说一组$k$个女孩d至少总共认识$k$个男孩；

Lemma

两个匹配的对称差的每个分量是偶圈或者路径；

proof：注意到$\Delta(F)\le 2,\chi’(F)=2$;

Theorem(Berge)

图$G$中的匹配$M$是最大匹配当且仅当$G$中没有$M$增广路径；

proof: 充分性显然，下证必要性，若$M$没有增广路径也不是最大匹配，取$G$中的最大匹配$M’$，令$F=M\triangle M’$，$F$只包含偶圈和路径，注意到$\mid M’\mid>\mid M\mid$，$F$必须包含一个分量是路径，其两个端点属于$M’$的边，这个路径就是$M$的增广路径，矛盾；

Theorem(Hall)

对于二部图$G(X;Y)$，存在$X$到$Y$的完美匹配的充分必要条件是对任意子集$S\sube X$，均有$\mid S\mid\le \mid N(S)\mid$;

proof:这说明结婚条件是充分必要的；必要性显然，下证充分性

取$G$中的最大匹配$M$,$M$没有浸润$X$,我们说明存在子集$S\sub X$使得$\mid N(S)\mid< \mid S\mid$;

取$u\in X$且$u$未被$M$浸润,取$u$通过$M$交替路径到达的所有点中在$X$的部分为$S$,在$Y$中的部分为$T$,注意有$u\in S$;

image-20250112155607024

  • 断言:$M$匹配$T$和$S-{u}$

    每个在$S-{u}$的顶点都可以通过$M$中的一条边到达$T$中顶点；$M$没有增广路径因此$T$中顶点都是浸润的，因此一个到达顶点$y\in T$的$M$交替路径也通过$M$的边到达$S-{u}$，因此有$\mid S-{u}\mid = \mid T\mid$

  • 由于$T\sube N(S)$，于是必有$T=N(S)$，故
    $$
    \mid N(S)\mid=\mid T\mid =\mid{S-{u}}\mid = \mid S\mid -1< \mid S\mid
    $$

由此证明了充分性；

也可以用归纳法证明；也可以使用Menger定理证明；

Corollary

对于$k$-正则的二部图有完美匹配；

proof:统计边数验证满足结婚条件；

Theorem(Konig)

二部图中最大匹配数等于最小点覆盖数；

proof:相互构造

image-20250112162708568

Flow

称两条从$u$到$v$的路径是边不相交的(edge-disjoint)，如果它们没有公共边；

称两条从$u$到$v$的路径是点不相交的(vertex-disjoint)，如果它们没有公共点；

考虑图$G$中不相邻的两个顶点$v,w$，$vw$断集(vw-disconnected set)指图$G$中的一个边集$E$，每条从$v$到$w$的路径包括$E$中的一条边；$vw$分离集(vw-seperated set)指图$G$中的一个点集$S$，每条从$v$到$w$的路径包括$S$中的一条点;

一个网络(network)$N$是一个带权有向图，每一条箭头$a$分配一个容量$c(a)$；

一个流(flow)$f$为每个箭头分配一个流量$f(a)$；

对于顶点$v$，定义流出量$f^+(v)$为离开$v$的箭头总流量，流进量$f^-(v)$为进入$v$的箭头总流量；

称一个流$f$是可行(feasible)，如果满足

  • 流量约束：对于每个箭头$a$，$f(a)\le c(a)$；
  • 守恒约束：对于每个顶点$v$，$f^+(v)=f^-(v)$;

零流显然是可行，定义流的净流量/值为在汇点$t$处
$$
f^-(t)-f^+(t)
$$
一个最大流是一个拥有最大净流量的可行流；

对于网络$N$中的流$f$，一个$f$增广路径(f-augmenting path)是一个从源点$s$到汇点$t$的路径$P$，在底图$G$中的边$e\in E(P)$满足如下性质：

  • 若$P$在$e$上同向，则$f(e)< c(e)$,定义$\epsilon(e)=c(e)-f(e)$;
  • 若$P$在$e$上反向，则$f(e)>0$,定义$\epsilon(e)=f(e)$;

称路径$P$的容忍度(tolerance)为
$$
\min_{e\in E(P)} \epsilon(e)
$$
一个$f$增广路径对应一个大值流，这样的定义确保了容忍度为正；

一个s/t割(source/sink cut)$[S,T]$由点集$S$出发的到点集$T$的箭头组成，$S,T$构成点集的划分；

源/汇割的容量${\rm cap}(S,T)$,是这些箭头的总容量；

一个最小割是指拥有最小总容量的割；

image-20250113154526967

Theorem(Menger)

连通图$G$中相异顶点$v,w$之间的边不相交路径最大条数等于$vw$不连通集的最少边数；

proof:显然后者不超过前者，只需证明前者不超过后者即可；

对边数归纳，考虑非平凡情况，假设图$G$中最小的$vw$不连通集$E$的边满足$\mid E\mid =k$

  • 不是所有的边和$v$相关联
  • 不是所有的边和$w$相关联

$G-E$有两个分别包括顶点$v,w$的不相交的子图$V,W$;

定义$G_1$为$G$收缩$V$中的每一条边形成的图，$G_2$为类似收缩$W$的每一条边形成的；由归纳假设，$G_1,G_2$给出$k$个边不相交的路径，所求的$k$个边不相交路径显然就是给出的路径的并；

对于平凡情况，可以假设$G$中每条边都在$E$中，否则可以删去它使用归纳假设，考虑$vw$间的最短路$P$，$P$包括至多一条边在$E$中；对$G-E(P)$采用归纳假设，至少有$k-1$条边不相交路径，算上$P$即可；

Theorem(Menger)

连通图$G$中相异顶点$v,w$之间的点不相交路径最大条数等于$vw$分离集的最少点数；

Corollary

对于图$G$是$k$-连通的当且仅当任意相异顶点之间有至少$k$条边不相交的路径；

对于至少有$k+1$个顶点的图$G$，$G$是$k$-连通的当且仅当任意相异顶点间至少有$k$个点不相交的路径；

值得一提的是，Menger定理对有向图也成立，因此一般表述成连通图中最大流等于最小割；手动添加两个顶点也可证明Hall定理；

Lemma

令$P$是$f$增广路径，具有容忍度$z$，通过以下方式改变流

  • $+z$:在与$P$同向的箭头上
  • $-z$:在与$P$反向的箭头上

形成的新可行流$f’$，其值${\rm val}(f’)={\rm val}(f)+z$

Theorem(Max-flow Min-cut)

在任意网络中，最大流的值等于最小割的容量；

proof:容量为整数情形时可以看作Menger定理视作有向图中连接对应容量个箭头；

只需要找到一个流值等于一个割流量即可；

取$f$为最大流，如下定义点集划分$S,T$：点$z\in S$当且仅当存在路径$v=v_0\to v_1\to \cdots \to v_{m-1}\to v_m = z$使得$\epsilon(v_iv_{i+1})>0$或$\epsilon(v_{i+1}v_i)=f(v_{i+1v_i})>0$

由引理,源点$s\in S$,汇点$t\in T$;显然对每个$(x,z)\in [S,T]$,有$\epsilon(xz)=0$,对于每个$[z,x]\in [T,S]$，我们有$f(z,x)=0$，否则$z$应该属于$s$;

因此有
$$
{\rm cap}([S,T])={\rm val}(f)
$$
$[S,T]$是所求的最小割；

Algorithm(Ford-Fulkerson)

image-20250113171531290