作业反馈3-12 TC 26.2-10， 26.2-13    Problem 26.1  26.2

能否能在查找最大流的同时， 直接找到这些paths？ Ford-Fulkerson Edmonds-Karp 都不行 由于一张图最多就|E|条边,因此 序列的势不大于|E|,因此我们可以用最多不大于E的增广路径序列得到最大 流.

求最大流算法 基本思路 反复查找是否存在f可增路P 如果存在,沿P则更新当前流f 否则f即为最大流 查找f可增路P Y P=null? N 𝑓 𝑎 = 𝑓 𝑎 +Δ𝑓 𝑃 ,𝑎为𝑃的正向弧 𝑓 𝑎 −Δ𝑓 𝑃 ,𝑎为𝑃的反向弧 𝑓 𝑎 , 𝑎不在𝑃上 返回当前流f

Ford-Fulkerson标号算法 𝑙 𝑣 实际表示的是x经过当前所查找的 一条路P到达v可能的最大流量 给定网络N,求N的一个最大流 0.初始化: ∀𝑎∈𝐴,令𝑓 𝑎 =0;//初始流量为0 1. 𝑙 𝑥 =∞;𝐿= 𝑥 ;𝑆=∅//L表示已标未查集,S表示已标已查集 2.while(𝐿≠∅) 从𝐿中任意取一个节点𝑢, 对所有𝑣∈𝑁 𝑢 −(𝐿∪𝑆)： 如果𝑎= 𝑢,𝑣 ∈𝐴且𝑐 𝑎 >𝑓(𝑎),则给𝑣标号： 𝑙 𝑣 = min 𝑙 𝑢 ,𝑐 𝑎 −𝑓 𝑎 ;𝐿=𝐿+{𝑣} 如果𝑎= 𝑣,𝑢 ∈𝐴且𝑓 𝑎 >0,则给𝑣标号： 𝑙 𝑣 = min 𝑙 𝑢 , 𝑓 𝑎 ,𝐿=𝐿+{𝑣} 𝐿=𝐿− 𝑢 ;𝑆=𝑆+{𝑢}//u处理完毕 if 𝑦∈𝐿，则存在f可增路, break： 3. if 𝑦∈𝐿(存在f可增路) 顺延标号更新流f 转第1步 4.if 𝐿=∅不存在f可增路;流f为最大流且 𝑆, 𝑆 为最小割, 返回f (𝑢,+,𝑙(𝑣)) (𝑢,−,𝑙(𝑣)) 更新f： 1. 令z=y 2. 如果z的标号为 𝑤,+,𝑙 𝑧 ,令𝑓 𝑤,𝑧 =𝑓 𝑤,𝑧 +𝑙(𝑦); 如果z的标号为 𝑤,−,𝑙 𝑧 ,令𝑓 𝑧,𝑤 =𝑓 𝑧,𝑤 −𝑙(𝑦); 3. 如果𝑤≠𝑥,令𝑧=𝑤并转2;

Ford-Fulkerson标号算法 复杂度𝑂(𝜀𝑣 𝑐 𝑚𝑎𝑥 ) 不仅依赖于问题规模𝜀,𝑣,还依赖一个参数 𝑐 𝑚𝑎𝑥 反复查找是否存在f可增路P 如果存在则更新当前流f 否则f即为最大流 x v1 v2 y m 1

Edmonds-Karp算法 𝑂( 𝜀 2 𝑣) 广度优先遍历,找最短f可增路 给定网络N,求N的一个最大流 0.初始化: ∀𝑎∈𝐴,令𝑓 𝑎 =0;//初始流量为0 1. 𝑙 𝑥 =∞;𝐿= 𝑥 ;𝑆=∅//L表示已标未查集队列,S表示已标已查集 2.while(𝐿≠∅) 从𝐿取第一个节点𝑢, 对所有𝑣∈𝑁 𝑢 −(𝐿∪𝑆)： 如果𝑎= 𝑢,𝑣 ∈𝐴且𝑐 𝑎 >𝑓(𝑎),则给𝑣标号：𝑙 𝑣 = min 𝑙 𝑢 ,𝑐 𝑎 −𝑓 𝑎 ;𝐿= 𝐿+{𝑣} 如果𝑎= 𝑣,𝑢 ∈𝐴且𝑓 𝑎 >0,则给𝑣标号：𝑙 𝑣 = min 𝑙 𝑢 , 𝑓 𝑎 ,𝐿=𝐿+{𝑣} 𝐿=𝐿− 𝑢 ;𝑆=𝑆+{𝑢}//u处理完毕 if 𝑦∈𝐿，则存在f可增路, 进行以下操作： 顺延标号更新流f 转第1步 4. 𝐿=∅不存在f可增路;流f为最大流且 𝑆, 𝑆 为最小割, 返回f 𝑂( 𝜀 2 𝑣) 广度优先遍历,找最短f可增路 (𝑢,+,𝑙(𝑣)) (𝑢,−,𝑙(𝑣)) 更新f： 1. 令z=y 2. 如果z的标号为 𝑤,+,𝑙 𝑧 ,令𝑓 𝑤,𝑧 =𝑓 𝑤,𝑧 +𝑙(𝑦); 如果z的标号为 𝑤,−,𝑙 𝑧 ,令𝑓 𝑧,𝑤 =𝑓 𝑧,𝑤 −𝑙(𝑦); 3. 如果𝑤≠𝑥,令𝑧=𝑤并转2;

网络的割 定义 给定一个单源单汇网络 𝑁 𝑉,𝑥,𝑦,𝐴,𝐶 𝑆⊆𝑉, 𝑆 =𝑉−𝑆 𝑆, 𝑆 ={ 𝑢,𝑣 |𝑢∈𝑆,𝑣∈ 𝑆 } 𝑆, 𝑆 ={ 𝑢,𝑣 |𝑢∈𝑆,𝑣∈ 𝑆 } 如果𝑥∈𝑆∧𝑦∈ 𝑆  𝑆, 𝑆 为网络N的 一个割 割的容量𝐶𝑎𝑝 𝑆, 𝑆 ： 𝑪𝒂𝒑 𝑺, 𝑺 = 𝒂∈ 𝑺, 𝑺 𝒄(𝒂) S S x y

割的示例 S t v1 v2 v3 v4 8 3 6 5 𝑺={𝒔}? 𝑺, 𝑺 ={ 𝒔,𝒕 , 𝒔, 𝒗 𝟏 , 𝒔, 𝒗 𝟐 } 𝑺={𝒔, 𝒗 𝟏 , 𝒗 𝟐 }? 𝑺, 𝑺 ={ 𝒔,𝒕 , 𝒗 𝟏 , 𝒗 𝟑 , 𝒗 𝟏 , 𝒗 𝟒 , 𝒗 𝟐 , 𝒗 𝟑 , 𝒗 𝟐 , 𝒗 𝟒 } S t v1 v2 v3 v4 8 3 6 5 Y Y 𝐶𝑎𝑝 𝑆, 𝑆 =8+5+6=19 𝐶𝑎𝑝 𝑆, 𝑆 =5+3+3+3+6=20 𝑺={ 𝒗 𝟏 , 𝒗 𝟐 }? 𝑺, 𝑺 ={ 𝒗 𝟏 , 𝒗 𝟑 , 𝒗 𝟏 , 𝒗 𝟒 , 𝒗 𝟐 , 𝒗 𝟑 , 𝒗 𝟐 , 𝒗 𝟒 } S t v1 v2 v3 v4 8 3 6 5 S t v1 v2 v3 v4 8 3 6 5 N Y 𝑺={𝒔, 𝒗 𝟏 }? 𝑺, 𝑺 ={ 𝒔,𝒕 , 𝒗 𝟏 , 𝒗 𝟑 , 𝒗 𝟏 , 𝒗 𝟒 , 𝒔, 𝒗 𝟐 } 𝐶𝑎𝑝 𝑆, 𝑆 =3+3+5+6=17

? 2 1 3 2 实际 1 𝐸 就足够小了！

b) Describe an efficient algorithm to solve the escape problem, and analyze its running time. 每个空白点拆分为两个节点（容量控制1） 每个起点作为一个源点,边界点作为汇点 每个点和边的capacity均为1 这是一个多源点的最大流问题 利用各种最大流求解算法求解最大流 最后只要查看最大流是否等于原点个数即可,如 果等于就可以,小于就不行.

原图中最小路径覆盖=|𝑽|−二部图的最大匹配数 有向无环图 将原图中所有节点i拆成 𝑥 𝑖 , 𝑦 𝑖 如果在原图中有边(𝑖,𝑗)那么我们添加边：( 𝑥 𝑖 , 𝑦 𝑗 )且容量为无穷大， 这样我们得到一个二部图 添加一个 super source S 和 a super sink T ，将S与所有 𝑥 𝑖 连接，并将所有 𝑦 𝑖 链接到 T，这些边的容量都为 1。 计算新图中 S 到 T 的最大流 M。M 同时也是二部图的最大匹配。 由于 原图中最小路径覆盖=|𝑽|−二部图的最大匹配数，所以我们要的最小路径覆盖就是|V|-M 证明： 原图中最小路径覆盖=|𝑽|−二部图的最大匹配数 一开始在原图中每个点都是独立的为一条路径，总共有|V|条不相交路径。 每次在 二分图里找一条匹配边就相当于在原图中把两条路径合成了一条路径，也就相当于路径数减 少了 1。 所以找到了几条匹配边，路径数就减少了多少。 所以有最小路径覆盖=原图的结点 数-新图的最大匹配数

b. Does your algorithm work for directed graphs that contain cycles b. Does your algorithm work for directed graphs that contain cycles? Explain.