第 3 页输入定义内容输入是一个边加权有向图、一个源顶点 s、一个目标顶点 t。每条边有一个正容量capacity。物理含义这是一个有向图每条边除了方向外还携带一个double类型的容量值权重。容量代表这条边在单位时间内能通过的最大流量例如管道直径、电缆带宽、铁路运力。源点 ssource 是流量的起点汇点 t target是流量的终点。与最短路径的区别最短路径找的是两点间的一条最优路径最大流要找的是一组从 s 到 t 的流量分配使得总流量最大。图中边上的数字如 10、9、4、15、5、8、6、16 等就是容量。第 4 页st-割Cut的定义内容st-割是将顶点分成两个不相交集合的划分s 在一个集合 A 中t 在另一个集合 B 中。割的容量是从 A 到 B 的所有边的容量之和。物理含义这是一个划分动作把图中所有顶点分成两堆s 必须在 A 堆t 必须在 B 堆。割的容量只统计从 A 指向 B的边的容量之和。从 B 指向 A 的边不计入。页面示例S 单独在 A 中其余顶点在 B 中。从 S 到 B 的边有三条容量分别为 10、5、15。割的容量 10 5 15 30。割的物理意义如果把 A 和 B 看作两个区域割的容量代表“从 A 区流入 B 区的最大可能流量”因为流量只能沿边的方向走。第 5 页割的容量计算更复杂的划分内容展示另一个割A 包含 s 以及中间一列的两个顶点以及底部的顶点B 包含其余顶点。从 A 到 B 的边容量为 10、8、16。割的容量 10 8 16 34。右侧标注“dont count edges from B to A”不要统计从 B 到 A 的边。物理含义随着 A 集合变大从 A 到 B 的边会变少。但割的容量不一定变小因为剩下的边可能容量更大。这一页强调割的容量只与从 A 到 B 的方向有关。B 到 A 的边无论有多少条、容量多大都不计入。物理原因流是从 s 流向 t 的。如果你把 A 看作“已经过境的区域”那么流只能从 A 流向 B继续前进不能从 B 流回 A那意味着回流在割的容量计算中不计入因为割的容量是“前方通道的上限”。第 6 页最小 st-割问题Mincut内容定义最小 st-割问题找到容量最小的割。示例割的容量 10 8 10 28。物理含义在所有可能的划分中找到那个“从 A 到 B 的边容量之和最小”的划分。这个最小值就是 mincut。物理直觉如果每条边代表管道割代表管道的截面。mincut 就是所有可能截面中“总管道截面最小”的那个截面。任何从 s 到 t 的流都必须穿过这个截面所以流的大小不可能超过这个截面的总容量。第 7 页应用1950 年代内容冷战时期自由世界的目标切断苏联与东欧国家之间的铁路补给线如果冷战变成热战。展示的是 1999 年五角大楼解密的苏联-东欧铁路网络地图。物理含义铁路网络是有向图。顶点是车站/城市边是铁路容量是铁路的运输能力。切断裂铁路补给线的最小成本 找到最小割。这张图直观展示了 mincut 在地缘政治中的物理意义找到最薄弱的运输瓶颈用最小代价切断整个补给网络。第 8 页应用2010 年代内容当代应用政府切断与某些人的通信。展示 Facebook 的全球连接图。物理含义社交网络/通信网络是有向图。顶点是人/服务器边是通信链路容量是带宽。切断某人/某群人与外界的通信 找到围绕这些人的 mincut。这与第 7 页是同一个数学问题的不同物理载体把“铁路运输”换成“信息传输”。第 9 页输入定义重复内容与第 3 页相同重新展示图。物理含义无新信息用于引出后续的 flow 定义。第 10 页st-流Flow的定义内容st-流是给每条边赋一个流量值满足两个约束容量约束0 ≤ 边的流量 ≤ 边的容量。局部平衡除 s 和 t 外每个顶点的流入量 流出量。页面展示了一个流分配示例并计算了顶点 v 的流入和流出流入 5 5 0 10流出 10 0 10。物理含义流量是double值每条边有两个状态容量固定和流量可变。容量约束流量不能超过容量管道不能超载也不能为负不能逆流。局部平衡中间顶点不能“消耗”或“产生”流量。流入多少就必须流出多少。这是守恒定律。物理例外s 和 t 不受局部平衡约束。s 可以产生流量总流出 ≥ 总流入t 可以消耗流量总流入 ≥ 总流出。这一页是最大流问题的核心约束。后续所有算法都在寻找满足这两个约束的流量分配。第 11 页流的值内容定义流的值 t 点的流入量。页面展示了一个流t 的流入为 5 10 10 25。同时假设没有边指向 s也没有边从 t 指出。物理含义流的值是整个系统从 s 到 t 的净流量大小。因为局部平衡从 s 流出的总量 流入 t 的总量 流的值。“假设没有边指向 s 或从 t 指出”是一个简化假设。它保证 s 只有流出t 只有流入避免回边干扰值的定义。第 12 页最大 st-流问题Maxflow内容定义最大 st-流问题找到值最大的流。示例中流的值 8 10 10 28。物理含义在所有满足容量约束和局部平衡的流分配中找到总流量最大的那个。这个最大值就是 maxflow。物理直觉如何在不超载任何管道的前提下从 s 往 t 输送尽可能多的流量。第 13 页应用1950 年代maxflow 版本内容苏联的目标最大化向东欧输送补给。展示同一张铁路地图但这次是最大化流量。物理含义与第 7 页的 mincut 问题对偶mincut 是最小切断成本maxflow 是最大输送能力。在这张图上如果你要最大化补给流量你需要找到从苏联到东欧的最大流。第 14 页应用2010 年代maxflow 版本内容“自由世界”的目标最大化向特定人群的信息流。展示 Facebook 连接图。物理含义与第 8 页对偶maxflow 用于最大化信息传输mincut 用于最小化通信切断成本。同一个数学问题的两个方面。第 15 页总结内容输入加权有向图、源点 s、汇点 t。Mincut 问题找到容量最小的割。Maxflow 问题找到值最大的流。页面同时展示了一个流值 28和一个割容量 28。底部“Remarkable fact. These two problems are dual!”重要事实这两个问题是对偶的物理含义这一页是整个章节的核心引理maxflow 的值 mincut 的容量。这不是巧合而是一个数学定理Maxflow-Mincut Theorem。它表明你从 s 能输送到 t 的最大流量恰好等于任何割中最小的那个割容量。对偶性的物理意义任何一个流的值 ≤ 任何一个割的容量弱对偶。当两者相等时你同时找到了最大流和最小割。这个定理是整个 Ford-Fulkerson 算法和后续所有最大流算法的理论基础。