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

圖的同構(gòu)判定是圖論學(xué)科的基本問題之一。所謂圖的同構(gòu)，就是指兩個圖的拓?fù)浣Y(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)系。通過對全體特征值的逐一考察，實(shí)現(xiàn)圖同構(gòu)的判定并確定同構(gòu)圖的頂點(diǎn)對應(yīng)關(guān)系。 文中詳細(xì)介紹了算法和相關(guān)應(yīng)用，完成的工作包括： 1)對已發(fā)表文章中提...

圖的同構(gòu)判定是圖論學(xué)科的基本問題之一。所謂圖的同構(gòu)，就是指兩個圖的拓?fù)浣Y(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)系。通過對全體特征值的逐一考察，實(shí)現(xiàn)圖同構(gòu)的判定并確定同構(gòu)圖的頂點(diǎn)對應(yīng)關(guān)系。 文中詳細(xì)介紹了算法和相關(guān)應(yīng)用，完成的工作包括： 1)對已發(fā)表文章中提出的同構(gòu)算法進(jìn)行了回顧，并指明存在的不足； 2)對與算法相關(guān)的新概念進(jìn)行了闡述，主要包括：圖的預(yù)處理、描述任意圖的鄰接矩陣、權(quán)度序列、特征值序列、同序向量組和關(guān)系矩陣等。 3)對算法涉及的性質(zhì)和定理進(jìn)行了詳細(xì)證明； 4)提出了任意圖的同構(gòu)判定算法：特征向量法。文中給出詳細(xì)的算法描述同時，將本文算法與部分發(fā)表文獻(xiàn)中方法進(jìn)行了判定性能對比。 5)將算法應(yīng)用于電路、化學(xué)、機(jī)械等領(lǐng)域中，實(shí)現(xiàn)算法理論價值與應(yīng)用價值的結(jié)合。 大量同構(gòu)判定實(shí)驗(yàn)表明，隨著判定規(guī)模增大及圖對稱性增強(qiáng)，特征向量法與已有一些方法相比，具有更高的同構(gòu)判定效率，并且證實(shí)多數(shù)情況下此方法是快捷有效的。

展開 

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