| Fuzzy矩阵Schein秩的计算复杂性 |
| |
| 引用本文： | 王学平,杨雁.Fuzzy矩阵Schein秩的计算复杂性[J].计算数学,2007,29(3):273-284. |
| |
| 作者姓名： | 王学平 杨雁 |
| |
| 作者单位： | 四川师范大学数学与软件科学学院,成都,610066 |
| |
| 基金项目： | 国家自然科学基金(10671138)，四川省青年基金(05ZQ026-003)资助项目． |
| |
| 摘 要： | 本文讨论Fuzzy矩阵Schein秩的计算复杂性问题,证明了它是一个"NP-完全问题".首先,刻画了交可分解的Puzzy关系的交分解解集.然后,从Fuzzy关系的交分解与广义分解之间的关系出发,给出了Fuzzy关系广义分解的算法.最后,从Fuzzy关系广义分解的角度来讨论Fuzzy矩阵的Schein秩.指出它与色数问题之间的关系,即Fuzzy矩阵的Schein秩等于由它生成的简单图的色数,从而证明了计算Fuzzy矩阵的Schein秩是一个"NP-完全问题".
|
| 关 键 词： | Fuzzy关系 交分解 广义分解 解集 Schein秩 简单图 色数 NP-完全问题 |
| 修稿时间： | 2006-01-20 |
ON THE COMPUTATIONAL COMPLEXITY OF THE SCHEIN RANK OF FUZZY MATRICES |
| |
| Wang Xueping,Yang Yan.ON THE COMPUTATIONAL COMPLEXITY OF THE SCHEIN RANK OF FUZZY MATRICES[J].Mathematica Numerica Sinica,2007,29(3):273-284. |
| |
| Authors: | Wang Xueping Yang Yan |
| |
| Institution: | College of Mathematics and Software Science, Sichuan Normal University, Chengdu 610066, China |
| |
| Abstract: | 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. |
| |
| Keywords: | |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算数学》浏览原始摘要信息 |
| 点击此处可从《计算数学》下载免费的PDF全文 |
|
