计算机工程与应用2017，Vol.53Issue(13)：42-48,71,8.DOI:10.3778/j.issn.1002-8331.1612-0493
等价关系矩阵的置换合同性质与标准形计算
Congruent permutation and computation of canonical form on matrix of equivalence relation.
摘要
Abstract
The equivalence relation has many applications in network analysis, theory of graph, pattern recognition and database technology. Any matrix of equivalence relation is congruent permutation to the certain canonical form of block1-diagonal-matrix. Some properties of congruent permutation are obtained via the aspect of permutation computation. The generation algorithm for permutation matrix based on the Depth-First-Search(DFS)algorithm of graphis set up:according to the properties of searching road from Equivalent Relation Graph(ERG)by Depth-First Search, the permutation is obtained by the comparison of searching road from ERG by DFS and initial node-numbers. Then the permutation is resolved into the product of several interchanges. At last the final permutation matrix is conducted and the judgement of congruent permutation for certain two matrices of equivalence relation is finished. Besides, in order to verify the correct-ness and efficiency of the algorithm, the paper designs a generation algorithm of equivalent relation matrix. The experi-ments show that generation algorithm of permutation matrix algorithm and equivalent relation matrix is simple and easy to understand and realize.关键词
等价关系/置换合同/深度优先搜索/块1-对角矩阵Key words
equivalence relation/congruent permutation/depth-first search/block 1-diagonal-matrix分类
数理科学引用本文复制引用
张辰,李红军,罗柳红,何英豪..等价关系矩阵的置换合同性质与标准形计算[J].计算机工程与应用,2017,53(13):42-48,71,8.基金项目
国家自然科学基金(No.61372190,No.61571046). （No.61372190,No.61571046）
