求两种商品网络最大流的一个算法

A Algorithm Solving Two Commodity Network Maximnm Flows

本文对“两种商品流”问题进行了研究,给出了两种商品流总流值最大的一个充分必要条件和求两种商品网络最大流的一个算法。

In this paper the unresolved problem-the Fourth-nine problem which listed in 〔1〕is studied. This problem is two commodity network flows problem. A algorithm which solves two commodity network maximum flows is given in this paper.And the following results are obtained. 1. The total value of two flows is maximum if and only if the double path doesn't exist in a network. 2. If every edge capacity is integers, the two integer flows which total flows value is maximum exist.