网络流-经济百科

网络流（Network flow）

什么是网络流

在图论中，网络流是指在一个每条边都有容量（capaCITy）的有向图分配流，使一条边的流量不会超过它的容量。通常在运筹学中，有向图称为网络。顶点称为节点（node）而边称为弧（arc）。一道流必须匹配一个结点的进出的流量相同的限制，除非这是一个源点（source）──有较多向外的流，或是一个汇点（sink）──有较多向内的流。一个网络可以用来模拟道路系统的交通量、管中的液体、电路中的电流或类似一些东西在一个结点的网络中游动的任何事物。

网络流的应用

将一连串的水管绘画成一个网络。每条水管有一特定的阔度，因此只可以保持一特定的水流量。当任何水管汇合，流入汇流点的总水量必须等于流出的水量，否则我们会很快地缺水，或者我们会团积水。我们有一个作为源点的入水口，和一个作为汇点的出水口。一道流便是一条由源点到汇点而使从出水口流出的总水量一致的可能路径。直观地，一个网络的总流量是水从出口流出的速率。

流可以关于在交通网络上的人或物质，或电力分配系统上的电力。对于任何这样的实物网络，进入任何中途结点的流需要等于离开那结点的流。Bollobás以基尔霍夫电流定律描绘这限制的特性，同时较迟的作者（即Chartrand）提及它在某些守恒方程的普遍化。

在生态学中也可找到流网络的应用：当考虑在食物网中不同组织之间养料及能量的流，流网络便自然地产生。与这些网络有联系的数学问题和那些液体流或交通流网络中所产生的难题有很大分别。由Robert Ulanowicz及其他人发展的生态系统网络分析领域包含使用信息论及热力学的概念去研究这些网络随时间的演变。

普遍化及专门化

利用网络流去找出最大流是最简单及最普通的问题，它提供了在一指定的图中由源点到汇点的最大可能总流量。还有很多其它问题可以利用最大流算法去解决，假设它们可以适当地塑造成流网络的模样，例如二部图匹配（BIpartite Matching）、任务分配问题（Assignment PRoblem）和运输问题（Transportation Problem）。

在多物网络流问题（Multi-commodity Flow Problem）中，可以有多个源点和汇点，和各种各样的由指定源点发送到指定汇点的“物品（Commodities）”。例如这可能是不同的工厂生产的各种各样的货物经由“同一”运输网络运送到不同的消费者手上。