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

1、圖的同構(gòu)問題一直受到數(shù)學(xué)界與工程技術(shù)界的關(guān)注，其原因主要來自兩個方面：第一，從理論上講，一般認為該問題屬于NP-完全問題；第二，圖的同構(gòu)問題具有很好的應(yīng)用前景，在化學(xué)、運籌學(xué)，計算機科學(xué)、電子學(xué)、網(wǎng)絡(luò)理論等諸多領(lǐng)域都有應(yīng)用，但指數(shù)時間復(fù)雜度的算法以及算法本身適用對象的局限性使得涉及到復(fù)雜圖形同構(gòu)判定的應(yīng)用問題難以入手。 本文提出了面向任意圖的同構(gòu)判定算法并系統(tǒng)的討論了實際應(yīng)用中基于任意圖的建模方法。 在實現(xiàn)上述算法與應(yīng)用

2、過程中，本文完成了以下工作： 1．在分析了簡單圖拓撲結(jié)構(gòu)描述的基礎(chǔ)上提出了新的任意圖拓撲結(jié)構(gòu)描述方法和相應(yīng)的同構(gòu)判定條件。 2．建立了任意圖的伴隨電路模型，采用節(jié)點電壓方法求取電壓，將其作為同構(gòu)判定的參數(shù)，使用物理方法解決圖論問題。 3．針對部分特殊圖形提出了相對位序表的概念，以改進算法在處理這類圖形時的效率。 4．在具體應(yīng)用中引入任意圖建立模型，從而為一類很難采用單一拓撲圖建模的復(fù)雜問題提供了一種新的解