本文選題：同構(gòu)圖 + Floyd算法　； 參考：《西南師范大學(xué)學(xué)報(bào)(自然科學(xué)版)》2017年03期

【摘要】：首先,分析判別同構(gòu)圖的一種常用實(shí)現(xiàn)方法:基于鄰接矩陣存儲(chǔ),并討論其存在的時(shí)間復(fù)雜度為O(N!).接著,針對(duì)兩圖中結(jié)點(diǎn)數(shù)、邊數(shù)、每個(gè)結(jié)點(diǎn)的度均相同的特殊圖形提出無向無權(quán)圖同構(gòu)判別的另一算法:采用結(jié)點(diǎn)之間距離及關(guān)聯(lián)邊進(jìn)行判別.最后通過實(shí)例進(jìn)行算法測(cè)試和比較,證明了該算法是完全行之有效的.
[Abstract]:Firstly, a common method to distinguish the same composition: memory based on adjacent matrix is analyzed, and the time complexity of its existence is discussed as O (N!). Then, another algorithm for isomorphism discrimination of undirected unauthorized graph is proposed for the special graph with the same number of nodes, edge numbers and the same degree of each node in two graphs: the distance between nodes and the associated edges are used to judge the isomorphism of the undirected unauthorized graph. Finally, the algorithm is tested and compared with an example, and it is proved that the algorithm is completely effective.
【作者單位】： 運(yùn)城學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系;
【基金】：山西省運(yùn)城學(xué)院131人才專項(xiàng)(JG201634)
【分類號(hào)】：O157.5

【參考文獻(xiàn)】

相關(guān)期刊論文 前8條

1 趙路;王建鋒;;圖的第四大Q-特征值[J];西南師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2016年04期

2 吳炎;林越;;局部環(huán)上n階矩陣的{1}-逆作成的集合及其特征性質(zhì)[J];西南師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2015年12期

3 謝敏;楊帆;曾璇;;無向圖的層次化譜分析同構(gòu)判定算法[J];計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào);2015年11期

4 侯愛民;;求解圖同構(gòu)的判定算法[J];計(jì)算機(jī)工程與應(yīng)用;2011年16期

5 侯愛民;;圖同構(gòu)的一個(gè)充分必要條件[J];計(jì)算機(jī)工程與應(yīng)用;2009年30期

6 燕子宗;張寶琪;;圖論及其應(yīng)用[J];重慶科技學(xué)院學(xué)報(bào)(自然科學(xué)版);2007年02期

7 李鋒;陸韜;;任意圖同構(gòu)判定及其應(yīng)用[J];復(fù)旦學(xué)報(bào)(自然科學(xué)版);2006年04期

8 李鋒,商慧亮;有向圖的同構(gòu)判定算法:出入度序列法[J];應(yīng)用科學(xué)學(xué)報(bào);2002年03期

相關(guān)博士學(xué)位論文 前1條

1 商慧亮;一種新的圖同構(gòu)判定算法[D];復(fù)旦大學(xué);2009年

相關(guān)碩士學(xué)位論文 前1條

1 趙男;基于MapReduce的分布式極圖構(gòu)造算法研究[D];北京交通大學(xué);2013年

【共引文獻(xiàn)】

相關(guān)期刊論文 前10條

1 王文霞;;無向無權(quán)圖同構(gòu)判別算法[J];西南師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2017年03期

2 馬紀(jì)英;陳文燕;于金青;;三角矩陣環(huán)及其上模的同調(diào)性分析[J];西南師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2016年11期

3 張宗杰;吳炎;;對(duì)角線元為數(shù)量冪等矩陣的上三角矩陣及其應(yīng)用[J];西南師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2016年08期

4 陳中標(biāo);;基于關(guān)聯(lián)點(diǎn)度矩陣的無向圖同構(gòu)判定[J];無線互聯(lián)科技;2016年07期

5 羅賢海;李濤;;賦權(quán)混合圖的拓?fù)滢D(zhuǎn)化與同構(gòu)判別[J];陶瓷學(xué)報(bào);2014年04期

6 王文霞;王春紅;;基于無向圖轉(zhuǎn)有向圖的同構(gòu)判別[J];山西師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2014年02期

7 王文霞;;有向圖的同構(gòu)判定算法:出入度序列法[J];山西大同大學(xué)學(xué)報(bào)(自然科學(xué)版);2014年02期

8 商慧亮;劉洋;柳志棟;董文杰;李鋒;;改進(jìn)電路模擬法的應(yīng)用——同構(gòu)混合開關(guān)拓?fù)浔孀R(shí)[J];應(yīng)用科學(xué)學(xué)報(bào);2014年02期

9 王建新;徐r，

本文編號(hào)：2096671