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

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

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