本文關鍵詞：圖的同構，由筆耕文化傳播整理發(fā)布。

圖的同構判定是圖論學科的基本問題之一。所謂圖的同構，就是指兩個圖的拓撲結構完全相同。從定義看這個問題似乎并不復雜，但它卻是一個世界性難題，多數(shù)學者將其歸為NP-完全問題。 本文從圖鄰接矩陣的特征系統(tǒng)這一角度入手，提出了針對任意圖同構的判定算法。在構建有效描述任意圖鄰接矩陣的基礎上，分別計算兩個矩陣的特征值所對應的特征向量，并依據它們的極大無關組尋找可能的同構對應關系。通過對全體特征值的逐一考察，實現(xiàn)圖同構的判定并確定同構圖的頂點對應關系。 文中詳細介紹了算法和相關應用，完成的工作包括： 1)對已發(fā)表文章中提...

圖的同構判定是圖論學科的基本問題之一。所謂圖的同構，就是指兩個圖的拓撲結構完全相同。從定義看這個問題似乎并不復雜，但它卻是一個世界性難題，多數(shù)學者將其歸為NP-完全問題。 本文從圖鄰接矩陣的特征系統(tǒng)這一角度入手，提出了針對任意圖同構的判定算法。在構建有效描述任意圖鄰接矩陣的基礎上，，分別計算兩個矩陣的特征值所對應的特征向量，并依據它們的極大無關組尋找可能的同構對應關系。通過對全體特征值的逐一考察，實現(xiàn)圖同構的判定并確定同構圖的頂點對應關系。 文中詳細介紹了算法和相關應用，完成的工作包括： 1)對已發(fā)表文章中提出的同構算法進行了回顧，并指明存在的不足； 2)對與算法相關的新概念進行了闡述，主要包括：圖的預處理、描述任意圖的鄰接矩陣、權度序列、特征值序列、同序向量組和關系矩陣等。 3)對算法涉及的性質和定理進行了詳細證明； 4)提出了任意圖的同構判定算法：特征向量法。文中給出詳細的算法描述同時，將本文算法與部分發(fā)表文獻中方法進行了判定性能對比。 5)將算法應用于電路、化學、機械等領域中，實現(xiàn)算法理論價值與應用價值的結合。 大量同構判定實驗表明，隨著判定規(guī)模增大及圖對稱性增強，特征向量法與已有一些方法相比，具有更高的同構判定效率，并且證實多數(shù)情況下此方法是快捷有效的。

展開 

  本文關鍵詞：圖的同構，由筆耕文化傳播整理發(fā)布。