一种求最优环流的纯组合换弧方法

本文提出一种在有向图中求最优环流的有限算法.算法是通过在有向图中的支撑林和相应的补支撑林之间进行一系列弧的交换来完成的.交换弧的规则是纯组合的,它仅跟一些弧的最小编序有关,跟最小比检验无关5] 4] 3].算法是非单纯形的,即算法实施过程中的各个环流和相应环补流仅保持着基本性.算法是从所考虑有向图中任意给定的一个支撑林开始工作的.

A Purely-Combined Arc-Exchange Method of the Optimal Circulation

In this paper, a kind of finite algorithm to seek the optimal citculation in digraph is proposed. It is accomplished through a series of arc-exchang between supporty forests and corresponding complementary supporty forests in digraph. The rule of arc-exchange is purely-combined, only relates with minimal order of arrangement of several arce, and irrelevants with verification of minimal ratio 5], 4], 3]. It is non-simplex, namely, in the process to carry out it, each circulation and corresponding complentary circulations only keep basic property. Algorithm begins works from a supporty forest arbitrarily given in considered digraph.