紧急网络中的最小饱和流问题

网络N中的一个流，如果沿前向已无法再增流，则称为饱和流，在交通拥挤或紧急疏散时，网络往往被一饱和流所堵塞。显然，这饱和流的值越小，网络的性能就越差。于是从网络分析的观点就提出最小饱和流问题。本文首先证明此问题NP－困难的。然后给出关于最小饱和流与最大流的关系及算法方面的结果。

The Minimum Saturated Flow Problem in Emergency Networks

A flow in network N is said to be saturated if its value cannot be enhanced any more by only increasing flows along the forward direction.In a traffic jam or in a situation of emergency evacuation,the network is often blocked by a saturated flow.Clearly,the smaller the value of the saturated flow is,the worse is the performance of the network.This gives rise to the minimum saturated flow problem in network analysis.In this paper we first show that the problem is NP-hard.Then,the relation between minimum saturated flows and maximum flows,as well as results in the algorithmic aspect,are presented.