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

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