簡單無向圖的同構(gòu)判定方法

摘要： 給出了矩陣同構(gòu)變換、簡單無向圖距離矩陣、距離矩陣列和向量以及圖的距離譜的定義,將基于鄰接矩陣的同構(gòu)判定條件推廣到簡單無向圖距離矩陣.針對簡單無向連通圖的同構(gòu)判定問題:給出了基于距離矩陣特征多項式的同構(gòu)判定條件;進一步,為避免計算誤差對判定結(jié)果的影響,給出了基于距離矩陣的秩與列和向量的同構(gòu)判定條件.上述兩個判定條件均是充要條件且均具有多項式時間復雜度.