视频字幕
最大流问题是图论中的一个经典问题。它研究如何在一个网络中找到从源点到汇点的最大可能流量。想象一个水管网络，每个水管都有最大流量限制。问题是：每秒最多能从水源流多少水到排水口？在这个例子中，我们有一个流网络，其中s是源点，t是汇点。每条边上的数字表示该边的容量，也就是最多能通过的流量。
让我们了解最大流问题的核心概念。首先是容量，表示每条边的最大流量限制。流是每条边上实际通过的流量，必须满足容量限制，即流量不能为负，也不能超过容量。流量守恒原则要求，除了源点和汇点外，对于任何节点，流入的总流量必须等于流出的总流量。在这个例子中，我们可以看到每条边上的数字表示当前流量和最大容量。比如，从源点s到节点a的边上，流量是7，容量是10。对于节点a，流入量是7，流出量是5加2，也是7，满足流量守恒。整个网络的最大流是15，这是从源点s到汇点t的最大可能流量。
Ford-Fulkerson算法是解决最大流问题的经典方法。该算法的基本思想是不断寻找增广路径并增加流量，直到不存在增广路径为止。首先，我们初始化所有边的流量为0。然后，构建剩余图，在剩余图中寻找一条从源点到汇点的增广路径。如果找到增广路径，我们计算路径上所有边的最小剩余容量，这被称为瓶颈容量。接着，沿着这条增广路径更新流量，将路径上所有边的流量增加瓶颈容量。重复这个过程，直到剩余图中不存在从源点到汇点的路径。在这个例子中，我们找到了一条增广路径s-a-c-t，瓶颈容量是6，因为a到c的容量限制是6。更新后，这条路径上的所有边的流量都增加了6。
最大流最小割定理是网络流理论中的一个重要结果。它指出，在一个流网络中，最大流的值等于最小割的容量。割是将节点分成两组S和T的一种方式，使得源点s在集合S中，汇点t在集合T中。割的容量是从集合S到集合T的所有边的容量之和。最小割是具有最小容量的割。在这个例子中，我们将节点分为两组：集合S包含节点s、a和b，集合T包含节点c、d和t。从S到T的边有a到c和b到d，它们的容量分别是6和7，所以这个割的容量是13。然而，这个网络的最大流是15，这说明我们找到的不是最小割。实际上，最小割应该是从源点s到汇点t的所有边的最小容量集合，使得如果删除这些边，就无法从s到达t。
最大流问题在许多实际领域都有广泛应用。在交通网络规划中，可以用来确定道路网络的最大通行能力。在电信网络中，可以分析网络的最大传输容量。在二分图最大匹配问题中，例如求职者与职位的匹配，可以转化为最大流问题来求解。如图所示，左侧是5个求职者，右侧是5个职位，连线表示求职者可以胜任的职位。通过最大流算法，我们可以找到一个最优分配方案，使得所有求职者都能分配到合适的职位。其他应用还包括图像分割、项目调度和网络可靠性分析等。将二分图匹配转化为最大流问题时，我们添加一个源点连接所有求职者，所有职位连接一个汇点，并将所有边的容量设为1。这样，最大流的值就等于最大匹配的数量。