圖的同構(gòu)問(wèn)題算法研究.pdf

1、圖的同構(gòu)問(wèn)題一直受到數(shù)學(xué)界與工程技術(shù)界的關(guān)注，其原因主要來(lái)自兩個(gè)方面：其一，從理論上講，一般認(rèn)為該問(wèn)題屬于NP-完全問(wèn)題；其二，圖的同構(gòu)問(wèn)題具有很好的應(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)用問(wèn)題難以入手。
　　 本文對(duì)圖同構(gòu)問(wèn)題運(yùn)用不同的方法進(jìn)行研究，首先是特殊圖的同構(gòu)問(wèn)題，主要論述了最大外平面圖和樹圖的多項(xiàng)式算法

2、，并給出了必要的推理和改進(jìn)策略。然后針對(duì)精確圖同構(gòu)問(wèn)題，提出基于圖的鄰接矩陣變換的同構(gòu)算法，可以快速判定圖同構(gòu)問(wèn)題，但是并未從根本上在多項(xiàng)式時(shí)間內(nèi)給出問(wèn)題的解。為此，本文后續(xù)部分結(jié)合智能計(jì)算中的遺傳算法、神經(jīng)網(wǎng)絡(luò)算法以及粒子群算法，對(duì)圖同構(gòu)問(wèn)題進(jìn)行求解。遺傳算法中，把同構(gòu)問(wèn)題轉(zhuǎn)化為求最小值問(wèn)題，并對(duì)遺傳算子進(jìn)行優(yōu)化改進(jìn)，通過(guò)采取不同進(jìn)化策略，使得種群在求解過(guò)程中保持良好的多樣性和收斂性，得到了較好的實(shí)驗(yàn)結(jié)果。在神經(jīng)網(wǎng)絡(luò)部分介紹了一種基于

3、Hopfield網(wǎng)絡(luò)模型改進(jìn)算法，把遺傳算法同神經(jīng)網(wǎng)絡(luò)算法結(jié)合起來(lái)，有效地避免問(wèn)題陷入局部最優(yōu)解，并給出同構(gòu)算法并對(duì)結(jié)果進(jìn)行分析。最后針對(duì)同構(gòu)問(wèn)題給出粒子群計(jì)算模型，提出離散粒子群算法，對(duì)粒子群中的速度、位置重新定義，用于解決同構(gòu)問(wèn)題。由于同構(gòu)問(wèn)題的特殊性，在對(duì)算法的可行性、有效性測(cè)試操作中，本文采用多次實(shí)驗(yàn)，數(shù)據(jù)分析的方式對(duì)算法進(jìn)行分析，雖然取得了較好的結(jié)果，但從改進(jìn)策略角度和問(wèn)題判定準(zhǔn)確性角度，各種算法仍有待改進(jìn)的空間，這也是我們以