同构问题的关联矩阵亚字典排序判别法

A Destinguishing Method of Isomorphic Problem by Sorting on Inferior-Dictionary in Incidence Matrix

通过研究关联矩阵行列变换对两图同构性的影响情况,定义了关联矩阵的亚字典排序,探讨了关联矩阵亚字典排序的唯一性及两图同构的一个充要条件,最后给出一个通过对关联矩阵的亚字典排序,判定两图是否同构的有效算法。

The graph isomorphism affected by exchanging row or column in incidence matrix is researched; the sorting on inferior-dictionary in incidence matrix is defined and the uniqueness of this sorting result and a sufficient and essential condition about isomorphism are discussed. In the end,an algorithm for distinguishing graph isomorphism by using sort on inferior-dectionary in incidence matrix is given.