网络流 -{H|zh-hans:重定向;zh-hant:重新导向;}--{H|zh-cn:字符;zh-tw:字元;}--{H|zh-hans:文件; zh-hant:档案;}--{H|zh-hans:快捷方式; zh-hant:捷径;}--{H|zh-hans:项目;zh-hant:专案;zh-tw:计划;zh-hk:计划;zh-mo:计划;}--{H|zh-cn:计算机; zh-sg:电脑; zh-tw:电脑;}- 在图论中，网络流（）是指在一个每条边都有容量（Capacity）的有向图分配流，使一条边的流量不会超过它的容量。通常在运筹学中，有向图称为网络。顶点称为节点（Node）而边称为弧（Arc）。一道流必须符合一个结点的进出的流量相同的限制，除非这是一个源点（Source）──有较多向外的流，或是一个汇点（Sink）──有较多向内的流。一个网络可以用来模拟道路系统的交通量、管中的液体、电路中的电流或类似一些东西在一个结点的网络中游动的任何事物。 定义. 网络流图. 如果带权有限的有向图formula_1满足如下条件，则称之为网络流图(或容量网络): 净流. 通过容量网络中的一条弧 formula_7 的流量(或净流)记为 formula_8. 弧. 弧是网络流图中的一条带权边 formula_9. 特殊的弧有： 网络流. 一个流量的集合 formula_14 包含所有弧上的流，则称为这个容量网络的一个网络流。 可行流. 在容量网络中满足以下条件的网络流称为可行流: 伪流. 伪流是一种与可行流相对的概念，如果一个网络流只满足容量限制条件，不满足流守恒条件，那么这个网络流就是一个伪流。 剩余容量. 边的剩余容量（Residual Capacity）简称为残量,是 formula_19. 残量网络. 由所有边均为其残量的 formula_20 称为残量网络（Residual Network）或剩余网络.它显示可用的容量的多少。留意就算在原网络中由 formula_21 到 formula_22 没有边，在剩余网络仍可能有由 formula_21 到 formula_22 的边。因为相反方向的流抵消，减少由 formula_22 到 formula_21 的流等于增加由 formula_21 到 formula_22 的流。 最大流. 对于一个网络流图，它最大的可行流即为它的最大流。 增广路. 增广路（Augmenting Path）是一条路径 formula_29，而 formula_30、formula_31 及 formula_32，这表示沿这条路径传送更多流是可能的。当且仅当剩余网络 formula_33 没有增广路时处于最大流。 性质. 在任意时刻，formula_34 的网络流都满足如下性质。 容量限制. 通过一条弧的流量不能超过这条弧的容量上限。 formula_35 反对称性. 从一个结点 formula_21 到另一个结点 formula_22 的净流量一定是从 formula_22 到 formula_21 净流量的相反数。 formula_40 流守恒. 对于 formula_34 中任意一个结点 formula_21,如果它既不是源点也不是汇点，那么它到相邻结点的所有流量之和为0. formula_43 例子. 在右边可以看到一个有以formula_44标示的源点、以formula_45标示的汇点及4个额外结点的流网络。流及容量以formula_46显示。注意网络怎样保证斜对称、容量限制及流守恒。由formula_44到formula_45的总流量为5，由此可简单地观察到源于formula_44的所有向外流是5，也就是汇于formula_45的向内流。我们知道在其它结点中没有任何流出现或消失。 在下面你可以看到对既定的流的剩余网络。注意某些边的剩余容量是正数而原来的容量是零，如边formula_51。这道流不是一道最大流。沿路径formula_52、formula_53及formula_54还有可用的容量，也就是扩张路径。第一条路径的剩余容量是formula_55。注意扩张路径formula_54在原来的网络中并不存在，但你可以沿它传送流，因此仍是一道正当的流。 假如这是一个真实的网络，由formula_57到formula_58的2单位的流及由formula_58到formula_57的1单位的流事实上可能存在，但我们只维持净流。 应用. 将一连串的水管绘画成一个网络。每条水管有一特定的阔度，因此只可以保持一特定的水流量。当任何水管汇合，流入汇流点的总水量必须等于流出的水量，否则我们会很快地缺水，或者我们会团积水。我们有一个作为源点的入水口，和一个作为汇点的出水口。一道流便是一条由源点到汇点而使从出水口流出的总水量一致的可能路径。直观地，一个网络的总流量是水从出口流出的速率。 流可以适用于交通网络上的人或材料，或配电系统上的电力。对于任何这样的实物网络，进入任何中途结点的流需要等于离开那个结点的流。这个守恒限制相当于基尔霍夫电流定律。 在生态学中也可找到网络流的应用：当考虑在食物网中不同组织之间养料及能量的流，网络流便自然地产生。与这些网络有联系的数学问题和那些液体流或交通流网络中所产生的难题有很大分别。由Robert Ulanowicz及其他人发展的生态系统网络分析领域包含使用资讯理论及热力学的概念去研究这些网络随时间的演变。 普遍化及专门化. 利用网络流去找出最大流是最简单及最普通的问题，它提供了在一指定的图中由源点到汇点的最大可能总流量。还有很多其它问题可以利用最大流演算法去解决，假设它们可以适当地塑造成流网络的模样，例如二分图匹配（Bipartite Matching）、任务分配问题（Assignment Problem）和运输问题（Transportation Problem）。 在多物网络流问题（Multi-commodity Flow Problem）中，可以有多个源点和汇点，和各种各样的由指定源点传送到指定汇点的「物品（Commodities）」。例如这可能是不同的工厂生产的各种各样的货物经由「同一」运输网络运送到不同的消费者手上。 在最小费用最大流问题（Minimum Cost Flow Problem）中，每条边formula_61都有特定费用formula_62。沿这条边传送formula_8的费用是formula_64。目标是要用最低的成本由源点传送一特定数量的流到汇点。 在环流问题（Circulation Problem）中，每条边除了有上限formula_65外，还有下限formula_66。每条边亦有一个费用。很多时，流守恒适用于环流问题中"所有"结点，由汇点到源点亦有一条连结。这样便能利用formula_67和formula_68支配总流量。这问题因流环绕网络流动而得名。 在有增益网络或普遍化网络中，每条边都有增益，一个实数（非零）使如果这条边有一增益"g"而有一流量"x"的流在尾部流入，便有一流量"gx"的流从头部流出。