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

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 correctness and efficiency of the algorithm, the paper designs a generation algorithm of equivalent relation matrix. The experiments show that generation algorithm of permutation matrix algorithm and equivalent relation matrix is simple and easy to understand and realize.

Key words: equivalence relation, congruent permutation, depth-first search, block 1-diagonal-matrix