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

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

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