简单无向图的同构判定方法

王 卓 王成红

图的同构判定在化学分析、计算机科学、人工智能以及智能决策与控制等领域有着广泛的应用[1-3].上世纪前半叶,与图同构相关的问题主要围绕图的邻接矩阵及其性质、邻接矩阵(拉普拉斯矩阵)特征值及其应用展开[4],取得了若干重要的理论成果和一大批应用成果.

上世纪70 年代,Karp、Garey 和Johnson 等认为图的同构判定问题是少数几个既不能归类为P,也不能归类为NP的问题[1,3].自此之后,该问题成为理论计算机领域的公开问题并受到广泛重视.

1982 年,Luks 使用有限群等数学工具给出了一个当时最好的两图同构判定算法,该算法的时间复杂度是(n为图的顶点数)[5-6].此后40 年来,图的同构判定问题引起了众多学者的关注,几百篇这方面的文章得以在不同的学术期刊上发表[1].2015 年,Babai 在Luks 算法的基础上,利用群作用下轨道间的局部关系和群的正则分解技术,给出了两图同构判定问题的拟多项式算法,该算法的时间复杂度是 e xp((logn)O(1))[5].上述算法的目的在于给出同构判定问题的复杂度上界,并不能直接用于具体图的同构判定[5].Babai 的工作虽然是一个重要进展,但图的同构判定问题是否在多项式时间内可解仍然悬而未决[1].

图的同构判定问题的另一研究路径是设计可执行的具体判定算法,大致可以分为传统判定算法和非传统判定算法两种情况.传统判定算法有两类:1)针对一些特殊图(如树和极大外平面图等)[7-8]的同构判定算法(如Ullman 算法、Schmidt 算法、Falkenhainer 算法和Messmer 算法等)[9].这些算法主要使用“搜索、标号和回溯”技术且被证明具有多项式时间复杂度;2)针对一般简单图的判定算法,如一些放在因特网上用于测试两图是否同构的程序(如Nauty、Saucy、Bliss、Conauto 和Traces等)[3,5].这些程序运行速度很快,但算法的时间复杂度分析和正确性证明却没有公开报道.非传统判定算法也有两类: 1)基于遗传算法、神经网络和粒子群算法等的智能同构判定算法.这些算法将图的同构判定问题转化为一类优化求解问题,但其判定结果并不完全可靠.2)基于生物(DNA)计算[9]和量子计算的判定算法.这类算法虽然高效,但实现比较困难而且也不能回答图的同构判定是P还是NP问题.

本文的主要思路和贡献是: 1)给出了矩阵同构变换和简单无向图距离矩阵的定义,将基于邻接矩阵的同构判定条件推广到简单无向图距离矩阵.2)针对简单无向连通图的同构判定问题,给出了基于距离矩阵特征多项式的同构判定条件.因用数值方法求解特征多项式会产生计算误差,故该判定条件仅适合中小规模简单无向连通图的同构判定[10-11].3)为避免计算误差对判定结果的影响,给出了简单无向连通图距离矩阵列和向量与图的距离谱的定义,并进而给出了基于距离矩阵的秩与列和向量的同构判定条件.该判定条件不产生计算误差,因而适合大规模简单无向连通图的同构判定.上述两个判定条件均是充要条件且均具有多项式时间复杂度,将这些条件用于简单无向不连通图的各个连通子图,就可解决简单无向不连通图的同构判定问题.

1 相关概念和预备知识

1.1 相关概念

若仅考虑顶点间的邻接关系和拓扑结构,则图可视为由若干个顶点和若干条边连接成的网络.

定义 1[4,12-13]. 图G是一个二元组,记作G=〈V,E〉,其中:

1)V={v1,v2,···,vn||V|=n,n≥1},vi∈V称为G的顶点,V称为G的顶点集;

2)E={e1,e2,···,em||E|=m,m≥0},ej∈E称为G的边,E称为G的边集;

3)∀ej∈E:ej为无向边时,称G为无向图,ej为有向边时,称G为有向图;

4)连接同一个顶点的边称为自环,两个顶点间的多条无向边或多条方向相同的有向边称为重边.无自环和重边的图称为简单图,否则称为复杂图.

本文分析和讨论的图均是顶点和边为有限数的无向图.

定义 2[12-14]. 设G=〈V,E〉 为无向图,V={v1,v2,···,vn}.若顶点vi和vj(1≤i,j ≤n)之间有k(k≥0 为非负整数)条边,令aij=k;称由元素aij构成的矩阵A(aij)∈Rn×n为无向图G的邻接矩阵.

在定义2 中,k=0 表示无边,aii=k表示顶点vi有k个自环.如此,定义2 既适合简单无向图也适合复杂无向图.

定义 3[4,12-14]. 设G=〈V,E〉 为无向图,V={v1,v2,···,vn}(n≥2),E={e1,e2,···,em} (m≥1).1)G中顶点与边的交替序列W=v1e1v2e2···vkekvk+1(k ≤n-1)称为G的链,各边互异的链称为迹,各顶点互异的链称为路;当W是路时,W中的边数k称为W的长度,记作k=|W|.2)设vi和vj是V中的任意两个顶点,当vi和vj之间有s条路Wp(1≤p ≤s)时,称d(vi,vj)=min{kp=|Wp||1≤p ≤s} 为vi和vj之间的距离;若vi和vj之间无路(G不连通),约定d(vi,vj)=∞.3)称d(G)=max{d(u,v)|u,v∈V} 为G的直径.

图的同构问题可以这样表述: 给定两个图,当忽略图中顶点的标号、顶点间的相对位置、边的长短和曲直信息时,问这两个图是否具有相同的结构? 现有文献中关于简单图的同构定义已有多个[4,13-14],这些定义虽然表述略有不同但彼此等价.下面,我们给出一个既适合简单图又适合复杂图的同构定义.

定义 4[4].设G1=〈V1,E1〉 和G2=〈V2,E2〉 是两个无向(有向)图.若存在一个从V1到V2的一一映射g:∀vi,vj∈V1,vi至vj有k条无向(有向)边,当且仅当g(vi),g(vj)∈V2,且g(vi)至g(vj)也有k条无向(有向)边,则称G1和G2同构,记作G1∼=G2.

1.2 预备知识

定义 5[15]. 设In∈Rn×n为单位矩阵,交换In的第i行与第j行(或第i列与第j列)所得的矩阵P(i,j)称为对换矩阵,对换矩阵的乘积称为置换矩阵.

引理 1[15]. 对换矩阵和置换矩阵具有如下性质:

由引理1 中的性质2)和性质6)可知,对换矩阵和In也是置换矩阵.

定义 6.设A,B ∈Rn×n,Ω⊂Rn×n为全体n阶置换矩阵的集合.若存在置换矩阵Q∈Ω,使得A=QTBQ,则称A与B同构,记作A∼=B;此外,称QTBQ是对B的同构变换.

任给一个无向(有向)图G=〈V,E〉,|V|=n≥2.对V中每个顶点指定一个1～n的标号,可以得到一个标号向量=[σi1σi2··· σin]∈R1×n({σi1,···,σin}是 {1,2,···,n} 的一个置换)和一个邻接矩阵A∈Rn×n.设π1和π2是V的任意两个标号向量,A与B分别是图G相应于π1和π2的邻接矩阵.当π1=π2时,A=B;当π1≠π2时,A≠B(或A=B).

设π1≠π2.逐次不重复地对调π1中两个分量的位置(对换两个顶点的标号),经有限次对调就可将π1变成π2,同时将A变成B.对调顶点vi与vj的标号,π1将变为P(i,j)π1(P(i,j)为对换矩阵),A将变为P(i,j)APT(i,j).其中,P(i,j)APT(i,j)是对调A的第i行和第j行之后,再对调第i列和第j列所得的矩阵.设顶点标号经m(m≥1)次对调之后π1变成π2,并且第s(1≤s ≤m)次对调所对应的对换矩阵为Ps,则π2=PmPm-1···P1π1=Qπ1(Q=.由引理1 可知,Q∈Ω 为置换矩阵.如此,π1=QTπ2,A=QTBQ.

由上述分析和定义6 可知: 任给无向图G,若A和B是G的两个邻接矩阵,则存在置换矩阵Q ∈Ω,使得A=QTBQ,即同一图的任意两个邻接矩阵彼此同构;邻接矩阵的行列同时互换是同构变换,邻接矩阵的同构变换还是邻接矩阵.

引理 2[12]. 设G1=〈V1,E1〉 和G2= 〈V2,E2〉 是两个图,|V1|=|V2|=n,A与B分别是G1和G2的邻接矩阵.则G1∼=G2的充要条件是存在n阶置换矩阵Q∈Ω,使得A=QTBQ,或A=Q-1BQ.

证明.设存在n阶置换矩阵Q∈Ω,使得A=QTBQ.由定义6 可知,QTBQ是对B的同构变换.因邻接矩阵的同构变换还是同一图的邻接矩阵,故A=QTBQ是G2的邻接矩阵.如此,G1和G2有相同的邻接矩阵A,即G1和G2是同一个图;换言之,G1∼=G2.

设G1∼=G2.当G1和G2同构时,B可经有限次行列同时互换转化为A,即存在n阶置换矩阵Q ∈Ω,使得A=QTBQ.

引理2 表明,两个图同构当且仅当该两图的邻接矩阵同构;若两个图有相同的邻接矩阵,则这两个图同构.容易证明,引理2 中的Q是唯一的.

2 简单无向图的同构判定方法

由定义3 可知,复杂无向图中的自环和多重边中的重边对顶点间的距离没有影响.为区分起见,本节仅讨论简单无向图.

定义 7.设G=〈V,E〉 是简单无向图,V={v1,v2,···,vn},dij=d(vi,vj)表示顶点vi和vj(1≤i,j ≤n)之间的距离: 当i=j时,令dii=0 ;当i≠j且d(vi,vj)=k(d(vi,vj)=∞)时,令dij=k(dij=∞),其中k≥1 为正整数;称由元素dij构成的矩阵D(dij)∈Rn×n为简单无向图G的顶点距离矩阵,简称G的距离矩阵.

因i≠j时,d(vi,vj)=d(vj,vi),所以dij=dji,简单无向图G的距离矩阵D是对称矩阵.与邻接矩阵一样,顶点标号不同时,G的距离矩阵通常也互不相同.

定理 1.设G1=〈V1,E1〉 和G2=〈V2,E2〉 是两个简单无向图,|V1|=|V2|=n≥2,D1与D2分别是G1和G2的距离矩阵;则G1∼=G2的充要条件是存在n阶置换矩阵Q∈Ω,使得D1=QTD2Q,或D1=Q-1D2Q.

证明.设存在n阶置换矩阵Q∈Ω,使得D1=QTD2Q.因Q∈Ω,由定义6 可知,QTD2Q是对D2的同构变换.因QTD2Q只改变D2行与列的排列而不改变D2的元素,故QTD2Q=D1也是G2的距离矩阵.同理,D2=QD1QT也是G1的距离矩阵.如此,D1和D2既是G1的距离矩阵也是G2的距离矩阵.设G1的顶点标号向量为π1,相应的距离矩阵和邻接矩阵分别是D1和A1;G2的顶点标号向量为π2,相应的距离矩阵和邻接矩阵分别是D2和A2.因D1和D2均是G1的距离矩阵,类似第1.2 节的分析可得,当D1=QTD2Q时,π1=QTπ2,A1=QTA2Q.如此,若存在Q∈Ω,使得D1=QTD2Q,则A1=QTA2Q.由引理2 可知,G1∼=G2.

设G1∼=G2.由引理2 可知,存在Q∈Ω,使得A1=QTA2Q.同上分析可得,当A1=QTA2Q时,π1=QTπ2,D1=QTD2Q.这表明,若G1∼=G2,则存在Q∈Ω,使得D1=QTD2Q,或D1=Q-1D2Q.

定理1 表明,两个简单无向图同构当且仅当这两个图的距离矩阵同构;距离矩阵的同构变换还是距离矩阵;距离矩阵的同构性与邻接矩阵的同构性保持一致.

不难理解,定理1 即是引理2 在简单无向图距离矩阵上的推广.

设G=〈V,E〉 是简单无向连通图,|V|=n≥2,D(dij)∈Rn×n是G的距离矩阵.由定义7 可知,D是对角线元素均为零而其他元素全为正整数的对称矩阵.由定义3 和定义7 可知,G的直径可由D的元素求取,即d(G)=max{dij|1≤i,j ≤n}.此外,由D的元素还可求出G中各顶点的离心率和G的半径[4,13].

定义 9.设T ⊂Rn×n(n≥2)表示全体n阶正交矩阵的集合;Ω-={-S|S ∈Ω} 表示全体n阶负置换矩阵的集合;Φ=Ω∪Ω-表示全体n阶置换矩阵和全体n阶负置换矩阵的并集;Θ=T-Φ 表示T中除 Φ 之外全体n阶正交矩阵的集合.

由定义9 和正交矩阵的性质可知: Θ∩Φ=∅(∅为空集),Θ∪Φ=T;∀Q1,Q2∈Φ,Q1Q2∈Φ;∀Q ∈Φ,∀P ∈Θ,QP,PQ ∈Θ ;∀P ∈Θ,∀E ∈Φ,∀Q ∈T且Q≠EPT,QP,PQ ∈Θ.

引理 3[15]. 设A∈Rn×n,则A为正交矩阵的充要条件是存在正交矩阵P∈T,使得

其中,Is与It分别是s阶和t阶单位矩阵,

s+t+2k=n,θj∈R(1≤j ≤k)为实数.

由正交矩阵的定义可知,Pθ和Hθ均是正交矩阵.

定理 2.设A(aij)∈Rn×n(n≥2)是对角线元素均为1 而其他元素均为正整数的对称矩阵,则∀P ∈Θ,PTAP不是正整数矩阵(PTAP的元素不全是正整数).

其中,a1,a2,a3为正整数,δ=±1,θ∈R.如此,

其中,α1(θ)=a1cosθ-a2sinθ,α2(θ)=a1sinθ+a2cosθ,α3(θ)=a3sin 2θ.当δ=1 且θ≠±2lπ(l=0,1,2,···),或δ=-1 且θ≠±hπ(h为奇数)时,P ∈Θ,PTAP不是正整数矩阵.类似n=2 时的分析可得,对一切3 阶正交矩阵Q∈Θ,QTAQ不是正整数矩阵.

其中,A11∈Rs×s,A22∈Rt×t,A33∈R2k×2k均是对角线元素为1 而其他元素为正整数的分块对称矩阵,A12,A13,A23均是分块正整数矩阵;Pθ和Hθ为形如引理3 中的矩阵,s+t+2k=n,θj∈R(1≤j ≤k)为实数.如此,

引理4[15]. 设A,B ∈Rn×n为对称矩阵,则det(λIn-A)=det(λIn-B)的充要条件是存在正交矩阵P∈T,使得A=PTBP=P-1BP.

基于定理1、定理2 和引理4,下面给出两个简单无向连通图是否同构的判定条件.

定理 3.设G1=〈V1,E1〉 和G2=〈V2,E2〉 是两个简单无向连通图,|V1|=|V2|=n≥2,D1与D2分别是G1和G2的距离矩阵,则G1∼=G2的充要条件是 det(λIn-D1)=det(λIn-D2).

证明.设 det(λIn-D1)=det(λIn-D2).因D1和D2均是实对称矩阵,由引理4 可知,当det(λIn-D1)=det(λIn-D2)时,存在n阶正交矩阵P∈T,使得D1=PTD2P.下面证明,∀n≥2,P∈Ω (或P=-S,S∈Ω).假设存在一个P∈Θ,使得D1=PTD2P,则In+D1=PTP+PTD2P=PT(In+D2)P.因In+D1和In+D2均是正整数矩阵,故PT(In+D2)P也是正整数矩阵,这与定理2 的结论矛盾.如此,P∈/Θ.因 Θ∩Φ=∅,Θ∪Φ=T,故当P∈T且P∈/Θ 时,必有P ∈Φ.换言之,∀n≥2,当D1和D2均是距离矩阵且det(λIn-D1)=det(λIn-D2)时,一定存在P∈Ω (或P=-S,S∈Ω),使得D1=PTD2P.由定理1 可知,G1∼=G2.

设G1∼=G2. 由定理1 可知,当G1∼=G2时,存在n阶置换矩阵P∈Ω,使得D1=PTD2P.因r(D)和do(D)均是矩阵同构变换下的不变量,故当D1=PTD2P时,r(D1)=r(D2)且do(D1)=do(D2).

因距离矩阵D是非负整数矩阵,故求解r(D)和do(D)均不会产生计算误差.如此,定理5 为无误差判定条件.此外,因求解 det(λIn-D)比求解r(D)和do(D)困难得多,故定理5 比定理3 在计算便利性方面更具优势.上述两个优点表明,定理5更适合大规模简单无向连通图的同构判定.

有了推论4,两个无向树的同构判定问题就变为一个简单的算术问题.

不难理解,将定理3 特别是定理5 用于简单无向不连通图的各个连通子图或将推论4 用于无向森林的各个无向树,就可解决任意简单无向不连通图的同构判定问题.

例 1.试判定下列各对应图(如图1 所示)是否同构.

图1 例1 各对应图Fig.1 Corresponding figures of Example 1

解.1)G1和G2均是无向树(毛虫形[4,16,19]),按图中顶点标号,经计算可得G1和G2的距离矩阵分别为

由D1和D2可得,

因ds(D1)≠ds(D2),由推论3 或推论4 均可判定G1和G2不同构.

此外,G1和G2的邻接矩阵同谱,即ϕ(G1,λ)=ϕ(G2,λ)=λ10-9λ8+26λ6-27λ4+8λ2.若将邻接矩阵特征多项式相等作为判据来判定G1和G2是否同构[16,19],就会得出错误的结果.

2)G3和G4均是3 正则无向图(Wagner 图[1,20]).按图中顶点标号,经计算可得G3和G4的距离矩阵分别为

另一方面,因r(D3)=r(D4)=8;do(D3)=[1111111111111111],do(D4)=[1111111111111111],do(D3)=do(D4);由定理5 可轻松判定G3∼=G4.

3)G5和G6均是3 正则简单无向连通图[3].按图中顶点标号,经计算可得G5和G6的距离矩阵分别为

经计算可得,det(D5)=0,det(D6)=-4352.因 det(D5)≠det(D6),由定理3 可以判定G5和G6不同构.

因ds(D5)=ds(D6)=[304020],但r(D5)≠r(D6),故由推论2 或定理5 亦可判定G5和G6不同构.

4)G7和G8均是3 正则简单无向连通图(Petersen 图[4,13]).按图中顶点标号,经计算可得G7和G8的距离矩阵为

因D7=D8,由定理1、定理3 或定理5 均可判定G7∼=G8.

此外,因图的距离谱不同,故由定理5 可轻松判定G7和G8与G5或G6不同构.

5)G9和G10均是简单无向连通图,按图中标号可得G9和G10的距离矩阵分别为

3 结束语

图的同构关系是一种等价关系.图论在自然科学和社会科学的诸多领域中有着广泛的应用,凡与图的结构相关的分类、聚类、识别与学习等问题均与图的同构判定问题有关.时至今日,图的同构判定问题仍然具有重要的理论和应用价值.

本文给出了简单无向图距离矩阵的定义,将基于邻接矩阵的同构判定条件推广到简单无向图距离矩阵.由简单无向连通图的距离矩阵很容易求得该图的直径(求图的直径是图论中的难题[13])、半径和离心率等[4],而这些整体性结构参数不可能由邻接矩阵得到.此外,距离矩阵是素矩阵而邻接矩阵一般不是素矩阵.正是利用了这些邻接矩阵所没有的整体结构性质,本文给出了基于距离矩阵特征多项式的同构判定条件(定理3).距离矩阵特征多项式不同于邻接矩阵特征多项式,邻接矩阵特征多项式相等仅是两个简单无向连通图同构的必要条件.就无向树而言,随着顶点数趋于无穷大,几乎没有树可被它的邻接矩阵特征值唯一确定[4].为避免特征多项式计算误差对判定结果的影响,本文率先给出了简单无向连通图距离矩阵列和向量与图的距离谱的定义,并进一步给出了基于距离矩阵的秩与列和向量的同构判定条件(定理5).该条件易于验证且不产生计算误差,故更适合大规模简单无向连通图的同构判定.定理3 和定理5 均是充要条件且均具有多项式时间复杂度.针对无向树的同构判定问题,本文还给出了基于距离谱的判定条件(推论4).容易理解,将定理3 特别是定理5 用于简单无向不连通图的各个连通子图或将推论4 用于无向森林的各个无向树,就可解决任意简单无向不连通图的同构判定问题.最后,本文用一些典型例图说明了定理3、定理5、推论4 及其他相关结论的使用方法,其中部分例图(如Wagner 图和Petersen 图)曾被多位学者深入研究或引用过.

本文的主要创新点和贡献可概括为: 1)给出了简单无向图的同构判定条件,这些条件均具有多项式时间复杂度,间接地证明了简单无向图的同构判定问题是P问题;2)不同于现有的图上操作算法(搜索-标号-回溯算法),本文所给的同构判定条件均是数学方程式,不仅便于分析和应用而且便于计算机编程;3)因简单无向图是一大类常见的图且无向树和极大无向外平面图均是简单无向图的真子集,故本文的主要结果是现有工作的一个重要进展.需要说明的是,虽然本文在简单无向图的同构判定问题上有较大进展,但一般(任意)无向或有向图的同构判定是P还是NP问题仍然没有得到解决.

今后,我们将针对简单有向强连通图的同构判定问题开展研究,期望得到一些有理论和实用价值的新结果.