图的流与网络 1. 基本概念 图的流（flow）是定义在有向图上的函数，为每条边分配一个数值，满足特定约束条件。典型场景是 网络流 （network flow），其中图表示传输系统（如水管、道路），边权代表容量（capacity）。核心要素包括： 源点 （source）：流的起点（记为 \( s \)）。 汇点 （sink）：流的终点（记为 \( t \)）。 容量函数 \( c(e) \)：每条边 \( e \) 允许的最大流量。 流函数 \( f(e) \)：实际通过边 \( e \) 的流量，需满足： 容量约束 ：\( 0 \leq f(e) \leq c(e) \)。 流量守恒 （除源点和汇点）：每个中间顶点的流入量等于流出量。 2. 最大流问题 目标：从源点 \( s \) 到汇点 \( t \) 输送尽可能多的流量。 最大流最小割定理 （Max-Flow Min-Cut Theorem）是关键结论： 割 （cut）：将顶点集 \( V \) 划分为两个集合 \( S \) 和 \( T \)，且 \( s \in S, t \in T \)。 割的容量 ：所有从 \( S \) 指向 \( T \) 的边的容量之和。 定理 ：最大流的值等于最小割的容量。 3. 增广路径算法 Ford-Fulkerson 算法通过寻找 增广路径 （augmenting path）逐步增加流量： 残量网络 （residual graph）：原图中每条边 \( (u,v) \) 添加反向边 \( (v,u) \)，容量为剩余容量（即 \( c(e)-f(e) \) 或反向边的 \( f(e) \)）。 步骤 ： 在残量网络中找一条从 \( s \) 到 \( t \) 的路径（增广路径）。 沿路径增加流量，增加量为路径上最小剩余容量。 更新残量网络，重复直至无增广路径。 优化版本（如 Edmonds-Karp 算法）使用 BFS 保证多项式时间复杂度。 4. 应用与扩展 二分图匹配 ：可将最大匹配问题转化为最大流问题。 多源点多汇点 ：添加超级源点和超级汇点处理。 最小费用流 ：在容量约束下，使流的总费用最小（结合最短路径算法）。 整数流定理 ：若容量为整数，则存在整数最大流。 5. 高级主题 预流推进算法 （Push-Relabel）：通过局部操作（推送超额流量、重标高度）高效计算最大流，适合稠密图。 Dinic 算法 ：分层网络基础上多路增广，复杂度优化至 \( O(V^2E) \)。 网络流的对偶性 ：最大流问题与线性规划对偶性关联，最小割对应对偶问题的最优解。 通过流理论，可进一步研究 图连通性 （如 Menger 定理）、 图像分割 （图割算法）等跨领域问题。