Fuzzy矩阵Schein秩的计算复杂性

• 作者: 杨雁 王学平
• 来源期刊: 计算数学
• 学科: 数学
• 关键词: Fuzzy关系 交分解 广义分解 解集 Schein秩 简单图 色数 NP-完全问题
• 年，卷（期）: 2007,（3）
• 页码范围: 273-284
• 页数: 12页
• 分类号: O24
• 字数: 9094字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-7791.2007.03.005

摘要

本文讨论Fuzzy矩阵Schein秩的计算复杂性问题,证明了它是一个"NP-完全问题".首先,刻画了交可分解的Fuzzy关系的交分解解集.然后,从Fuzzy关系的交分解与广义分解之间的关系出发,给出了Fuzzy关系广义分解的算法.最后,从Fuzzy关系广义分解的角度来讨论Fuzzy矩阵的Schein秩.指出它与色数问题之间的关系,即Fuzzy矩阵的Schein秩等于由它生成的简单图的色数,从而证明了计算Fuzzy矩阵的Schein秩是一个"NP-完全问题".

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王学平	四川师范大学数学与软件科学学院	73	405	11.0	18.0
2	杨雁	四川师范大学数学与软件科学学院	2	2	1.0	1.0