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

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

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