�
FEIT EDUCATION
‘6��.Q:�
Week 8 Asm 梳理班 – COMP3027
by
Jeff老师
Table of Contents
学习目的： ………………………………………………………………………………………………………………. 1
网络流的概念梳理…………………………………………………………………………………………………….. 2
最大流算法的复杂度 ………………………………………………………………………………………………………….4
最大流网络题型 …………………………………………………………………………………………………………………5
NF 的证明步骤（重要） …………………………………………………………………………………………… 4
Asm2 Q1 思路 …………………………………………………………………………………………………………… 7
Asm2 Q2 思路 …………………………………………………………………………………………………………. 10
report 要求总结 …………………………………………………………………………………………………………………………..10
学习目的：
NF 算法梳理
• 如何找 max flow == min cut, 几种算法
• 如何证明两个命题互相可以转化 (我们的重点)
• 实际上是在求 max flow 求解的几类问题之证明
最大流网络题型拓展
• Bipartite Graph Matching 二分图匹配
• Stable marriage 完美匹配
• Edge Disjoint Path
• Network Connectivity
Asm3 思路解析
Asm3 证明框架梳理
网络流的概念梳理
网络流(Network flow)是啥？
比喻：有一个自来水管道运输系统，起点是 s，终点是 t，途中经过的管道都有一个最
大的容量，可以想象每条管道不能被水流“撑爆”。求从 s 到 t 的最大水流量是多少？
网络流问题里一定有一个 Graph, 由 directed edge 和 node 组成. 一个每条边都有容量
(capacity)的有向图(directed graph)上分配每条路的流量(flow)，使一条边(edge)的 流量
不会超过它的容量, 并且于每个 node, 必须符合一个结点的进出的流量相同的限制，除
非这是一个源 点(source)或是一个汇点(sink)。
假设 G = (V,E) 是一个有向图，它的每条边 (u,v) ∈E 都有一个大于等于 0 的 capacity
c(u,v).
对于所有除了 S 和 t 的 Node u 和 v 都有以下特性:
• 容量限制(Capacity Constraints): f(u,v)≤c(u,v) 一条边可以经过的 flow 不能超过它
的 capacity。
• 流量守恒(Flow Conservation): 除非 u = s 或 u = t，否则中间结点的流入等于流
出。 以这个简单图为例, 2 这个 Node 有两个进入的 flow, 分别是 4 和 1, 所以从
它出去的 flow 必须是 5
为什么 max flow = mincut？
最大流(maxflow)问题就是，给定一个流网络 G，一个源节点 s，一个汇点 t，我们希望
找到值最大的一个 flow。
Min cut 的概念:
Cut 定义: 一个 s-t 的 Cut C = (S, T) 把 所有的结点集合 V 分成两部分 S 和 T，其中源节
点 s ∈ S, 汇点 t ∈ T.
为什么 max flow 小于等于 min cut 呢?
对于任意一个 cut, 通过的 flow 等于 v(f) = 𝑓out(𝑆) − 𝑓𝑖n(𝑆) (S 代表了包括 source 的这半
边)
因为𝑓𝑖n(𝑆)可能是 0 (考虑只有 Source 一个 node 的 cut set S)
所以, 由 S 到 t 的任意一个 cut 的 edge 的 capacity 上限, 就是整个 network 里 flow 的上限. v(f)≤
𝑐ap(𝑆, 𝑇)
最大流算法的复杂度
最常用: Ford Fulkerson 方法, 不叫算法是因为它有好几种 implementation。
• 残留网络(residual capacity)：容量网络 – 流量网络 = 残留网络
• 增广路径(augmenting path): 这是一条不超过各边容量的从 s 到 t 的简单路径，向
这个路径注入流量，可以增加整个网络的流量。我们称在一条增广路径上能够
为每条边增加的流量的最大值为路径的残余容量，cap(p) = min{cap(u,v) : (u,v)∈
路径 p}
• 割：用来证明 “当残留网络中找不到增广路径时，即找到最大流”，最大流最小
切割定理.
图 3 中黑色就是 residual graph 的反向边， 红色是 augmenting path
runs in O(mF) time
m 是 graph 里有几个 edge
F 是 source node 的 outgoing edges 的 capacity 之和.
此算法具体的实现不太可能考, 并且往届也没有要求 implement 最大流算法的实现, 大
家有空再熟悉即可.
有一个很好用的网站, 专门讲 Ford Fulkerson 算法的, 可以让大家放自己的模型进去算,
还会带大家一步一步 过这个算法:
https://www-m9.ma.tum.de/graph-algorithms/flow-ford-fulkerson/index_en.html
NF 的证明步骤（重要）
对于转化问题的证明分两步:
1. 证明若原问题为 True, 则目标问题为 True
2. 证明若目标问题为 True, 原问题也为 True
最大流网络题型
Bipartite matching 二分图匹配
什么是二分图(bipartite graph):
比如有一群男生, 一群女生, 每个人可以有许多选择去匹配对方群体中的人, 但是最终至多只能
匹配对方群 体中的一个人.
另外的例子滴滴打车如何配对乘客, 猎头如何找到找工作的人, 之类. 一旦是排他性的匹配(只能
配对方群体 中的人, 并且只能一个配一个), 二分图是一个很好的模型.
问题转化过程:
已知一个 bipartite graph, 就是这些信息已经给了 – 哪些 node 可能潜在匹配哪些对方的 node.
这个例子里我们给左边的 node 起名字叫 L, 右边叫 R.
我们先给这个图加一对 source 和 sink.
对于所有 L, 我们连一个 capacity 为 1 的 edge 到 source; 对于所有 R, 我们也连一个 capacity 为 1
的 edge 到 sink. 至于 L 和 R 中间的这些选择 node, 我们也都设置成 1, 并且我们很清楚最终这
些 edge 只会有部分会通 过 flow.
为什么要如此设定 capacity 呢? 因为从任意一个 L 到任意一个 R, 我们希望最多有一个 flow 通
过, 代表了一 个 match 可以发生. 所以只能最多让一个 flow 从 source 进到一个 L node, 也最多
让一个 flow 从一个 R node 回到 sink.
对于这个新图求 max flow, maxflow 的值就是原图里最多能匹配的值. 如何匹配, 就看这个
maxflow 选中了哪 些 edge 使经过它的 flow 不为 0.
Perfect matching 完美二分图匹配
和上面的问题非常相似, 不过 perfect matching 是问一个是与否的问题:
给定一个 bipartite graph (已知 L, R, 每个 L 的偏好), 是否可以让所有的 L 都一一配对到 R?
很显然要求是 L 的个数必须等于 R, 否则绝对是不存在一一匹配的 (pigeon hole principle). 当然,
我们完全可以用刚才的结论, 只要看看 max flow 是不是等于 |L| 就好了
我们需要掌握的一个结论是:
如果存在 perfect matching 的话, 对于任意一个 subset, subset 的可匹配对象数目必须大于这个
subset 的大 小.
举个例子理解: 无论总的男生女生群体有多大, 如果存在某三个男生只喜欢某两个女生, 最后肯
定至少有一 个单身狗.
Edge Disjoint Path
有多少完全不重复的路线可以从某点(S)走到另一点(t)呢?
问题转化:
直接把每个 edge 都给 1 个 capacity, run max flow.
证明:
• 假如有 k 个完全不重复的路线, 我们标记在任意一个 path 里用到的 edge 为 1 个 flow, 没
用到的为 0 个 flow. 那因为从 s 到 t 有 k 条路, 显然从 s 出去的 flow 一定是 k 个, 也就是
max flow.
• 假如新图里 max flow 是 k, 那沿着 flow 选中为 1 的路走来描绘路线, 可以保证没有两条
flow 用了同 一个 path(因为 capacity 上限是 1), 所以有 k 个完全不重复的路线.
另外一些常用的转化问题小技巧 (tutorial 里介绍的)
1. 如果是 undirected graph 想知道 maxflow/mincut 怎么办? 创一个新图, 让每个 undirected
graph 的边变成两条方向相反的, 和原图 capacity 一样的边. 然后一样算.
2. 如果不仅仅是 edge, 连 node 都有通过的 flow 上限怎么办? 把一个有 capacity 限制的
node 变成两个 node, 用一个 capacity 为这个上限的 node 相连, 然后一样算.
Asm2 Q1 思路
证明步骤：写清楚状态，转移方程，0 号问题，结果，证明方程正确性。
记住代码和图一定不能直接用。(因为你需要 启发式学习 + 查重 0 容忍)
理解后改命名，改语法方式。
Description 例子：
思路：MF 比 G 好？
可能：最短路径去掉之后破坏了其他路径，减少了 number of paths。
构造：要想短路导致断路，故意构造两个长路径，再构造一条短路破坏两条路径。
Try and Error time
解答步骤：
1. 画出反例 H，给出 S will be the set of edge-disjoint paths output by the algorithm.
2. 描述反例 H 执行 G 得到的每条路径。
3. 给出 optimal = H 执行 by MF。画或描述。
画图推荐工具：
Finite State Machine Drawer
http://madebyevan.com/fsm/
http://madebyevan.com/fsm/
Lucid Chart
https://lucid.app/
效果：
https://lucid.app/
Asm2 Q2 思路
report 要求总结
• 语言要简洁，点到为止。Recurrence 尽量用图或数学表达式证明，
correctness of Recurrence 稍微多说一点。
• 2 页最好，不能超过 4 页。
• 一定不能迟交。
• 结构完整，逻辑清晰，语言通顺。
例：
1. Describe how you transform the grid A into a max flow decision problem. You need to describe the
flow network G and the target value L of your max flow decision problem.
2. Prove the correctness of your reduction. You need to prove the following two statements:
• If the max flow in G is at least L, then A is winning.
• If A is winning, then the max flow in G is at least L.
(c) Prove the time complexity of your entire algorithm, considering the time taken to compute G and L, and to
solve the max flow decision problem. Make sure you state which max flow algorithm you use to solve the max
flow decision problem, and that your time complexity is in terms of n, the side length of the grid A.
套用到 Q2 上：
1. Describe how you transform the Edge Direction Problem into a Max Flow Decision Problem. You
need to describe the flow network H and the target value L of your max flow decision problem.
如何 creates G，add s, t, add 每个 vertex，add 每个 edge with capacity 1.
2. Prove the correctness of your reduction. In particular, you need to prove the following two statements:
(a) If the max flow in H is at least L, then it is possible to direct the edges so that the resulting directed
graph has in-degree at most B.
证明当 ED 为 YES 则 MF 一定为 YES。
(b) If it is possible to direct the edges so that the resulting directed graph has in-degree at most B, then
the max flow in H is at least L.
证明当 ED 为 YES 则 MF 一定为 YES。
3. Prove the time complexity of your entire algorithm, taking into account the time taken to compute H
and L, and to solve the max flow decision problem. Make sure you state which max flow algorithm you
use to solve the max flow decision problem, and that your time complexity is stated in terms of G and
B.
照搬 FF 方法 runs in O(mF) time
m 是 graph 里有几个 edge
F 是 source node 的 outgoing edges 的 capacity 之和.
1是关键
2是容易失分的点
3是送分点
如何转换呢 构造！
中间怎么连呢？
如果我们链接 wv 去掉 vw
一旦画不成 indegree < B ,肯定没法完成 at least m。 可想而知 什么是 L呢 注意 in + out = 2m，in = out L = m 学习目的： 网络流的概念梳理 最大流算法的复杂度 NF的证明步骤（重要） 最大流网络题型 Asm2 Q1思路 Asm2 Q2思路 report要求总结