算法设计与分析.07.网络流 (3)

网络流 (3)

  • Network Flow

bipartite matching

  • \(G=(V,E)\) 的一个匹配 \(M\in E\),满足每个节点最多在 \(M\) 中出现一次
  • 最大匹配:\(\vert{M}\vert\) 最大的匹配
  • 二分图:能够将节点划分为两个部分 \(A,B\),只有 \(A,B\) 之间有边

max-flow

  • 转化为 max-flow 问题
    • 增加两个虚拟节点 \(s,t\),分别和两个部相连
    • 中间的权重设置为 1 也行

  • 匹配 \(M\) 和流量 \(f\) 一一对应
  • SB 定理
    • 单射 + 单射 = 双射
    • \(A\subseteq B\land B\subseteq A\Rightarrow A=B\)
  • FF 算法:\(O(mn)\)

完美匹配

  • 每个 \(G\) 中的顶点恰好都在 \(M\) 中出现 1 次
  • \(S\):节点子集

\[ N(S)=\{v:edge(w,v)\in E\land v\in S\} \]

Hall

  • 满足 \(\vert{L}\vert=\vert{R}\vert\) 的二部图 \(G=(V,E)\)\(V=L\cup R\)
    • \(G\) 存在完美匹配 \(\Leftrightarrow\) 对于任意 \(S\subseteq L\),都有 \(\vert{N(S)}\vert\ge \vert{S}\vert\)
  • 注意 Hall 定理的前提是二部图
  • \(\Rightarrow\)
    • 每一个点都需要匹配到不一样的点
  • \(\Leftarrow\)
    • 反证法
    • \(cap(A,B)=\vert{L_B}\vert+\vert{R_A}\vert\)
      • 从最小割的角度思考
      • 首先不会包含 \(\infty\) 的边,也就是说 \(A\) 只有可能有如下两种情况
        • \(A=\{s\}\)
        • \(A=\{s\cup V_1\}\),同时 \(V_1\)\(V-V_1\) 之间没有边
      • 再观察就看得出来上面的式子了
    • \(N(L_A)\subseteq R=R_A\cup R_B\)\(R\) 除去无穷边(连接 \(L,R\) 的边),即 \(R_B\)
      • 于是 \(R_B\) 中的点不在 \(N(L_A)\)

发展史

非二部图的匹配

  • 结构更加复杂
  • Blossom algorithm:\(O(n^4)\)
    • [Edmonds 1965]
  • Best known:\(O(mn^{0.5})\)
    • [Micali–Vazirani 1980, Vazirani 1994]

k-regular bipartite graph

  • 二部图,每个节点恰好都有 \(k\) 个相邻的点
  • every k-regular bipartite graph have a perfect matching
  • 证明
    • \(S\) 关联的边的数量 \(k\vert{S}\vert\)
    • \(N(S)\) 关联的边的数量 \(k\vert{N(S)}\vert\)
    • \(S\) 关联的边一定和 \(N(S)\) 关联
      • \(k\vert{N(S)}\vert\ge k\vert{S}\vert\)
      • \(\vert{N(S)}\vert\ge \vert{S}\vert\)
    • 根据 Hall,得证

disjoint paths

  • edge-disjoint paths:路径两两之间没有相同的边
    • 节点可以相同

Edge-disjoint paths problem

  • \(G=(V,E)\),给定点 \(s,t\),找出最多的边不相交的路径
  • 最大流模型:所有的容量都设置为 \(1\)
  • 正确性:证明双射
    • 路径 \(\Rightarrow\) 最大流:赋权即可
    • 最大流 \(\Rightarrow\) 路径:根据流守恒提取出 k 条路径

Network connectivity

  • 有向图删除几条边,才能让 \(s\) 不可达 \(t\)
    • 和上面一样的转化,求最小割

Menger’s theorem

  • The max number of edge-disjoint \(s\to t\) paths equals the min number of edges whose removal disconnects \(t\) from \(s\)
  • 路径 \(P_1,\cdots,P_k\)
  • 去除边集 \(\vert{F}\vert=l\)
  • \(\le\):每条路径至少使用了 \(F\) 的一条边
  • \(\ge\):最大流 \(\Rightarrow\) 最小割 \(\Rightarrow\) \(k\ge l\)

无向图

  • 最大流模型:每一条边 \(e(u,v)\) 转化为两条有向边 \(e(u,v),e(v,u)\),权重设置为 1
  • 存在最大流,使得对于任意一组反向边 \(e,e'\),满足 \(f(e)=0\lor f(e')=0\)
  • 证明
    • 若存在不满足条件的边,则都减去 \(\min\{f(e),f(e')\}\),此时 \(val(f')=val(f)\)
  • 正确性:证明双射
    • 路径 \(\Rightarrow\) 最大流:赋权即可
    • 最大流 \(\Rightarrow\) 路径:转化为 \(f(e)=0\lor f(e')=0\),然后再根据流守恒提取

Menger 定理

最大流扩展

多源多汇

  • 增加一个虚拟的源点、一个虚拟的汇点
  • 虚拟源点连接所有的源点,权重设置为 \(\infty\)
  • 接所有的汇点连虚拟汇点,权重设置为 \(\infty\)

顶点有需求

  • Circulation with supplies and demands

  • 看能否构建起流通
  • 增加虚拟的源点和汇点,边这么加

  • 能流通起来,当且仅当存在最大流 \(D\)
    • 只有把新加的边满起来了,才能满足流量限制

\[ D=\sum_{v:d(v)>0}d(v)=\sum_{v:d(v)<0}-d(v) \]

  • \(c(e),d(v)\) 都是整数,如果存在流通,则存在赋值全为整数的循环
    • max-flow
  • 不存在流通 \(\Leftrightarrow\) 存在一个划分 \((A,B)\),使得 \(\sum_{v\in B}d(v)>cap(A,B)\)
    • 需要的超过了能供给的
  • \(G'\) 中的割集 \((A,B)\),记作 \(cap'\)

\[ \begin{aligned} cap'(A,B) &=cap(A,B)+\sum_{v\in B\land d(v)<0}-d(v)\\ &<\sum_{v\in B}d(v)+\sum_{v\in B\land d(v)<0}-d(v)\\ &=\sum_{v\in B\land d(v)>0}d(v)\\ &\le\sum_{v\in V\land d(v)>0}d(v)\\ \end{aligned} \]

  • 不满足流通条件了

带下界+顶点有需求

  • Circulation with supplies, demands, and lower bounds

  • 把边的下界转换到点上

  • \(G\) 中有流通 \(f(e)\) \(\Leftrightarrow\) \(G'\) 中有流通 \(f(e)-l(e)\)

应用

Survey design

  • 求一个流通,注意 \(t\to s\) 的边

airline scheduling

  • 重用航班人员、飞机,很难的问题

  • 不考虑时间,二分求解流通问题

  • 时间复杂度:\(O(k^3\log k)\)
    • \(k\) 个航班
      • edge:\(O(k^2)\)
      • node:\(O(k)\)
    • \(\log k\) 次尝试
    • 每次 \(O(k^3)\)\(O(mn)\)
  • Can solve in \(O(k^3)\) time by formulating as minimum-flow problem

image segmentation

  • 前后景分割
  • 无向图
  • node:像素
  • edge:最多 4 个邻居像素
  • \(a_i\):像素为前景的概率
  • \(b_i\):像素为后景的概率
  • \(p_{i,j}\):penalty 当 \(i,j\) 一个是前景一个是后景
  • Goal

  • 转化为最小化问题

建模

  • 无向图转为有向图
  • s-j:\(a_j\)
  • i-t:\(b_i\)

  • 转变为最小割问题
  • Grabcut. [ Rother–Kolmogorov–Blake 2004 ]

project selection

  • 每一个工程需要财政 \(p_v\)(可正可负)
  • 若干限制:\(v\) 需要在 \(w\) 之前
  • 目标:满足限制条件下,最大化财政
  • 先驱图:\(w\)\(v\) 的先决条件 \(\Rightarrow\) edge(v,w)
  • 最小割模型

  • \((A,B)\) 是最小割 \(\Leftrightarrow\) \(A-\{s\}\) 是最优结果
    • 最小割不会选中 \(A\to B\) 的无穷边
    • \(A\to B\) 的边
      • \(s\to v,v\in B\)
      • \(v\to t,v\in A\)

\[ \begin{aligned} cap(A,B) &=\sum_{v\in B:p_v>0}p_v+\sum_{v\in A:p_v<0}(-p_v)\\ &=\sum_{v:p_v>0}p_v-\sum_{v\in A}p_v\\ \end{aligned} \]

  • 第一项为常数,第二项就是结果
  • 最小化就是最大化财政
  • 如何满足多个先决条件?
    • 如果只满足了部分先决条件,则会存在 \(A\to B\) 的无穷边
    • 算法保证不会出现这种情况

open-pit mining

baseball elimination

  • 判定冠军最有可能是谁
  • 信息:当前输赢信息,还需要和谁比几场
  • 发现:判定和如下信息有关
    • 当前输赢
    • 接下来要和谁打
  • 判断 4 是否还有机会胜利
    • \(w_i\):队 \(i\) 已经赢得的比赛数量
    • \(r_i\):队 \(i\) 还剩下的比赛数量
    • 队 4 如果接下来全胜,则赢得的比赛数量 \(w_4+r_4\)
    • 其他队应该都要比 \(w_4+r_4\)

  • s 出来的边都被饱和了 \(\Leftrightarrow\) 4 还有机会赢
    • 如果存在最大流,则说明比赛都比完了,而且满足了队 4 赢最多的要求

HR 定理

  • 在一个集合中,他们赢得的总数+内部还需要比赛的场数,如果他们算出来的平均胜利场数大于 \(w_z+g_z\),则该球队没戏了
  • \(\Rightarrow\):上面的说法
  • \(\Leftarrow\):max-flow
    • 最小割不包含无穷边
      • 比赛节点 \(x-y\in A\) \(\Rightarrow\) 球队节点 \(x,y\in A\)
    • max-flow
      • 球队节点 \(x,y\in A\) \(\Rightarrow\) 比赛节点 \(x-y\in A\)
      • 否则将其加进来之后能够增流 \(g_{xy}\)
    • 如果没戏,则最大流未满足 \(s\to\cdot\)

  • \(S\):球队
  • \(T^{\ast}\)\(A\) 中的球队