[發明專利]一種基于譜分析的圖同構判斷方法

有效

• 申請號: 201310357552.3
• 申請日: 2013-08-15
• 公開（公告）號: CN104376139B
• 公開（公告）日: 2018-10-26
• 發明（設計）人: 曾璇;謝敏;楊帆
• 申請（專利權）人: 復旦大學
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 上海元一成知識產權代理事務所(普通合伙) 31268
• 代理人: 吳桂琴

1.一種基于譜分析的圖同構判斷方法，其特征在于，將大規模純電阻網絡圖建模為非混合無向簡單圖，將二維平面圖映射成一維分布，根據處理后的一維分布的情況來判定兩圖是否同構，其包括：

對圖的Laplace矩陣進行譜分析，計算出第二小特征值所對應的特征向量，對該特征向量進行處理，比較兩處理后的特征向量是否相等，若相等則兩圖同構；所述的對特征向量進行處理的過程如下，先對特征向量的所有元素分別取絕對值，再對絕對值進行升序排列，若兩處理后的特征向量相等，則兩圖同構；

若不相等，則對升序排列的第二小特征值對應的特征向量進行劃分組成粗化圖，對粗化圖進行譜分析判斷同構，若粗化圖不同構，則兩圖不同構；若粗化圖同構，則再對新點里的子圖進行譜分析判斷同構，若子圖也一一同構，則兩圖同構；所述的對升序排列的第二小特征值對應的特征向量劃分，是將值相等的對應頂點劃分在一起，形成新點，用新點構造出粗化圖，對粗化圖進行譜分析；再對新點里的子圖進行譜分析，一一對應同構才判定子圖同構，當粗化圖和子圖都同構，則兩圖同構。

2.按權利要求1所述的基于譜分析的圖同構判斷方法，其特征在于，其包括如下具體步驟：

步驟1：分別讀取純電阻網絡的電路網表文件sp1和sp2，根據網表信息將電路圖轉化為非混合無向簡單圖T＝(V,E)來表示，其中頂點集合V表示電路節點，而邊集合E表示連接節點的電阻；圖中每條邊e(i,j)的權重w(i，j)定義為電路節點i和j之間的電導，上述網表sp1和sp2對應的圖表示為g和h，計算出上述兩圖g和h相應的Laplace矩陣L1和L2；

圖T的Laplace矩陣L定義如下：

步驟2：同構圖的頂點數和邊數都相等；首先判斷兩圖的頂點數V1和V2或者邊數E1和E2是否相等，若不相等，則判定兩圖不同構；若均相等，則執行步驟3；

步驟3：對上述兩圖的Laplace矩陣進行譜分析；利用圖的Laplace矩陣進行特征分解后將得到的特征向量進行分析，即通過計算矩陣的第二小特征值對應的特征向量q，將該特征向量的值取絕對值后進行升序排列得到一維分布q′；若一維分布完全相同，即經過此處理后的兩特征向量q′完全相等，則判定兩圖同構；若不相等，則執行步驟4；

步驟4：由圖映射的一維分布反映出圖頂點的聚類性，將圖T在一維分布的相鄰兩點距離階躍處進行劃分，得到劃分子集{p₁,p₂,…,p_n}；把每個劃分里的頂點聚合在一起，形成一個新點，用所有新點構成一個粗化圖coarseGraph，對兩個電路圖分別形成的粗化圖coarseGraph1和coarseGraph2再進行譜分析判斷是否同構；

聚合每個劃分p_i里的頂點從而形成新點，用新點構成粗化圖coarseGraph，得到粗化圖的Laplace矩陣CL1和CL2；

步驟5：若上述粗化圖coarseGraph1和coarseGraph2的頂點數分別等于原圖的頂點數，則判定兩圖同構；若上述兩個粗化圖的頂點數不相等，則判定兩圖不同構；否則對粗化圖執行步驟3，判定粗化圖是否同構；若粗化圖判定為非同構，則原圖非同構，若粗化圖判定為同構，則執行步驟6；

步驟6：將上述步驟4中得到的每個劃分子集p_i里的頂點再構造成子圖subGraph1和subGraph2，執行步驟3，分別對兩個電路圖對應的兩個劃分子集里的子圖一一對應進行譜分析，判斷是否同構，若所有子圖均一一對應同構，則判定原圖同構，若不同構，則判定原圖不同構。