计算机问题求解 – 论题3-13 - 最大流算法 2018年12月4日

Lucky Puck Company’s Trucking Problem Lucky公司生产冰球，其工厂在温哥华，仓库在温尼泊。公司委托物流公司运输。物流公司经营固定线路网，可能经过多个中间城市。分配给Lucky公司的任意两个城市间的最大运输量是固定的。如果Lucky公司是按运输量确定生产量，它如何计划它每天最大产量？ 问题1： 如何建立解决这个问题的模型？ 公司只关心每天最多可以生产多少,每天温尼泊能收到多少?

问题2:运输方案有多种,最优方案是什么? 图中的方案是最优的吗?

问题3： 如果工厂与仓库都不止一 个，该怎么办？

A Model of Oil Supply 17 16 18 a f g S 20 60 D 20 30 12 17 12 10 15 c supplying capacity cosuming capacity 16 18 a f g S 20 60 D 20 30 12 17 12 10 15 c e h 20 7 20 b d i Vertices: a, b: refineries g, h, i: markets others: relays 13 30 pipeline, with max capacity/week 17

严格的数学模型 容量限制 流量守恒：除了源节点和汇节点，所有节点流入和流出的都抵消。

问题4: 什么叫一个flow的“value”? 什么是最大流问题? |f| = 从源节点流出的总流量 - 流入源节点的流量（一般为0） 最大流：给定G、s、t，希望找到值最大的一个流。 什么是最大流问题?

How to get the maximum flow? 6 5 4 3 2 1 7

How to get the maximum flow? 6 5 4 3 2 1 2/7 2/5 2/6 在现有网络中，找到一条增广路径，然后将其提升到最大值。

Path1 in N 2/6 2/5 2/7 1 4 5 6 Value of flow increased by 3 1 4 5 5/6 5/5 6 5/7 Properly oriented

How to get the maximum flow? 5/5 4 5 5/6 5/7 1 2 6 4 5 2 3 5

Path2 in N 4,0 5,0 5,0 1 2 3 6 Value of flow increased by 4 1 2 3 4,4 5,4 6 Properly oriented

How to get the maximum flow? 5/5 4 5 5/6 5/7 1 2 6 4/4 4/5 2 3 4/5 No other path?

Path3 in N 5/6 0/2 4/5 1 4 3 6 Value of flow increased by 1 1 4 3 6/6 1/2 6 5/5 Properly oriented

No other path! 5/5 4 5 6/6 5/7 1 1/2 6 4/4 5/5 2 3 4/5 Find all the path and increase its flow value to the max!

找到所有的augmenting path是方法的关键所在!

再看这个流网络中的流f： 当前流f下的残存运力Cf 当前流f下的残存网络Gf 6 4 5 4 5 1 6 1 6 2 3 2 3 5/5 4 4/5 4/4 5/7 5/5 5/6 当前流f下的残存运力Cf 6 6 5 4 3 2 1 6 5 4 3 2 1 当前流f下的残存网络Gf

借助残存运力/网络概念，再看上述寻找过程 6 5 4 3 2 1 7 6 5 4 3 2 1 6 5 4 3 2 1 6 5 4 3 2 1 6 5 4 3 2 1 Over？

6 5 4 3 2 1 7 6 5 4 3 2 1 f‘对f的增广 6 5 4 3 2 1

证明要点： 1，证明函数是一个流：符合流的两个特性 2，证明

我们找到的方法一定正确吗？ 问题出在什么地方？ 这种决策在增广流过程中能保证不出现吗？ 这是最大的流了吗？ 我们有办法还是在“残存”模型中“纠正”这个错误吗？ 11/16 12/13 1/4 12/12 11/14 0/9 7/7 4/4 19/20 No！

residual capacity 问题5：我们为什么要如此定义residual capacity?

Residual Network 残存网络中找不到源到目的地的路径，所有增广路确定全部找到？

增广结果是G的一个新的流，更大的流；

证明要点： 1，证明函数是一个流：符合流的两个特性 2，证明

S V2 V1 T

增广路径 问题7：如果在residual network中发现了一条s,t路径， 是否一定可以将流网络中的流进行扩大？ 能否找到？ 残余能力是否一定大于0？ 最小的残余能力是否一定可以被利用？ 问题7：如果在residual network中发现了一条s,t路径， 是否一定可以将流网络中的流进行扩大？ 问题8：If not，是否意味着最大流已经出现？

答案是肯定的：

问题10：任意的流值，都不会超过任意的割容量? 6 5 4 3 2 1 7

流网络的割 问题9：任何一个割的净流量是否一定等于f的值？

Yes： 证明： 流量守恒 所有由S中节点发出的流的和 减去 所有进入S中节点的流的和 其中，S中节点发给S中其它节点的流和 等于 S中节点收到的S中其它节点发出的流和 因此才有书中证明结束前第二个刮号内的值是0.

f(x,y)重复出现，结果为0 S和T是V的划分

任意割的净流量一定小于割容量

证明要点：找不到增广路径时，残存网络必定将网络进行了切割，这个切割的容量恰好就是这个流的值 T T S S

如何设计该方法的实现算法？ 算法的正确性已经证明，但其效率取决于s-t路径的探知

Labeling Algorithm (Ford & Fulkson) General Scenario: Residual capacity: ei,j=Ci,j-Fi,j ei,j=Fj,i if Fj,i>0 6 5 4 3 2 1 e1,4 e3,6 e2,5 e2,3 e2,4 e4,5 e5,6 e4,2 e6,3 e3,2 e2,1 e6,5 e4,1 e5,2 3 4 2 2 4 3 5 3 edges in N Ci,j is the capacity of edge (i,j) Fi,j is the flow on edge (i,j) edges in s(N), but not in N

Chatty tenants and the cloud network sharing problem [NSDI'13] Preliminaries Multi-tenant Datacenters: Public/Private cloud datacenters Tenants: users renting virtual machines Requirements for network sharing [FairCloud, SIGCOMM’12] Req. 1: Min Bandwidth Guarantee Tenants want predictable performance/cost Req. 2: High Utilization Utilize sparse resource as much as possible Req. 3: Proportionality Not all flows are equal; some pay more

Prevalent of inter-tenant traffic Inter-tenant traffic leads to richer communication pattern and makes minimum bandwidth guarantee harder! When new tenants arrive, how to deploy their VMs to ensure their Min Bandwidth Guarantee and each physical link is not over-used? A max-flow approach

Bpmin : min bandwidth guarantee for each VM of tenant p. Bpinter : min bandwidth guarantee between tenant p and all the other tenants. All dashed edges in the right figure have infinity capacities. Applying a max-flow algorithm to the right figure can examine whether the total traffic (the max-flow value) exceeds the capacity of the physical link.

工作分配问题 问题表述 一个机构有m个工作位置,有n个申请者。每个申请者适合位置中的一部分。 是否有可能给每个申请者安排合适的位置？ 如果不能，最多可以安排多少人？ 怎么安排？

Matching G上的最大匹配 s1 b1 s1 b1 s2 b2 s2 b2 s3 b3 s3 b3 s4 b4 s4 b4 s5 b5

用网络流来解两步图最大匹配问题 s1 b1 y x s2 b2 s3 b3 s4 b4 Labeling algorithm for max flow is used in the network to compute the matching s5 b5 with each capacity set to 1

Hall’s Marriage Theorem Let R be a relation from A to B. Then there exists a complete matching M if and only if for each XA, |X||R(X)|

Open topics: 1,写出标号算法。用标号法求解以下流网络的最大流 1 7 2 3 4 5 6 2,利用最大流算法，证明hall定理

课外作业 TC Ex.26.1: 1, 2, 6, 7 TC Ex.26.2: 2, 6, 8, 10, 12, 13 TC Ex.26.3: 3 TC Prob.26: 1, 2

Hall’s Marriage Theorem Let R be a relation from A to B. Then there exists a complete matching M if and only if for each XA, |X||R(X)| Proof:  Obviously  |A| = n add supersource and supersink, if max flow value is |A|, then we get it. If min cut has value |A|, we get it.

Hall’s Marriage Theorem Suppose K is a minimal cut. We can consider all edges in K as in three sets: S1: those begin at supersource; |s1|=m S2: those correspond to pairs in R; S3: those end at supersink. s1 s2 s3 x y A B

Hall’s Marriage Theorem Remove S1: |A1| = m s1 s2 s3 x y B2 = R(A2) |A2| = n-m K is the min cut, No edges in K begin from A1 保留A1到B中的一条边并不会导致X和Y的连通。 |B2| >= |A2| = n-m precondition If m = n, s1=n, we get it X通过A2集合元素至少和n-m个B2元素相连

Hall’s Marriage Theorem Remove S2: suppose |S2| = r |S1|=m X至少和n-m 个B2元素相连 s1 x y s2 s3 S3如果还有边，X和Y就一定相连。 if |S3|=0, |S2| = n-m, |K|= |S1|+|S2| = n X is still connected to at least (n-m)-r elements of B if |S3|>0

Hall’s Marriage Theorem K is a min cut: X is still connected to at least (n-m)-r elements of B |S3| >= (n-m)-r s1 s2 s3 x y |K| = |S1|+|S2|+|S3| >= m + r+ n-m-r = n

Proof of Hall’s Theorem: |K| >= n, So, the following greens is one of the min cut. So , the following reds is one of the complete matching x y