网络流 网络流是图论中研究资源在网络上传输和分配的重要模型。让我们从基础开始逐步深入。 首先，网络流定义在一个有向图上，这个图被称为“流网络”。一个流网络包含两个特殊节点：源点（s，代表资源起点）和汇点（t，代表资源终点）。图中的每条有向边都有一个非负的容量，表示该边能承载的最大资源量。 接下来是核心概念——“流”。流是一个函数，它为每条边分配一个数值（流量），必须满足两个条件：1）容量限制：每条边的流量不能超过其容量。2）流量守恒：对于除源点和汇点外的任何中间节点，流入该节点的总流量必须等于流出该节点的总流量。直观地说，资源在中间节点既不会凭空产生也不会积累。 一个流的大小（或称值）定义为从源点流出的总流量，它也等于流入汇点的总流量。网络流问题的核心目标通常是寻找一个使得流的大小达到最大的方案，即最大流问题。 为了求解最大流，一个关键工具是“增广路径定理”（最大流最小割定理）。该定理指出，在一个流网络中，从源点到汇点的最大流的值，等于其“最小割”的容量。一个割是将网络节点划分为两个集合S和T，其中S包含源点，T包含汇点。割的容量是所有从S指向T的边的容量之和。这个定理将动态的流问题与静态的割问题联系起来，是算法设计的理论基础。 基于增广路径思想的最经典算法是Ford-Fulkerson算法。其基本步骤是：从零流开始，只要存在一条从源点到汇点的“增广路径”，就沿该路径增加流量。增广路径是指在残余网络中存在的路径。残余网络是对原网络的扩展，它为每条边添加了一条反向边，反向边的容量等于当前该边上已使用的流量。这样，沿反向边增加流量就相当于“退回”部分已分配的流量，从而为找到更优的流分配方案提供了灵活性。 Ford-Fulkerson算法的一个著名实现是Edmonds-Karp算法，它规定每次寻找增广路径时都使用最短路径（边数最少），从而保证了算法的时间复杂度为O(V E²)，其中V是节点数，E是边数。 最大流模型有广泛的应用，例如在交通系统中最大化车流量，在通信网络中最大化数据传输率，或者解决特定的匹配问题（如将任务分配给机器）。