基于關(guān)聯(lián)點(diǎn)度矩陣的無向圖同構(gòu)判定

陳中標(biāo)

摘 要：文章給出判定2個(gè)無向圖同構(gòu)的重要概念：關(guān)聯(lián)點(diǎn)度矩陣和完全圈矩陣。首先對(duì)兩無向圖頂點(diǎn)的度序列進(jìn)行非減排序編號(hào)，若兩無向圖和為非正則圖，則同構(gòu)于的充要條件是和的關(guān)聯(lián)度矩陣的行相同；若和為正則圖，則同構(gòu)于的充要條件是和的完全圈矩陣相同。

關(guān)鍵詞：圖的同構(gòu)；關(guān)聯(lián)點(diǎn)度矩陣；完全圈矩陣；正則圖

圖的同構(gòu)判定問題是圖論的一個(gè)難題，至今沒有一個(gè)簡單明了的方法來判斷兩圖是否同構(gòu)。現(xiàn)有的方法有金雄偉、梁立的《一種新的改進(jìn)的判定圖同構(gòu)的遺傳算法》，侯愛民的《求解圖同構(gòu)的判定算法》，郭美美的《基于CAD判斷圖同構(gòu)》等。筆者也就此問題作簡單探討，引出了關(guān)聯(lián)點(diǎn)度矩陣和完全圈矩陣的概念，并且給出了判定無向圖同構(gòu)的相關(guān)定理。

1 圖同構(gòu)的相關(guān)定義

[參考文獻(xiàn)]

[1]金雄偉，梁立.一種新的改進(jìn)的判定圖同構(gòu)的遺傳算法[J].云南師范大學(xué)學(xué)報(bào)，2013（1）：50-52.

[2]候愛民.求解圖同構(gòu)的判定算法[J].計(jì)算機(jī)工程與應(yīng)用，2011（16）：52-54.

[3]郭美美.基于CAD判斷圖同構(gòu)[J].圖形圖像，2014（6）：49-51.

[4]汪毅，龔世才.圖論導(dǎo)引[M].北京：人民郵電出版社，2007.

[5]瓚武.應(yīng)用圖論[M].長沙：國防大學(xué)出版社，2006.

[6]丁曉紅，王敏麗.關(guān)于圖的同構(gòu)判定方法的探討[J].大學(xué)數(shù)學(xué)，2006（2）：75-77.

[7]李曉艷.圖的同構(gòu)判定算法：關(guān)聯(lián)度系列法及其應(yīng)用[J].復(fù)旦學(xué)報(bào)：自然科學(xué)版，2001（3）：323.

The Improvement and Analysis of the Regular Graph Isomorphism Algorithm

Chen Zhongbiao

（Wuxi Technology and Professional College， Wuxi 214000， China）

Abstract： This article gives two important concepts of undirected graph isomorphism which is correlation degree matrix and full circle matrix. First，gives the two undirected graphs vertex degree sequence for Not reduced order and serial number. Then， if the two undirected graphand is a Irregular figure， the sufficient and necessary condition of they are isomorphism is at the same line of correlation matrix. If the two undirected graphand is a regular figure， the sufficient and necessary condition of they are isomorphism is they completely same circle matrix.

Key words： graph isomorphism； correlation degree matrix； full circle matrix； regular graph