探索流网络和最大流最小割定理的领域
介绍
在网络流优化领域中，最大流最小割定理作为一个卓越的数学里程碑脱颖而出。它的优雅性揭示了解决涉及通过由边缘相连的节点组成的网络中流体或资源流动的复杂优化问题的关键。它的应用范围涵盖了广泛的系统，从交通网络到通信基础设施，高效的流管理对于这些系统至关重要。通过理解这个定理及其数学表述背后的基本概念，您可以解开在各种实际场景中最大化资源利用和达到最佳性能的谜题。
在本文中，我们的目标是简化并使定理易于理解，适合所有读者。我们将向您介绍其历史发展，概述其源自早期公式的根基，这将帮助我们欣赏为这个定理及其整个数学研究领域铺平道路的杰出思想家的贡献。此外，我们将深入探讨最大流最小割定理的实际应用。从设计高效的交通系统到处理图像处理任务，它的多样性似乎是无限的。通过探索其实际影响，您将目睹这个定理对不同领域和行业的深远影响。
最后，我们的目标是为您提供一个既简单又正式的详细解释。不需要先前的高级数学知识，尽管对图论和离散数学（逻辑和集合论）的一些了解可以大大帮助；您只需要一颗好奇的心和愿意揭示这个卓越定理的实用性。
历史
最大流最小割定理最早由Ford和Fulkerson于1956年在他们的重要论文《通过网络的最大流》中介绍，与其他相关数学家合作，如信息论的发展者Claude Shannon。该定理指出，网络中的最大流等于割的最小容量，其中割是将网络节点分为两个不相交集合的分割，其容量是穿过割的所有边的容量之和。从那时起，这个定理就成为了流网络理论的基石。
然而，这个定理的引入伴随着其他关键的科学贡献，如Edmonds-Karp、Ford-Fulkerson或Dinic等算法，它们都用于寻找通过具有源和汇的网络的最大流。类似地，通过最大流最小割定理，这个值与将汇点与源点分隔的最小割相匹配。此外，我们可以利用算法的内部计算来识别构成最小割的边集，我们将进一步探讨这个问题。
流网络
因此，为了简化接下来关于定理的解释，我们先了解图论中流网络的基本概念。
如上例所示，流网络是一个加权有向多图，用于表示需要从一个或多个点“源”（表示为S节点）到一个或多个其他节点（称为“汇”（T节点））传递或移动一定数量资源（称为“流”）的网络结构化对象或系统。尽管此示例没有显示多图的属性，因为两个节点之间只有一条边。
为实现这种模板的表示，流网络中的每条边都有与之关联的权重。在这个上下文中，加权边模拟了资源（流）交换的多个点之间的物理/逻辑连接，其中正实数权重的实际值代表其容量（支持的最大流量）。上面，您可以看到每个边标签右侧显示的容量，以及当前通过的流量，这个例子中是0。
除了每条边的容量之外，定义资源在每条边上单位时间内传输的速率的关键指标是流量。你可以将其视为道路上的交通量或管道中的水量。因此，从源节点（或超源节点，如果所有网络的源都连接到主源流量发生器）生成，然后传输到汇节点（或超汇，如果类似的构造存在于汇点上），我们可以将流量定义为一个函数f:E→R，它接受属于图边集合E的边(u,v)作为输入，并输出其在时间f(u,v)中的当前流量，该流量是一个正实数。
因此，如果我们对流网络的所有相应源S或汇T计算上述表达式，我们可以得到通过图的总流量。
为了保证流量与网络约束的粘合，它必须满足两个基本属性：
- 容量约束：通过任何边的流量不能超过其容量。形式上，如果边的容量表示为“c(u, v)”，流量表示为“f(u, v)”，那么对于网络中的所有边(u, v)，它必须满足条件0 ≤ f(u, v) ≤ c(u, v)。简单来说，我们不能通过一条边传输比其容量还多的流量。
- 流量守恒：在每个节点（不包括源节点和汇节点）上，进入节点的总流量必须等于输出的总流量。
这确保了流量在网络中不中断地流动，不会在网络中累积或耗散，尽管如果系统需要，可以允许流量累积。数学上，对于每个节点“u”及其由超节点“v”和“w”表示和分组的相邻节点，流量守恒属性表示为：
最后，请注意，流量可以相互抵消，因为如果节点u和v之间存在流量f1(u,v)和f2(v,u)，那么减少f1(u,v)等价于增加f2(v,u)，因为它们具有相反的方向。
剩余网络和增广路径
在这里，我们将介绍两个新的、更复杂的概念，在使用前面提到的算法找到最大流时非常有帮助。
这两个概念中的第一个是在给定时间内边的容量与其流量之间的差异，称为剩余容量，表示为：
有了这个属性，我们可以定义一种特殊类型的流网络，称为剩余网络，其与标准网络的唯一区别是其边的重新定义容量。剩余网络具有上述定义的函数cf，它将边集合及其相应的容量和流量映射到相应的剩余容量。
在这个示例中，上图中的网络中的每条边都有一个特定的流函数。因此，残差网络将是下面的网络，其边缘标签包含根据相应边缘的方向和相反方向中的流量量执行流增量操作时可发送的剩余容量（请记住流量取消属性，在网络具有一定对称性的情况下，这可能很有用）。
通过源头或汇点公式，可以计算通过网络实现的流量，就像之前所见的一样，本例中是分布在4+3个从S流出的单位或者4+1+2个流入T的单位。然而，如果我们考虑反向（或双向）的(v5, v1)边缘，那么沿着路径S-V1-V5-V4-V3-T还有可能发送2个流量单位，这将增加总流量并成为给定网络中最大的可用流量。因此，在推导出残差网络之后，有可能存在一条或多条连接源和汇点的路径，其中所有边缘的剩余容量都大于0。换句话说，在存在多个源或汇点的情况下，存在可以从源到汇点传输流量的路径。
在这种情况下，这样的路径是解决流量最大化或成本最小化问题的算法的基础，并被称为增广路径。为了理解为什么，在上述网络中，我们可以看到建立的流量导致存在一条增广路径，可以将2个流量单位从S传输到T。因此，网络上的实际流函数不能提供通过网络的最大可传输流量，这是Maxflow Mincut定理面临的问题之一，我们将在后面讨论。
因此，如果我们增加通过显示路径的流量，我们将能够确保所得到的流量是最大的，其值为9个单位，因为没有其他路径可以增加网络流量。最后，在引入定理之前，重要的是要记住，为了找到网络的最大流量，像Ford-Fulkerson这样的算法使用一种直观的过程（贪婪），从一个没有任何流量的残差网络开始，并继续寻找增广路径（借助残余边缘或相反方向的流量），同时根据这些路径增加流量。因此，一旦没有更多的路径可以发现增加流量，就可以确保达到的流量是最大的，也就是说，没有更快的方法可以从S到T移动资源，因为某些边缘缺乏容量，甚至网络中缺乏边缘。
另一种思考这个过程的方法是考虑每次迭代添加的流量量。对于任意的增广路径，您可以添加的最大量由具有最小剩余容量的边缘给出，因为它对于从S流出的流量构成了一个瓶颈。由于其能够限制沿增广路径的所有潜在流量，这样的瓶颈边缘在需要最大化流量的情况下至关重要。
例如，考虑上述简单的流网络（剩余网络）只有一条增广路径可用，我们可以清楚地识别边缘(v2, v3)的瓶颈组件，该组件将整个路径（在本例中是网络）的最大流设置为3。根据路径建议增加3个单位的流量后，没有增广路径可以进一步增加流量，因此可以得出最大流已达到。然而，验证结果的另一种方法是关注网络中的瓶颈；如果S和T之间的每条路径的空瓶颈值（即其最大剩余容量等于0）均为零，则相当于不存在增广路径，不能再增加流量，当前流量将被视为最大，如上所示。
为了解决关于瓶颈的问题，我们应该强调最大流也可以表示为通过Ford-Fulkerson类算法找到的所有增广路径的瓶颈之和，因为每条路径增加的流量由其对应的瓶颈确定。
流网络割
我们将涵盖有关流网络基础的最后一部分是割，这是Maxflow Mincut定理的基本组成部分，也是理解前面部分的关键概念，例如瓶颈和流网络的分区之间的联系。
首先，让我们从其定义开始；割是网络节点的一个分区，其中源节点S在一个集合A中，而汇节点T在与之前集合不相交的另一个集合B中。
A和B集合都不能是空集，因为它们必须包含源和汇节点。因此，如果网络是连通的，将存在能够在A和B节点之间执行连接功能的边缘，这些边缘是双向的。此外，这些边缘包含在另一个名为割集合的集合中，尽管只有那些起点是A节点且终点是B节点的边缘被考虑在内，即能够以正确方向传输流量的边缘。
例如，您可以看到上面可以应用于图形的最简单的割，导致将顶点集合V划分为集合的并集A={S}和B={V1,V2,V3,V4,V5,T}。由于唯一的网络源在一个集合中保持孤立，我们可以更加准确地理解割的概念及其后续属性。通常，割被表示为一条寻求将A或B两个集合之一围起来的线。此外，划分的边界穿过多条属于割集合的边缘，双向地。这些边缘用于确定割的流量和容量，这在建立网络的任意割和流之间的关系时非常重要。这在本文中提出的定理的证明中至关重要。
一方面，通过给定割的流量定义为所有在A-B方向传输流量的边缘的总和，减去从集合B到集合A的边缘的流量。
然而，在这种情况下，流量在这个上下文中并没有重要价值，因为它受到割的容量的限制。因此，我们还可以类似于流量的方式定义割的容量，但区别在于只考虑上述公式的第一项，即能够将流量从S流向T的边缘的容量，而不必减去任何其他边缘的值。
一旦我们正式介绍了割集中流量和容量的概念，就有必要考虑一些尽可能简化这些思想并在这个领域中理解它们的合理性的示例。
首先，让我们检查每个集合的顶点，保留 A={S,V5,V4} 和 B={V1,V2,V3,T}。由于网络已经被分配了流量，因此割流量不会为零，并且将由连接集合 A 和 B 的边上的流量总和确定。
此外，其容量是根据相同的先前边和它们各自的容量获取的，构成了可能通过割中传输的最大流量。
在这个有趣的最后一个割集示例中，我们可以观察到割集不必是由两个集合的顶点组成的连接组件的分割，也就是说，每个集合可以包含任何节点，只要满足割的基本约束即可。
此外，这个例子对于理解割集和流量之间的关系非常有帮助，在攻击定理之前提供了坚实的基础。首先，请注意，根据割的定义，割后的网络（在割后）与 s-t 相对于连接断开。这意味着这样一个割的容量是由从源集合到汇集的所有边的总和计算得出的。在最基本的情况下，隔离单个流源，割的容量将超过或等于网络的最大流量。然而，在前面的例子中，可以明显看出，通过插入更多具有出边的节点，割的容量不可避免地增加，因为边的数量超过了达到最大流的严格要求，即源的边决定了在瓶颈情况下随后将通过网络的流量。
定理陈述
我们在解决流网络优化问题时的主要目标是确定从源到汇传递的最大可达流量。这必须在遵守容量限制、流量守恒以及确保实际流量最大的情况下完成。因此，在处理定理时，我们将采取的步骤是将该值约束在一个可以类似于流量计算的上界中，从而确认其正确性。
首先，应该强调这样一个上界恰好是一个割，它满足具有最小容量的属性。作为定理的主要引理，它可能不完全清楚，因此让我们引入并证明两个更简单的思想；
第一个涉及证明任意给定割的流量与总网络流量之间的等式，而总网络流量又与源生成的流量相匹配。为此，我们可以假设初始命题为真，并将归纳方法应用于任意割的集合A，其中A = {S}作为基本情况，然后使用先前提到的流量守恒原理来处理与S或T不同的节点。但由于这会变得复杂，我们将选择一种更简单但非常相似的方法。
请注意，在证明过程中的先前流量值可以具有任何允许的值。
1- 流量定义：在初始步骤中，我们从网络中的任意给定流函数f的总流量值开始，并且有可能的定义之一。在这里，我们以源节点S作为参考，它是任意网络割的最小可能集合A，将流量值与由S生成的流量匹配，减去流入S的流量，因为有时可能有一定量的流量返回到S。
2- 流量守恒性质：在将网络流量视为源S生成的总流量之后，我们应用流量守恒原理，即除了s-t之外的所有节点必须传播它们收到的所有流量，通过减去出流量与入流量之差，将其贡献给|f|的流量。现在，如果我们取任意割(A,B)，则集合A中的节点v（除了生成流量{S}的节点）贡献的总流量将为零，满足我们之前的等式。
3- 通过割的流量：最后，我们得到一个表达式，在第一项中加上A中除S以外的节点的所有出流量，在第二项中加上S自己的出流量，减去所有先前节点的相应入流量部分。这对应于割流量的前述定义，因此我们可以得出结论，网络中的所有现有流量必然与任意给定割的流量相匹配。
我们将证明关于最大流最小割定理的第二个命题，它包含了一个不等式，它上界了网络中任意流量的值，使其不超过任意给定割的容量值。
1- 替代流量定义：利用先前关于任意割的流量的结果，我们可以将任意流量|f|等同于任意割(A,B)的流量。
2/3- 流量界定：在第二步中，我们建立了一个不等式，它排除了集合A中模拟流入流量的第二项，只留下从A到B携带流量的边的出流量。在去除这样一项之后，结果总是大于或等于先前的结果，因为如果没有边将流量从B返回到A，则从A到B的剩余边的流量之和不会减少。
然后，我们可以通过将从A到外部的边的流量设置为小于或等于这些边的容量来简单地增加不等式的值。这个不等式的有效性来自于所有网络边上的容量约束。
4- 弱对偶性：在将集合A的所有出边的容量总和与割的容量相匹配后，可以得出结论，对于网络中的任意给定流量和割，流量总是小于或等于割的容量，这是我们即将证明的定理的起点。此外，如果我们试图最大化流量，我们将达到一个可以通过最小化割容量来实现的点，建立了一种弱对偶关系，在这种关系中，没有确保最小容量割等于最大流量的存在。
在达到最大流和最小割定理之前的弱对偶性后，我们可以提供一个更容易理解和验证的陈述。
正如前面提到的，该定理通过强对偶性保证了任何网络中的最大流与可达到的最小割的容量相匹配。与前面的弱对偶结果相比，该定理确保了流量的最大化对偶与任何割容量的最小化完全相等，消除了两个结果之间的差异，并在引理上提供了强对偶条件。
在进行证明之前，我们应该强调该定理的一个用例。在这里，最大流的值为7，与每个流出截断边的容量之和相等。请注意，这些边以其最大容量携带流量，在像所示的最小容量割中，这些边成为瓶颈，即割集本身作为全局网络流量的瓶颈。为了简化对这个思想的解释，下面是一个资源，帮助您理解：
最大流最小割定理的直观解释是什么？
我即将阅读最大流最小割定理的证明，它有助于解决最大网络流问题。请问……
math.stackexchange.com
证明
如果我们想要证明最大网络流在所有情况下等于网络中的最小容量割，我们将使用三个命题，这些命题必须对定理成立。
存在一个满足 |f|= cap(A, B) 的割 (A, B)。
流量值 |f| 是最大的。
在流网络中不存在增广路径。
为了显示所有陈述是等价的，我们将证明逻辑蕴含关系 1⇒2⇒3⇒1。这意味着我们可以从任何一个陈述推断出任何其他陈述。在 1⇒2 的情况下，可以使用前面展示的弱对偶性进行轻松验证。然后，考虑到任何流都小于具有最小容量的割，如果我们假设存在与任意割的容量相等的流 (1)，则弱对偶性告诉我们，该容量是任何给定流的上界，因此得到的流，与该上界重合，是最大的 (2)。
继续进行 2⇒3，验证它的最简单方法是取反命题 ¬3⇒¬2。然后，只需取一个任意流 |f| 作为例子，假设存在一个增广路径 s-t ¬(3) 可以传输流量，那么可以沿着相应路径增加 |f| 的流量，这意味着 |f| 最初不是最大流 ¬(2)。
最后，这个证明中最具挑战性的一步是 3⇒1。首先，我们假设一个流 |f|，在该网络中没有增广路径。此外，我们定义一个集合 A，其中包含从 S 在剩余网络中可达到的所有顶点。也就是说，A 包含所有在剩余网络中存在一条从 S 到达的路径的顶点，并且同时，该路径上的所有剩余边都非零。通过这些定义，我们可以确定 S 在 A 中，因为它可以自己到达，而且由于没有增广路径，从 S 到达剩余网络中的 T 不可行，所以我们知道至少一个节点 (T) 不在集合 A 中。然后，如果我们将 T 插入到另一个集合 B 中，那么我们就得到了对网络中的割 (A, B) 的所有标准的满足。
在这一点上，我们必须意识到关于割(A, B)的两件事。一方面，割在S-T方向上的流量必须等于其容量。因为根据前面的定义和假设（3），它们不相等的唯一可能性在于B的节点的可达性，所以如果其中任何一个从剩余网络中的S可达，导致割的边上的流量未达到其完全容量，那么该节点必须在A中而不是B，这是一个矛盾。另一方面，割的另一个方向上的流量结果为零，原因与前面相同，即如果它不为零，那么在剩余网络中将存在一条边在A-B方向上（用负号表示的剩余边流量）达到B节点并导致矛盾。
最后，要做的唯一事情就是将网络流匹配到割流，这在之前已经证明过，移除流入割的项，因为它为零，并使用割容量定义得出流量|f|等于结果割容量（3⇒1）。
应用
最大流最小割定理在各个领域中有许多应用。然而，为了简洁起见，我们只是简单提及一些用例的基本方面，并提供更详细的资源以帮助您正确理解它们。
Ford-Fulkerson/Edmonds-Karp算法
首先，该定理所提供的发现和结果与其他定理（如整数定理）一起，导致并支持一系列计算最大流的算法的正确性证明。
其中最重要的算法，也是我们已经谈论过的算法，是Ford Fulkerson算法，一种贪婪的方法，通过寻找s-t增广路径来增加流量。然而，基本版本的算法在某些具有特定输入的情况下（例如使用实数或无理数及其表示）没有保证能够在特定情况下终止或收敛到最大流，这是由于它选择增广路径的方式。这也影响到它的时间复杂度，即O（|E| |f|），意味着在最坏的情况下，算法需要遍历网络的所有边缘，为了达到最大流中包含的每个（至少一个）流量单位。
然后，为了改进以前的版本，即最早用于解决这类问题的版本，改进了计算增广路径的方式。这样，虽然Ford-Fulkerson版本使用深度优先搜索（DFS）计算到T的随机路径，但改进的Edmonds-Karp变体使用广度优先搜索（BFS）算法来寻找增广路径。因此，在每次迭代中选择具有最少可能边的增广路径，该算法与以前的算法相比具有终止保证，此外，时间复杂度的变化为O（V E²）。
然而，使用这些和类似的算法，不仅可以计算网络中的最大流，还可以计算容量等于其值的最小割。该过程非常简单；在计算网络中所有边的最大流之后，根据最大流最小割定理，从S在相应的剩余网络中可以到达的节点形成了我们正在寻找的割的集合A，剩余节点在B中，并导致得到的最小容量割（A，B）。
最后，需要注意的是最大流算法的研究领域远远大于此处所展示的内容。因此，如果您希望继续学习，在这里有一份资源详细介绍了这些算法及其实现。
实际应用案例
我们生活中与之互动的几乎所有系统都有一定的潜力可以被流网络（至少部分）建模，这将使它们成为解决复杂可扩展性问题的关键工具。同样地，由于可能性非常广泛，这里只提到一些与基本概念直接相关的案例。
首先，所有的交通系统，从道路网络和公共交通系统到航空路线和货物分配，都可以被表示为流网络。因此，我们可以分析交通模式，优化路线，提高整体效率。这在城市规划中尤为重要，因为管理人员、车辆和货物的流动对于防止拥堵和确保运营顺畅至关重要。此外，并非所有这些用例都完全有益；例如，流网络还可以对应国家的铁路系统，这在军事冲突情况下可能成为攻击目标，攻击应尽可能具有战略优势。您可以在此资源中了解更多关于这个特定应用的信息。
除了在电信、能源分配甚至医疗保健领域的其他重要应用外，我们将重点关注与计算机科学特别是计算机视觉领域更密切相关的一个应用，该领域取得了重大突破。在图像处理中，流网络的主要部署依赖于图像分割算法，负责将图像划分为与对象、主题或需要检测的不同区域对应的片段或区域，这些区域可能无法被人眼区分。在这种情况下，流网络通过将像素之间的关系建模为网络，其中边表示相邻像素之间的相似性/差异性的可能性值的流动。此外，还值得提到在类似范围中的应用，例如机器学习模型，其中流概念用于优化特定的学习、生成或分类任务。
结论
本文仅涵盖了流网络数学领域的一小部分，同时证明并简化了其基本定理之一。然而，由于它在世界的消费、交通和人口管理系统中具有广泛的应用，继续扩大理论并深入了解这些应用的知识是非常有用的。为此，以下是观察更高级的定理形式化、逐步理解本文提到的算法以及学习流网络特定应用新概念的最有效资源：
https://www.cs.upc.edu/~mjserna/docencia/grauA/P20/MaxFlow-fib.pdf
https://ocw.tudelft.nl/wp-content/uploads/Algoritmiek_Introduction_to_Network_Flow.pdf