任意圖的同構(gòu)判定及應(yīng)用研究.pdf

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

2、對應(yīng)關(guān)系。 文中詳細介紹了算法和相關(guān)應(yīng)用，完成的工作包括： 1)對已發(fā)表文章中提出的同構(gòu)算法進行了回顧，并指明存在的不足； 2)對與算法相關(guān)的新概念進行了闡述，主要包括：圖的預(yù)處理、描述任意圖的鄰接矩陣、權(quán)度序列、特征值序列、同序向量組和關(guān)系矩陣等。 3)對算法涉及的性質(zhì)和定理進行了詳細證明； 4)提出了任意圖的同構(gòu)判定算法：特征向量法。文中給出詳細的算法描述同時，將本文算法與部分發(fā)表文獻中方法進