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

Posted on Edited on In Views:
二分图匹配，Hall 算法，最大流算法的扩展，网路流算法的应用

网络流 (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\) 中的球队