Fuzzy矩阵Schein秩的计算复杂性  

ON THE COMPUTATIONAL COMPLEXITY OF THE SCHEIN RANK OF FUZZY MATRICES

作　　者：王学平[1] 杨雁[1] 

机构地区：[1]四川师范大学数学与软件科学学院,成都610066

出　　处：《计算数学》2007年第3期273-284,共12页Mathematica Numerica Sinica

基　　金：国家自然科学基金(10671138);四川省青年基金(05ZQ026-003)资助项目.

摘　　要：本文讨论Fuzzy矩阵Schein秩的计算复杂性问题,证明了它是一个"NP-完全问题".首先,刻画了交可分解的Puzzy关系的交分解解集.然后,从Fuzzy关系的交分解与广义分解之间的关系出发,给出了Fuzzy关系广义分解的算法.最后,从Fuzzy关系广义分解的角度来讨论Fuzzy矩阵的Schein秩.指出它与色数问题之间的关系,即Fuzzy矩阵的Schein秩等于由它生成的简单图的色数,从而证明了计算Fuzzy矩阵的Schein秩是一个"NP-完全问题".This paper deals with the computational complexity of the Schein rank of fuzzy matrices. At first, given a A-decomposable fuzzy relation R, the A-decomposable solution set of A and B with A A B = R is obtained. Then the relationship between the A-decomposition problem and the general decomposition problem of fuzzy relations has been investigated, and an algorithm is shown to construct a general decomposition for a given fuzzy relation. In the end, the Schein rank of a fuzzy matrix has been considered by the view of general decomposition. For a given fuzzy matrix, it is proved that its Schein rank is equal to the chromatic number of a simple graph generated by it. Thus, calculating the Schein rank of a fuzzy matrix is an NP-complete problem.

关 键 词：FUZZY关系 交分解 广义分解 解集 Schein秩 简单图 色数 NP-完全问题 

分 类 号：O241.6[理学—计算数学]