基于關聯點度矩陣的無向圖同構判定

陳中標

摘 要：文章給出判定2個無向圖同構的重要概念：關聯點度矩陣和完全圈矩陣。首先對兩無向圖頂點的度序列進行非減排序編號，若兩無向圖和為非正則圖，則同構于的充要條件是和的關聯度矩陣的行相同；若和為正則圖，則同構于的充要條件是和的完全圈矩陣相同。

關鍵詞：圖的同構；關聯點度矩陣；完全圈矩陣；正則圖

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

1 圖同構的相關定義

[參考文獻]

[1]金雄偉，梁立.一種新的改進的判定圖同構的遺傳算法[J].云南師范大學學報，2013（1）：50-52.

[2]候愛民.求解圖同構的判定算法[J].計算機工程與應用，2011（16）：52-54.

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

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

[5]瓚武.應用圖論[M].長沙：國防大學出版社，2006.

[6]丁曉紅，王敏麗.關于圖的同構判定方法的探討[J].大學數學，2006（2）：75-77.

[7]李曉艷.圖的同構判定算法：關聯度系列法及其應用[J].復旦學報：自然科學版，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