等价关系矩阵的置换合同性质与标准形计算

来源：计算机工程与应用杂志2017年第13期北京时间：

作者：张 辰，李红军，罗柳红，何英豪

单位：北京林业大学 理学院，北京 100083

摘要：等价关系在网络分析、图论、模式识别和数据库技术等方面都有许多应用，而任意等价关系矩阵都置换合同于块1-对角矩阵标准形，从置换运算的角度分析置换合同的几条性质，提出基于图的深度优先搜索策略的置换矩阵构造算法：根据等价矩阵关系图搜索路径的性质，将图的深度优先搜索所得顶点路径与初始顶点顺序对比构造置换映射。利用置换分解原理，将置换映射分解成相应的对换乘积，得到最终置换矩阵，完成等价关系矩阵的置换相似判定。为了验证该算法的正确性和效率，设计了一个等价关系矩阵的自动生成算法。实验结果表明，置换矩阵构造算法和等价关系矩阵的自动生成算法简洁且易于理解和实现。

关键词：等价关系,置换合同,深度优先搜索,块1-对角矩阵