网络分析中求最大流的商空间方法

The Computation of Maximum Flow in Network Analysis Based on Quotient Space Theory

该文研究利用商空间的保真、保假原理给出分析网络的新方法,并以求网络中两点的最大流量为例进行说明,主要工作包括:(1)给出利用保真、保假原理求解问题的基本原则;(2)给出将所研究的问题(求最大流问题)化成"问题求解"形式的方法;(3)利用商空间理论建立对应问题求解的保真、保假原理,并证明对所研究的问题,保真、保假原理均成立;(4)根据保真、保假原理给出求两点最大流量的方法.新方法对求所有的点对点的最大流的计算量由原来需要求n(n-1)/2次点对点的最大流,变成只要求(n-1)次点对点的最大流,显著降低了计算的复杂性.

A novel network analysis technique by using＂falsity preserving＂and＂truth preserving＂properties are presented.It is illustrated with computing maximum flow between two points in the network.The main contributions are as follows：（1）The basic principles of the use of falsity preserving and truth preserving on solving problems.（2）The method of transformation from the maximum flow problem into the form of＂problem solving＂.（3）The falsity preserving and truth preserving principle based on quotient space theory are established and proved to be correct on the corresponding problem solving.（4）The computation of maximum flow between two points in the network by using falsity preserving and truth preserving properties.By using this method,the computational complexity of maximum flow among all points is（n-1）times that between two points.However the existing method computational complexity is n（n-1）/2times.