流网络

流量网络显示容量和流量。标有边缘 $x / y$有流动 $X$和能力 $y$．^［1］

一种流网络是一个定向图形每条边都有容量和流量。它们通常用于模拟地点之间的物品运输问题，使用容量有限的路线网络。例如，在道路网络上建模交通，在管道网络中的流体，以及在电路元件网络中的电力。

例如，一个公司可能想用卡车在中间城市之间运输包裹，从洛杉矶运送到纽约。如果连接两个城市的路线上只有一辆卡车，并且每辆卡车都有最大载客量，那么描述交通选择的图将是一个流网络。每个节点将代表一个城市，每个边缘将代表城市之间的卡车路线(如高速公路)。某一特定路线的承载量是该路线卡车所能承载的最大负荷。利用这个模型，公司可以决定如何在不同的卡车之间分割包裹，以便包裹可以通过可用的路线和卡车到达目的地。公司决定沿着特定的卡车路线运输的包裹数量就是该路线的流量。

想象一下，想要从城市尽可能多地运送许多小部件的快递服务 $S.$到城市 $T.$．不幸的是，没有办法直接从 $S.$到 $T.$，因此Courier服务必须使用中间城市来运送小部件 $一种$那 $B.$那 $C$, $D.$．一些特定的城市通过航班连接起来，这使得这些城市之间的小部件运输成为可能。这个交通网络可以用下面的有向图表示，其中节点表示城市，有向边表示城市之间的航班。

代表城市之间可能的航班的图表

显然，任何一架现实的飞机都不可能携带无限数量的小部件。因此，根据货舱的大小，每架飞机可以携带的小部件的最大数量都是有限的。这个最大值叫做能力飞行。它是与上图中的每个边缘相关联的数字，并表示可以在城市之间传输的窗口小部件的最大数量。下图是上图加上了相应的容量。例如，飞行 $B.$到 $C$可以携带最大的 $9.$小部件,所以边缘 $\ vec {bc}$有能力 $9.$．

表示具有相应容量的城市间航班的图表

现在，快递服务具有它可以用于传输小部件的航班的代表，以及可以在城市之间移动的窗口小部件的最大数量，它可以开始决定每次飞行上运输多少个小部件的任务。沿着每次飞行运输的小部件的数量被称为流飞行。幼稚的解决方案是为每个航班分配尽可能多的小部件。然而，这违反了一般意义上的限制，即进入一个中间城市的小部件的数量必须等于离开该城市的小部件的数量。否则，小部件被留下(在这种情况下，飞进来的比飞出去的多)或凭空产生(在这种情况下，飞出去的比流进来的多)，这两种情况都不符合快递员的利益或能力。实际上，分配最大流量可能的叶子 $14.$小部件进入城市 $D.$,只 $11.$小部件离开,这意味着 $3.$小部件的消失了。

对于图中除了 $S.$和 $T.$，离开该节点的总流量必须等于进入该节点的总流量。一种考虑这两个约束的可能分配如下所示(边的流量不能超过它的容量，进入节点的流量必须等于离开该节点的流量)。

用于运输小部件之间的流程的一个有效分配 $S.$和 $T.$

一个很自然的问题是，这样的分配是否可以最大限度地从城市运送小部件 $S.$到城市 $T.$．由于窗口小部件的数量被运送到城市 $T.$只是离开的小部件数量 $S.$或进入 $T.$，对任意一个进行求和就会得到此流分配允许的发货 $9.$小部件。事实上，一个最优分配，被称为最大流量,是 $23.$小部件，如下图所示。这是一个流程分配(不一定是唯一的)，它最大化了快递服务所声明的最大部件数量的目标 $S.$到 $T.$．其他问题和目标将在本节中描述流量网络问题在下面。

流的分配最大化了小部件之间的传输 $S.$和 $T.$

正式,流网络被定义为

流动网络 $N$是一个元组 $n =（g，c，s，t）$在哪里

$G = (v, e)$是顶点的指示图 $V.$和定向边缘 $E.$
$c: E \right tarrow \mathbb{R}_0^+$是从边到非负实数的映射吗 $c (e)$被称为能力的边缘 $E.$
$s, t在V中$的特殊顶点是什么 $G$分别称源和沉没

允许的流动。或者，短暂的，一个流在n，被定义为

一个流 $F$对于流量网络 $N$是一个映射 $f: E \right tarrow \mathbb{R}_0^+$满足以下两个约束条件:

$0 \le f(e) \le c(e)$

为所有的边缘 $e \在e中$

$\ sum_ {e ^ + = v} f（e）= \ sum_ {e ^ - = v} f（e）$

为每个顶点 $V \neq s, t$,在那里 $e ^ -$和 $e ^ +$表示边缘的开始和终端顶点 $E.$， 分别

第一个约束（称为可行性条件）简单地说流量 $F（e）$沿着每条边 $E.$必须是非负的并且不能超过容量 $c (e)$的边缘。第二个约束(称为流动保护条件)说，流入顶点的流量必须等于流出顶点的流量，除了源顶点和汇聚顶点。

给定的顶点 $S a b t$与源 $S.$和水槽 $T.$，画出具有以下容量的流动网络，并确保每条边都标有相应的容量。

$c (vec {sa} \) = 1 c vec{…})(\ \四= 1 c vec {ab})(\ \四= 2 \四c (vec在{}\)= 1 c vec {bt})(\ \四= 1$

显示答案

一个可能的流动网络的布局显示在左边。注意，由于边在流网络中是定向的，边 $\ vec {ba}$是不是连边都不包括在图中 $vec {ab} \$包括在内。而且,由于 $S.$是一个源，它没有边进入。同样,沉 $T.$没有边留下。

给定前面例子中的流网络，这个映射(每个边的标签都等于那条边的流量)是否低于一个可容许的流量?

显示答案

没有，映射不是一个可接受的流。虽然映射满足可行性条件(检查每条边的流量在0和该边的容量之间)，但流量守恒条件不满足。具体来说，是退出节点的总流 $B.$是 $1$，而总流进入节点 $B.$是 $1．5$．改变边缘的流动 $\ vec {sb}$从 $综合成绩$到 $二十五分$将使其成为可接受的流动。

虽然许多不同的问题可以用流网络来表述，但有一些概念对几乎所有的问题都是通用的。有些用于将给定的问题陈述转换为规范形式 $n =（g，s，t，c）$如前一节所定义的，而其他则用作算法解决方案中的中间计算。

剩余容量

这剩余容量 $R.$流动网络的 $N$和一个流程 $F$是容量之间的差异 $C$和流程 $F$．正式，这被定义为

流量网络的剩余容量 $N$和流动 $F$是一个映射 $R：e \ lightarrow \ mathbb {r} _0 ^ +$这样

$R (e) = c(e) - f(e)$

为所有的边缘 $e \在e中$

将每条边的权重设为其剩余容量就形成了a剩余的网络对于流量网络 $N$和流动 $F$．该网络模拟所有边缘的可用容量，并用作中间计算Ford-Fulkerson算法为解决最大流问题．

增广路径

一个增广路径是残余网络中的一条定向路径，对于该路径中的每个边缘都具有未使用的容量。正式，这被定义为

流网络的扩充路径 $N$和流动 $F$是一条定向的路径 $P.$从源头开始 $S.$在水槽处结束 $T.$使剩余产能 $R.$对于该路径上的所有边缘都是非零的。具体来说，

$P = (u_1, u_2， \dots, u_{k-1}， u_k)$是一个有方向的路径 $U_1 = S.$和 $U_K = T.$这样

$R (e) = c(e) - f(e) \gt 0$

为所有的边缘 $e =（u_i，u_ {i + 1}）$为 $I = 1 \导k - 1$路径中 $P.$．

事实上，这是一个流动网络 $N$with $F$为最大流量，当且仅当剩余网络中没有增广路径时为。这个定理的“如果”部分，即最大流量没有增加路径，是很清楚的，因为存在这样的路径意味着存在更大的流量(通过沿着路径的最小剩余容量增加路径上所有边的流量)。这个定理的“仅当”部分，即没有增广路径意味着最大值，是不那么直观的，是背后的关键洞察力Ford-Fulkerson算法．

出错

多源多汇的流动网络。一个supersource $S.$和supersink $T.$添加了。^[2]

通常，给定的问题需要建模多个源和/或多个汇。由于流量网络的规范定义 $n =（g，s，t，c）$仅指定单个源和单个接收器，有时添加超级节目需要流量网络。具体地，多个来源需要添加一个SuperSource.，从超源到每个单独的源都有边，而多个汇则需要增加一个supersink，每个单独的边缘沉到上层链接。然后，流量网络的来源 $S.$是否设置为超源和流网络的汇 $T.$设置为超级墨水。

由于超级节点的添加不应该影响图上的任何计算，容量 $C$对于新创建的边缘被设置为Infinity，因此沿着这些边的流量仅被限制为非负。例如，右侧的数字是流量网络 $N$来源 $s_1 \点,s_n$和 $m$汇 $t_1，\ dots，t_m$, supersource $S.$和supersink $T.$．

有几个不同的问题可以作为流量网络建模。特别是一些常见的并且在非常多样化的领域中出现。由于流动网络问题已经很好地研究，因此这里仅在这里简要描述，以及一些示例应用程序。在每个问题描述中，更多的深度讨论都与之相关联。

最大流量

这最大流量问题是通过单个源，单槽流量网络找到最大可允许流的问题。它最初在1954年由数学家制定，试图建模苏联铁路交通流量。最大流量问题的众所周知的解决方案包括Ford-Fulkerson算法那Edmonds-Karp算法,Dinic的算法．

最大流量算法的应用范围非常广泛。例子包括航空公司机组人员调度、流通需求问题(具有位置依赖需求的货物必须使用容量有限的路线运输)，以及确定在体育赛季何时淘汰输掉比赛的球队。

最小费用流

最小费用流问题是找到最便宜的方式通过网络发送一定数量的流量。这就需要扩大流动网络，使每条边 $E = (u, v)$现在也有一个相关的成本 $a（e）$每个边缘单位流动。然后，流量的总成本 $sum_（e e e）$a（e）\ cdot f（e））。可以使用最小成本流量线性规划由于客观函数是线性的，因此约束。

最小成本流程的一个常见应用是确定从点A到Poix B传输项目的最便宜方式，给定有限的容量和相关成本的路由。例如，卡车路线可能具有更大的容量，但成本更高（时间条目），而平面路线可能具有较小的容量，但成本较低。因此，寻求最小化运输成本的公司将寻求使用最低成本流量的能力和成本之间建模这种权衡。

最大的二分匹配

最大的二分匹配是确定二分图的最大匹配的问题。如果该图形被建模为流量网络（从一组节点流到另一组），则可以使用各种流算法来解决它。例如，Ford-Fulkerson算法可以在未加权的图表中解决双层匹配，也可以Hopcroft-Karp算法，因为它是专门为二部图设计的，所以效率更高。对于加权图的情况(称为分配问题)，其中最著名的算法是匈牙利算法．

最有趣的极大二部匹配是用分配问题来构造的。分配问题最常见的表述是给定一定数量的agent和一定数量的任务，以及每个agent在每个任务上的成本/效益，将每个agent分配给恰好一个任务，使成本/效益最小化/最大化。许多常见的问题都可以用分配问题来表述，因此应用非常多样化。应用程序包括调度、资源分配和运输分割。

运输问题

一个更多的转让问题版本是运输问题．事实上，运输问题也是最小成本问题的一个更具体的版本。运输问题类似于分配问题，但不是每个agent只分配一个任务，而是每个agent可以将自己的时间分配到多个任务中，每个任务可以由多个agent参与。因此，可能没有分配一些代理和任务。

交通问题，顾名思义，有时用矿山和工厂来描述。如果矿山向工厂供应矿石，那么运输问题就变成了确定从单个矿山向单个工厂运输矿石的最具成本效益的方式。因此，来自一个矿山的矿石可能被送往多个工厂，而一个工厂可能使用来自多个矿山的矿石。在这种情况下，成本函数取决于每个矿山和工厂之间的欧氏距离，以及两者之间可用的运输方法的成本。显然，并非只有采矿业的运输问题可以用这种方式表述，所以这个问题本身是非常普遍的，它的应用也是如此。

1. ,J。network_flow_reversed_edge_1.．2013年1月23日，从https://en.wikiversity.org/wiki/file:network_flow_reversed_edge_1.svg.
2. 李,C。Multi-source_multi-sink_flow_problem．2009年9月7日，从https://commons.wikimedia.org/wiki/File:Multi-source_multi-sink_flow_problem.svg