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

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

1982年, Luks使用有限群等数学工具给出了一个当时最好的两图同构判定算法, 该算法的时间复杂度是$\exp ( {\text{O}}({\sqrt {n\log n} } ) )$ ($ n $为图的顶点数)^[5-6]. 此后40年来, 图的同构判定问题引起了众多学者的关注, 几百篇这方面的文章得以在不同的学术期刊上发表^[1]. 2015年, Babai在Luks算法的基础上, 利用群作用下轨道间的局部关系和群的正则分解技术, 给出了两图同构判定问题的拟多项式算法, 该算法的时间复杂度是$\exp({{{( {\log n} )}}}^{\rm{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 = \left\langle {V,E} \right\rangle $, 其中:

1) $ V = \left\{ {{v_1},{v_2}, \cdots ,{v_n}\left| {\left| V \right| = n,{\text{ }}n \ge 1} \right.} \right\} $, $ {v_i} \in V $称为$ G $的顶点, $ V $称为$ G $的顶点集;

2) $ E = \left\{ {{e_1},{e_2}, \cdots ,{e_m}\left| {\left| E \right| = m,{\text{ }}m \ge 0} \right.} \right\} $, $ {e_j} \in E $称为$ G $的边, $ E $称为$ G $的边集;

3) $ \forall {e_j} \in E $: $ {e_j} $为无向边时, 称$ G $为无向图, $ {e_j} $为有向边时, 称$ G $为有向图;

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

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

定义 2^[12-14]. 设$ G = \langle {V,E} \rangle $为无向图, $V = \{ {v_1}, {v_2}, \cdots ,{v_n} \}$. 若顶点$ {v_i} $ 和 $ {v_j} $$ (1 \le i,{\text{ }} $ $ j \le n) $ 之间有 $ k $($ k \ge 0 $为非负整数)条边, 令$ {a_{ij}} = k $; 称由元素$ {a_{ij}} $构成的矩阵$ A( {{a_{ij}}} ) \in {{\bf{R}}^{n \times n}} $为无向图$ G $的邻接矩阵.

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

定义 3^{[4, 12-14]}. 设$ G = \langle {V,E} \rangle $为无向图, $V = \{ {v_1}, {v_2}, \cdots ,{v_n} \}\;( {n \ge 2} )$, $ E = \{ {{e_1},{e_2}, \cdots ,{e_m}} \} $ $ ( {m \ge 1} ) $. 1) $ G $ 中顶点与边的交替序列 $W\; =\; {v_1}{e_1}{v_2}{e_2}\; \cdots {v_k}{e_k}{v_{k + 1}}{\text{ }}( {k \le n - 1} )$称为$ G $的链, 各边互异的链称为迹, 各顶点互异的链称为路; 当$ W $是路时, $ W $中的边数$ k $称为$ W $的长度, 记作$ k = | W | $. 2) 设$ {v_i} $和$ {v_j} $是$ V $中的任意两个顶点, 当$ {v_i} $和$ {v_j} $之间有$ s $条路$ {W_p}{\text{ }}( {1 \le p \le s} ) $ 时, 称$ d( {{v_i},{v_j}} ) = \min $$\{ {k_p} = | {{W_p}} || 1 \le p \le s \}$为$ {v_i} $和$ {v_j} $ 之间的距离; 若$ {v_i} $和$ {v_j} $ 之间无路($ G $不连通), 约定$ d( {{v_i},{v_j}} ) = \infty $. 3) 称$d( G ) = \max \{ d( u, v )| u $, $ {v \in V} \} $为$ G $的直径.

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

定义 4^[4]. 设$ {G_{\text{1}}} = \left\langle {{V_{\text{1}}},{E_{\text{1}}}} \right\rangle $和$ {G_2} = $$ \left\langle {{V_2},{E_{\text{2}}}} \right\rangle $是两个无向(有向)图. 若存在一个从$ {V_1} $到$ {V_2} $的一一映射$ g $: $ \forall {v_i},{v_j} \in {V_1} $, $ {v_i} $至$ {v_j} $有$ k $条无向(有向)边, 当且仅当$ g\left( {{v_i}} \right) $, $ g\left( {{v_j}} \right) \in {V_2} $, 且$ g\left( {{v_i}} \right) $至$ g\left( {{v_j}} \right) $也有$ k $条无向(有向)边, 则称$ {G_1} $和$ {G_2} $同构, 记作$ {G_1} \cong {G_2} $.

1.2   预备知识

定义 5^[15]. 设$ {I_n} \in {{\bf{R}}^{n \times n}} $为单位矩阵, 交换$ {I_n} $的第$ i $ 行与第$ j $ 行(或第$ i $ 列与第$ j $ 列)所得的矩阵$ P\left( {i,j} \right) $称为对换矩阵, 对换矩阵的乘积称为置换矩阵.

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

1) $ \det \left( {P\left( {i,j} \right)} \right) = - 1 $, $ {P^{ - 1}}\left( {i,j} \right) = P\left( {i,j} \right) $;

2) 置换矩阵的乘积仍是置换矩阵;

3) 设$ Q $是置换矩阵, 则$ \det \left( Q \right) = \pm 1 $;

4) 设$ Q $是置换矩阵, 则$ {Q^{\text{T}}} $和$ {Q^{ - 1}} $也是置换矩阵, 且$ {Q^{\text{T}}} = {Q^{ - 1}} $;

5) 置换矩阵是正交矩阵;

6) 置换矩阵是幂幺矩阵, 即若$ Q $是置换矩阵, 则$ {Q^m} = {I_n} $, $ m $是自然数.

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

定义 6. 设$ A,B \in {{\bf{R}}^{n \times n}} $, $ \Omega \subset {{\bf{R}}^{n \times n}} $为全体$ n $阶置换矩阵的集合. 若存在置换矩阵$ Q \in \Omega $, 使得$ A = {Q^{\text{T}}}BQ $, 则称$ A $与$ B $同构, 记作$ A \cong B $; 此外, 称$ {Q^{\text{T}}}BQ $是对$ B $的同构变换.

任给一个无向(有向)图$ G = \left\langle {V,E} \right\rangle $, $ \left| V \right| = n \ge 2 $. 对$ V $中每个顶点指定一个1 ~ $ n $的标号, 可以得到一个标号向量$ \pi _i^{\text{T}} = \left[ {{\sigma _i}_1{\text{ }}{\sigma _{i2}}{\text{ }} \cdots {\text{ }}{\sigma _{in}}} \right] \in {{\bf{R}}^{1 \times n}} $($\{ {\sigma _{i1}}, \cdots ,{\sigma _{in}}\}$是$ \left\{ {1,2, \cdots ,n} \right\} $的一个置换)和一个邻接矩阵$ A \in {{\bf{R}}^{n \times n}} $. 设$ {\pi _1} $ 和$ {\pi _2} $ 是$ V $的任意两个标号向量, $ A $与$ B $分别是图$ G $相应于$ {\pi _1} $和$ {\pi _2} $的邻接矩阵. 当$ {\pi _1} = {\pi _2} $时, $ A = B $; 当$ {\pi _1} \ne {\pi _2} $时, $ A \ne B $ (或$ A = B $).

设$ {\pi _1} \ne {\pi _2} $. 逐次不重复地对调$ {\pi _1} $中两个分量的位置(对换两个顶点的标号), 经有限次对调就可将$ {\pi _1} $变成$ {\pi _2} $, 同时将$ A $变成$ B $. 对调顶点$ {v_i} $与$ {v_j} $的标号, $ {\pi _1} $将变为$ P( {i,j} ){\pi _1} $($ P( {i,j} ) $为对换矩阵), $ A $将变为$ P( {i,j} )A{P^{\text{T}}}( {i,j} ) $. 其中, $ P( {i,j} )A{P^{\text{T}}}( {i,j} ) $是对调$ A $的第$ i $行和第$ j $行之后, 再对调第$ i $列和第$ j $列所得的矩阵. 设顶点标号经 $ m $$ ( {m \ge 1} ) $ 次对调之后$ {\pi _1} $变成$ {\pi _2} $, 并且第$ s $$ ( {1 \le s \le m} ) $次对调所对应的对换矩阵为$ {P_s} $, 则$ {\pi _2} = {P_m}{P_{m - 1}} \cdots {P_1}{\pi _1} = Q{\pi _1} $ $ ( Q = {P_m}{P_{m - 1}} { \cdots {P_1}} ) $, $B = {P_m}{P_{m - 1}} \cdots {P_1}AP_1^{\text{T}} \cdots P_{m - 1}^{\text{T}}\times P_m^{\text{T}} =QA{Q^{\text{T}}}$. 由引理1可知, $ Q \in \Omega $为置换矩阵. 如此, $ {\pi _1} = {Q^{\text{T}}}{\pi _2} $, $ A = {Q^{\text{T}}}BQ $.

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

引理 2^[12]. 设$ {G_{\text{1}}} = \left\langle {{V_{\text{1}}},{E_{\text{1}}}} \right\rangle $和$ {G_2} = $ $ \left\langle {{V_{\text{2}}},{E_{\text{2}}}} \right\rangle $是两个图, $ \left| {{V_1}} \right| = \left| {{V_2}} \right| = n $, $ A $与$ B $分别是$ {G_1} $和$ {G_2} $的邻接矩阵. 则$ {G_1} \cong {G_2} $的充要条件是存在$ n $阶置换矩阵$ Q \in \Omega $, 使得$ A = {Q^{\text{T}}}BQ $, 或$ A = {Q^{ - 1}}BQ $.

证明. 设存在$ n $阶置换矩阵$ Q \in \Omega $, 使得$ A = {Q^{\text{T}}}BQ $. 由定义6可知, $ {Q^{\text{T}}}BQ $是对$ B $的同构变换. 因邻接矩阵的同构变换还是同一图的邻接矩阵, 故$ A = {Q^{\text{T}}}BQ $是$ {G_2} $的邻接矩阵. 如此, $ {G_1} $和$ {G_2} $有相同的邻接矩阵$ A $, 即$ {G_1} $和$ {G_2} $是同一个图; 换言之, $ {G_1} \cong {G_2} $.

设$ {G_1} \cong {G_2} $. 当$ {G_1} $和$ {G_2} $同构时, $ B $可经有限次行列同时互换转化为$ A $, 即存在$ n $阶置换矩阵$ Q \in \Omega $, 使得$ A = {Q^{\text{T}}}BQ $. □

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

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

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

定义 7. 设$ G = \langle {V,E} \rangle $是简单无向图, $V = \{ {v_1}, {v_2}, \cdots ,{v_n}\}$, $ {d_{ij}} = d( {{v_i},{v_j}} ) $表示顶点$ {v_i} $和$ {v_j} $$ ( 1 \le i, j \le n ) $之间的距离: 当$ i = j $时, 令$ {d_{ii}} = 0 $; 当$ i \ne j $且$ d( {{v_i},{v_j}} ) = k $ $ ( {d( {{v_i},{v_j}} ) = \infty } ) $ 时, 令$ {d_{ij}} = k $$ ( {d_{ij}} = $ $ \infty ) $, 其中$ k \ge 1 $为正整数; 称由元素$ {d_{ij}} $构成的矩阵$ D( {{d_{ij}}} ) \in {{\bf{R}}^{n \times n}} $为简单无向图$ G $的顶点距离矩阵, 简称$ G $的距离矩阵.

因$ i \ne j $时, $ d\left( {{v_i},{v_j}} \right) = d\left( {{v_j},{v_i}} \right) $, 所以$ {d_{ij}} = {d_{ji}} $, 简单无向图$ G $的距离矩阵$ D $是对称矩阵. 与邻接矩阵一样, 顶点标号不同时, $ G $的距离矩阵通常也互不相同.

定理 1. 设$ {G_{\text{1}}} = \left\langle {{V_{\text{1}}},{E_{\text{1}}}} \right\rangle $和$ {G_{\text{2}}} = \left\langle {{V_{\text{2}}},{E_{\text{2}}}} \right\rangle $是两个简单无向图, $ \left| {{V_1}} \right| = \left| {{V_2}} \right| = n \ge 2 $, $ {D_1} $与$ {D_2} $分别是$ {G_1} $和$ {G_2} $的距离矩阵; 则$ {G_1} \cong {G_2} $的充要条件是存在$ n $阶置换矩阵$ Q \in \Omega $, 使得$ {D_1} = {Q^{\text{T}}}{D_2}Q $, 或$ {D_1} = {Q^{ - 1}}{D_2}Q $.

证明. 设存在$ n $阶置换矩阵$ Q \in \Omega $, 使得$ {D_1} = {Q^{\text{T}}}{D_2}Q $. 因$ Q \in \Omega $, 由定义6可知, $ {Q^{\text{T}}}{D_2}Q $是对$ {D_2} $的同构变换. 因$ {Q^{\text{T}}}{D_2}Q $只改变$ {D_2} $行与列的排列而不改变$ {D_2} $的元素, 故$ {Q^{\text{T}}}{D_2}Q = {D_1} $也是$ {G_2} $的距离矩阵. 同理, $ {D_2} = Q{D_1}{Q^{\text{T}}} $也是$ {G_1} $的距离矩阵. 如此, $ {D_1} $和$ {D_2} $既是$ {G_1} $的距离矩阵也是$ {G_2} $的距离矩阵. 设$ {G_1} $的顶点标号向量为$ {\pi _1} $, 相应的距离矩阵和邻接矩阵分别是$ {D_1} $和$ {A_1} $; $ {G_2} $的顶点标号向量为$ {\pi _2} $, 相应的距离矩阵和邻接矩阵分别是$ {D_2} $和$ {A_2} $. 因$ {D_1} $和$ {D_2} $ 均是$ {G_1} $的距离矩阵, 类似第1.2节的分析可得, 当$ {D_1} = {Q^{\text{T}}}{D_2}Q $ 时, $ {\pi _1} = {Q^{\text{T}}}{\pi _2} $, $ {A_1} = {Q^{\text{T}}}{A_2}Q.$ 如此, 若存在$ Q \in \Omega, $ 使得$ {D_1} = {Q^{\text{T}}}{D_2}Q, $ 则$ {A_1} = {Q^{\text{T}}}{A_2}Q. $ 由引理2可知, $ {G_1} \cong {G_2}. $

设$ {G_1} \cong {G_2} $. 由引理2可知, 存在$ Q \in \Omega $, 使得$ {A_1} = {Q^{\text{T}}}{A_2}Q $. 同上分析可得, 当$ {A_1} = {Q^{\text{T}}}{A_2}Q $时, $ {\pi _1} = {Q^{\text{T}}}{\pi _2} $, $ {D_1} = {Q^{\text{T}}}{D_2}Q $. 这表明, 若$ {G_1} \cong {G_2} $, 则存在$ Q \in \Omega $, 使得$ {D_1} = {Q^{\text{T}}}{D_2}Q $, 或$ {D_1} = {Q^{ - 1}}{D_2}Q $. □

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

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

设$ G = \left\langle {V,E} \right\rangle $是简单无向连通图, $ \left| V \right| = n \ge 2 $, $ D\left( {{d_{ij}}} \right) \in {{\bf{R}}^{n \times n}} $是$ G $的距离矩阵. 由定义7可知, $ D $是对角线元素均为零而其他元素全为正整数的对称矩阵. 由定义3和定义7可知, $ G $的直径可由$ D $的元素求取, 即$ d\left( G \right) = \max \left\{ {{d_{ij}}\left| {1 \le i,j \le n} \right.} \right\} $. 此外, 由$ D $的元素还可求出$ G $中各顶点的离心率和$ G $的半径^{[4, 13]}.

定义 8. 设$ G = \langle {V,E} \rangle $ 是简单无向连通图, $D( {{d_{ij}}} ) \in {{\bf{R}}^{n \times n}}$是$ G $的距离矩阵, $ {d_j} = \sum\nolimits_{i = 1}^n {{d_{ij}}} $$ ( 1 \le j \le n ) $; 对$ {d_j} $进行升序排列, 可得${d_o}( D ) = [ {{{\bar d}_1}}\;\; {{{\bar d}_2}}\;\; \cdots \;\;{{{\bar d}_n}} ]$$ ( {{{\bar d}_1} \le } $ $ {{{\bar d}_2} \le \cdots \le {{\bar d}_n}} ) $, 则$ {d_o}( D ) $是$ D $的列元素之和按升序排列所得的向量, 简称$ {d_o}( D ) $是$ D $的列和向量.

推论 1. 设$ {G_1} = \left\langle {{V_1},{E_1}} \right\rangle $和$ {G_2} = \left\langle {{V_2},{E_2}} \right\rangle $是两个简单无向连通图, $ \left| {{V_1}} \right| = \left| {{V_2}} \right| = n \ge 2 $, $ {D_1} $与$ {D_2} $分别是$ {G_1} $和$ {G_2} $的距离矩阵; 若$ {d_o}\left( {{D_1}} \right) \ne {d_o}\left( {{D_2}} \right) $, 则$ {G_1} $和$ {G_2} $不同构.

证明. 设$ {d_o}( {{D_1}} ) \ne {d_o}( {{D_2}} ) $时, $ {G_1} \cong {G_2} $. 由定理1可知, 当$ {G_1} \cong {G_2} $时, 存在$ n $阶置换矩阵$ Q \in \Omega $, 使得$ {D_1} = {Q^{\text{T}}}{D_2}Q $. 设$ {E_1} = \{ {d_1^{( 1 )},d_2^{( 1 )}, \cdots ,d_n^{( 1 )}} \} $与$ {E_2} = \{ {d_1^{( 2 )},d_2^{( 2 )}, \cdots } {,d_n^{( 2 )}} \} $分别是$ {D_1} $和$ {D_2} $列元素之和构成的集合. 因同构变换只改变矩阵列的排序而不改变列元素之和, 故在不考虑$ {E_2} $元素的排序时, $ {Q^{\text{T}}}{D_2}Q $列元素之和构成的集合仍是$ {E_2} $. 如此, 当$ {G_1} \cong {G_2} $时, $ {D_1} = {Q^{\text{T}}}{D_2}Q $, $ {E_1} = {E_2} $(两集合相等当且仅当它们的元素一一对应相等), $ {E_1} $和$ {E_2} $元素的升序排列相等, 即$ {d_o}( {{D_1}} ) = {d_o}( {{D_2}} ) $, 与推论1条件矛盾, 则$ {G_1} \cong {G_2} $的假设不成立. 综上可知, 当$ {d_o}( {{D_1}} ) \ne {d_o}( {{D_2}} ) $时, $ {G_1} $和$ {G_2} $不同构. □

定义 9. 设$ { T} \subset {{\bf{R}}^{n \times n}} $$ \left( {n \ge 2} \right) $表示全体 $ n $阶正交矩阵的集合; $ {\Omega ^ - } = \left\{ { - S\left| {S \in \Omega } \right.} \right\} $表示全体$ n $阶负置换矩阵的集合; $ \Phi = \Omega \cup {\Omega ^ - } $表示全体$ n $阶置换矩阵和全体$ n $阶负置换矩阵的并集; $ \Theta = { T} - \Phi $表示$ { T} $中除$ \Phi $之外全体$ n $阶正交矩阵的集合.

由定义9和正交矩阵的性质可知: $ \Theta \cap \Phi = \emptyset $($ \emptyset $为空集), $\Theta \cup \Phi = { T}$; $ \forall {Q_1},{Q_2} \in \Phi $, $ {Q_1}{Q_2} \in \Phi $; $ \forall Q \in \Phi $, $ \forall P \in \Theta $, $ QP,PQ \in \Theta $; $ \forall P \in \Theta $, $ \forall E \in \Phi $, $ \forall Q \in { T} $且$ Q \ne E{P^{\text{T}}} $, $ QP,PQ \in \Theta $.

引理 3^[15]. 设$ A \in {{\bf{R}}^{n \times n}} $, 则$ A $为正交矩阵的充要条件是存在正交矩阵$ P \in { T} $, 使得

其中, $ {I_s} $与$ {I_t} $分别是$ s $阶和$ t $阶单位矩阵,

$ s + t + 2k = n $, ${\theta _j} \in {\bf{R}}$$ \left( {1 \le j \le k} \right) $ 为实数.

由正交矩阵的定义可知, $ {P_\theta } $ 和$ {H_\theta } $ 均是正交矩阵.

定理 2. 设$ A\left( {{a_{ij}}} \right) \in {{\bf{R}}^{n \times n}} $$ \left( {n \ge 2} \right) $是对角线元素均为1而其他元素均为正整数的对称矩阵, 则$ \forall P \in \Theta $, $ {P^{\text{T}}}AP $不是正整数矩阵($ {P^{\text{T}}}AP $的元素不全是正整数).

证明. 当$ n = 2 $时, 设

其中, $ a $为正整数, $ \theta \in {\bf{R }}$. 如此,

当$ \theta \ne \pm l\pi $$ \left( {l = 0,1,2, \cdots } \right) $时, $ P \in \Theta $, $ {P^{\text{T}}}AP $不是正整数矩阵. 当$ P \in \Theta $时, 由定义9和引理3可知, 对一切2阶正交矩阵$ E \in \Phi $、$ C \in { T} $且$ C \ne E{P^{ - 1}} $, 则: 1) $ {Q_1} = CP \in \Theta $, $ {Q_2} = PC \in \Theta $, $ {Q_3} = {C^{\text{T}}}PC \in \Theta $; 2) $ Q_1^{\text{T}}A{Q_1} $、$ Q_2^{\text{T}}A{Q_2} $和$ Q_3^{\text{T}}A{Q_3} $均不是正整数矩阵. 故对一切2阶正交矩阵$ Q \in \Theta $, $ {Q^{\text{T}}}AQ $不是正整数矩阵.

当$ n = 3 $时, 设

其中, $ {a_1} $, $ {a_2} $, $ {a_3} $为正整数, $ \delta = \pm 1 $, $ \theta \in {\bf{R}} $. 如此,

其中, $ {\alpha _1}( \theta ) = {a_1}\cos \theta - {a_2}\sin \theta $, $ {\alpha _2}( \theta ) = $$ {a_1}\sin \theta \;+ {a_2}\cos \theta $, $ {\alpha _3}( \theta ) = {a_3}\sin 2\theta $. 当$ \delta = 1 $且$ \theta \ne \pm 2l\pi $$( l = 0,1,2, \cdots )$, 或$ \delta = - 1 $且$ \theta \ne \pm h\pi $($ h $为奇数)时, $ P \in \Theta $, $ {P^{{\rm{T}}} }AP $不是正整数矩阵. 类似$ n = 2 $时的分析可得, 对一切3阶正交矩阵$ Q \in \Theta $, $ {Q^{\text{T}}}AQ $不是正整数矩阵.

当$ n \ge 4 $时, 设

其中, $ {A_{11}} \in {{\bf{R}}^{s \times s}} $, $ {A_{22}} \in {{\bf{R}}^{t \times t}} $, $ {A_{33}} \in {{\bf{R}}^{2k \times 2k}} $均是对角线元素为1而其他元素为正整数的分块对称矩阵, $ {A_{12}} $, $ {A_{13}} $, $ {A_{23}} $均是分块正整数矩阵; $ {P_\theta } $和$ {H_\theta } $为形如引理3中的矩阵, $ s + t + 2k = n $, $ {\theta _j} \in {\bf{R}}{\text{ }}\left( {1 \le j \le k} \right) $为实数. 如此,

当$ s = n $ 或$ 1 \le s < n $、$ t = 0 $ 且所有的$ {\theta _j} = \pm 2l\pi \, ( 1 \le j \le k,{\text{ }}l = 0,1,2, \cdots ) $, 或$ s = t = 0 $且所有的 $ {\theta _j} = \pm 2l\pi $$ ( {1 \le j \le k,{\text{ }}l = 0,} {1,2, \cdots } ) $时, $ {P_\theta } = {I_n} \in \Omega $; 当$ t = n $, 或$ 1 \le t < n $, $ s = 0 $且所有的 $ {\theta _j} = \pm h\pi $ ($ 1 \le j \le k $, $ h $为奇数), 或$ t = s = 0 $且所有的$ {\theta _j} = \pm h\pi $($ 1 \le j \le k $, $ h $为奇数)时, $ {P_\theta } = - {I_n} \in \Phi $. 当$ s $, $ t $, $ k $ 和 $ {\theta _j} $$ ( {1 \le j \le k} ) $的取值不是前两种情况时, $ {P_\theta } \in \Theta $, $ P_\theta ^{\text{T}}A{P_\theta } $不是正整数矩阵. 当$ P \in \Theta $时, 由定义9和引理3可知, 对一切$ n \ge 4 $阶正交矩阵$ E \in \Phi $, $ Z \in {T} $且$ Z \ne E{P^{ - 1}} $, 则: 1) $ {Q_1} = ZP \in \Theta $, ${Q_2} = PZ \in \Theta$, $ {Q_3} = {Z^{\text{T}}}PZ \in \Theta $; 2) $ Q_1^{\text{T}}A{Q_1} $, $ Q_2^{\text{T}}A{Q_2} $, $ Q_3^{\text{T}}A{Q_3} $均不是正整数矩阵. 如此, 对一切$ n \ge 4 $阶正交矩阵$ Q \in \Theta $, $ {Q^{\text{T}}}AQ $不是正整数矩阵.

综合上述各种情况可得, 当$ n \ge 2 $时, $ \forall P \in \Theta $, $ {P^{\text{T}}}AP $不是正整数矩阵. □

此外, 不难证明, 当$ n \ge 2 $时, $ \forall Q \in \Phi $, $ {Q^{\text{T}}}AQ $是正整数矩阵.

引理 4^[15]. 设$ A,B \in {{\bf{R}}^{n \times n}} $为对称矩阵, 则$ \det \left( {\lambda {I_n} - A} \right) = \det \left( {\lambda {I_n} - B} \right) $的充要条件是存在正交矩阵$ P \in { T} $, 使得$ A = {P^{\text{T}}}BP = {P^{ - 1}}BP $.

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

定理 3. 设$ {G_{\text{1}}} = \left\langle {{V_{\text{1}}},{E_{\text{1}}}} \right\rangle $和$ {G_{\text{2}}} = \left\langle {{V_{\text{2}}},{E_{\text{2}}}} \right\rangle $是两个简单无向连通图, $ \left| {{V_1}} \right| = \left| {{V_2}} \right| = n \ge {\text{2}} $, $ {D_1} $与$ {D_2} $分别是$ {G_1} $和$ {G_2} $的距离矩阵, 则$ {G_1} \cong {G_2} $的充要条件是$ \det \left( {\lambda {I_n} - {D_1}} \right) $ $ = \det \left( {\lambda {I_n} - {D_2}} \right) $.

证明. 设$ \det \left( {\lambda {I_n} - {D_1}} \right) = \det \left( {\lambda {I_n} - {D_2}} \right) $. 因$ {D_1} $和$ {D_2} $均是实对称矩阵, 由引理4可知, 当$ \det ( \lambda {I_n} - {D_1}) = \det \left( {\lambda {I_n} - {D_2}} \right) $时, 存在$ n $阶正交矩阵$ P \in {T} $, 使得$ {D_1} = {P^{\text{T}}}{D_2}P $. 下面证明, $ \forall n \ge 2 $, $ P \in \Omega $(或$ P = - S $, $ S \in \Omega $). 假设存在一个$ P \in \Theta $, 使得$ {D_1} = {P^{\text{T}}}{D_2}P $, 则$ {I_n} + {D_1}\, =\, {P^{\text{T}}}P\; +\; {P^{\text{T}}}{D_2}P\, =\,{P^{\text{T}}}( {I_n} \;+ {D_2} )P $. 因$ {I_n} + {D_1} $和$ {I_n} + {D_2} $均是正整数矩阵, 故$ {P^{\text{T}}}\left( {{I_n} + {D_2}} \right)P $也是正整数矩阵, 这与定理2的结论矛盾. 如此, $ P \notin \Theta $. 因$ \Theta \cap \Phi = \emptyset $, $ \Theta \cup \Phi = {T} $, 故当$ P \in {T} $且$ P \notin \Theta $ 时, 必有$ P \in \Phi $. 换言之, $ \forall n \ge 2 $, 当$ {D_1} $和$ {D_2} $均是距离矩阵且$ \det \left( {\lambda {I_n} - {D_1}} \right) = \det ( \lambda {I_n} - {D_2}) $时, 一定存在$ P \in \Omega $(或$ P = - S $, $ S \in \Omega $), 使得$ {D_1} = {P^{\text{T}}}{D_2}P $. 由定理1可知, $ {G_1} \cong {G_2} $.

设$ {G_1} \cong {G_2} $. 由定理1可知, 存在$ n $阶置换矩阵$ P \in \Omega $, 使得$ {D_1} = {P^{\text{T}}}{D_2}P $. 如此, $ \det \left( {\lambda {I_n} - {D_1}} \right) = \det ( \lambda {I_n} - {D_2}) $. □

需要强调的是, 距离矩阵特征多项式和邻接矩阵特征多项式是两种完全不同的多项式; 邻接矩阵特征多项式相等并不总能确定两个简单无向连通图(特别是无向树)同构^{[4, 16]}. 设$ B \in {{\bf{R}}^{n \times n}} $是简单无向连通图的邻接矩阵, 因$ {I_n} + B $一般不是正整数矩阵(完全图除外, 完全图的邻接矩阵等于其距离矩阵), 故定理3的充分性证明方法不能用于邻接矩阵.

因求解距离矩阵$ D $^[13-14]和特征多项式$ \det ( \lambda {I_n} - D) $^[10-11]均有多项式时间算法, 故定理3的判定条件具有多项式时间复杂度.

因用数值方法求解特征多项式会产生计算误差^[10-11], 故当图的规模很大时, 这种计算误差可能会对定理3的判定结果产生影响. 因此, 寻找一种无误差判定条件无疑具有重要的应用价值.

推论 2. 设$ {G_{\text{1}}} = \left\langle {{V_{\text{1}}},{E_{\text{1}}}} \right\rangle $和$ {G_{\text{2}}} = \left\langle {{V_{\text{2}}},{E_{\text{2}}}} \right\rangle $是两个简单无向连通图, $ \left| {{V_1}} \right| = \left| {{V_2}} \right| = n \ge {\text{2}} $, $ {D_1} $与$ {D_2} $分别是$ {G_1} $和$ {G_2} $的距离矩阵; 若$ r\left( {{D_1}} \right) \ne r\left( {{D_2}} \right) $($ r\left( D \right) $表示$ D $的秩), 则$ {G_1} $和$ {G_2} $不同构.

证明. 因$ {D_1} $和$ {D_2} $均是实对称矩阵, 故$ {D_1} $和$ {D_2} $的特征值均是实数^{[15, 17]}. 设$ {D_1} $和$ {D_2} $的非零特征值个数分别是$ {r_1} $ 和 $ {r_2} $, $ {\lambda _i} $$ \left( {1 \le i \le {r_1}} \right) $ 和 $ {\mu _j} $$ \left( {1 \le j \le {r_2}} \right) $分别是$ {D_1} $和$ {D_2} $的非零特征值, 则存在$ n $阶正交矩阵$ {P_1},{P_2} \in { T} $, 使得

如此可得, $ r( {{D_1}} ) \;=\; r( {P_1^{ - 1}{D_1}{P_1}} ) \;=\; {r_1} $, $r( {{D_2}} ) \;= $ $ r ( {P_2^{ - 1}{D_2}{P_2}} ) = {r_2}$. 当$ r( {{D_1}} ) \ne r( {{D_2}} ) $时, $ {D_1} $和$ {D_2} $的非零特征值个数不相等, $ \det ( {\lambda {I_n} - {D_1}} ) \ne \det ( \lambda {I_n} - {D_2} ) $. 由定理3可知, $ {G_1} $和$ {G_2} $不同构. □

定义 10. 设$ G = \left\langle {V,E} \right\rangle $是简单无向连通图, $ \left| V \right| = n \ge 2 $, $ D\left( {{d_{ij}}} \right) \;\in \;{{\bf{R}}^{n \times n}} $是 $ G $ 的距离矩阵, $ d\left( G \right) = \max \left\{ {{d_{ij}}} \right\} $是$ G $的直径, $ {m_s} $是$ {d_{ij}} = s $$( 1 \le s \le d\left( G \right), {\text{ }}1 \le i,j \le n )$ 的元素总数; 称 ${d_s}\left( D \right) = [ {{m_1}}\;\;{{m_2}}\;\; \cdots \;\;{{m_{d\left( G \right)}}} ]$是$ G $的距离谱向量, 简称$ G $的距离谱.

由定义7和定义10可知: $ {m_s} $均是正整数, $\sum\nolimits_{i,j}^n {{d_{ij}} = \sum\nolimits_{s = 1}^{d\left( G \right)} {{m_s}s} }$, $\sum\nolimits_{i,j}^n {d_{ij}^2 = \sum\nolimits_{s = 1}^{d\left( G \right)} {{m_s}{s^2}} }$.

推论 3. 设$ {G_{\text{1}}} = \left\langle {{V_{\text{1}}},{E_{\text{1}}}} \right\rangle $和$ {G_{\text{2}}} = \left\langle {{V_{\text{2}}},{E_{\text{2}}}} \right\rangle $是两个简单无向连通图, $ \left| {{V_1}} \right| = \left| {{V_2}} \right| = n \ge {\text{2}} $, $ {D_1} $与$ {D_2} $分别是$ {G_1} $和$ {G_2} $的距离矩阵; 若$ {d_s}\left( {{D_1}} \right) \ne {d_s}\left( {{D_2}} \right) $, 则$ {G_1} $和$ {G_2} $不同构.

证明. 设$ {d_s}( {{D_1}} ) \ne {d_s}( {{D_2}} ) $时, $ {G_1} \cong {G_2}. $ 由定理1可知, 当$ {G_1} \cong {G_2} $时, 存在$ Q \in \Omega $, 使得$ {D_1} = {Q^{\text{T}}}\times {D_2}Q $. 因同构变换不改变图的距离谱, 故 $ {d_s}\left( {{D_1}} \right) \;= {d_s}( {{Q^{\text{T}}}{D_2}Q} ) = {d_s}( {{D_2}} ) $, 即$ {d_s}( {{D_1}} ) = {d_s}( {{D_2}} ) $, 与推论3的条件矛盾, $ {G_1} \cong {G_2} $的假设不成立. 换言之, 当$ {d_s}( {{D_1}} ) \ne {d_s}( {{D_2}} ) $时, $ {G_1} $和$ {G_2} $不同构. □

由推论1 ~ 3可知, $ {d_o}\left( {{D_1}} \right) = {d_o}\left( {{D_2}} \right) $, $ r\left( {{D_1}} \right) = r\left( {{D_2}} \right) $, $ {d_s}\left( {{D_1}} \right) = {d_s}\left( {{D_2}} \right) $均是两个简单无向连通图同构的必要条件.

定义 11^[17]. 设$ A \in {{\bf{R}}^{n \times n}} $$ \left( {n \ge 2} \right) $, 若存在$ n $阶置换矩阵$ P \in \Omega $, 使得

其中, $ {A_{11}} $是$ k \times k $$ \left( {1 \le k \le n - 1} \right) $阶子矩阵, $ {A_{22}} $是$ \left( {n - k} \right) \times \left( {n - k} \right) $阶子矩阵, 则称$ A $是可约矩阵; 否则, 称$ A $是不可约矩阵.

由定义7和定义11可知, 简单无向连通图的距离矩阵$ D $是非负不可约矩阵.

定义 12^[17]. 设$ A \in {{\bf{R}}^{n \times n}} $是非负不可约矩阵且有$ k $个模等于$ \rho \left( A \right) $的特征值: 若$ k = 1 $, 则称$ A $是素矩阵; 若$ k\; \gt \;1 $, 则称$ A $是指数为$ k $的循环矩阵.

引理 5^[17]. 设$ A \in {{\bf{R}}^{n \times n}} $是非负不可约矩阵, 则$ A $为素矩阵的充要条件是存在某正整数 $ m $, 使得$ {A^m}\; \gt \;0 $($ {A^m} $的所有元素大于零).

容易证明, 当$ n \ge 3 $时, 一切距离矩阵$ D $均是素矩阵($ {D^2} > 0 $).

引理 6^[17]. 设$ A \in {{\bf{R}}^{n \times n}} $是素矩阵, $ {\lambda _1},{\lambda _2}, \cdots , {\lambda _n} $是$ A $的特征值, 则谱半径$ \rho \left( A \right) > 0 $是$ A $的单特征值, 且对一切 $ \left| {{\lambda _i}} \right| \ne \rho \left( A \right) $, 均有 $ \left| {{\lambda _i}} \right| \lt \;\rho \left( A \right). $

引理 7^[17]. 设$ A\left( {{a_{ij}}} \right) \in {{\bf{R}}^{n \times n}} $为正规矩阵$ ( {A^{\text{T}}}A = A{A^{\text{T}}} ) $, $ {\lambda _1},{\lambda _2}, \cdots ,{\lambda _n} $是$ A $的特征值, 则$\sum\nolimits_{i,j}^n {a_{ij}^2} = \sum\nolimits_{i = 1}^n {\lambda _i^2}$.

设$ r\left( D \right) = k $, $ {\Delta _k} = {\Delta _{r\left( D \right)}} $表示$ D $的所有$ k $阶主子式的和. 使用符号$ {\Delta _k} $并依据引理5 ~ 7, 可以得到简单无向连通图的另一个同构判定条件.

定理 4. 设$ {G_{\text{1}}} = \left\langle {{V_{\text{1}}},{E_{\text{1}}}} \right\rangle $ 和 $ {G_{\text{2}}} = \left\langle {{V_{\text{2}}},{E_{\text{2}}}} \right\rangle $是两个简单无向连通图, $ \left| {{V_1}} \right| = \left| {{V_2}} \right| = n \ge 2 $, $ {D_1} $与$ {D_2} $分别是$ {G_1} $和$ {G_2} $的距离矩阵, 则$ {G_1} \cong {G_2} $的充要条件是$ {d_s}\left( {{D_1}} \right) = {d_s}\left( {{D_2}} \right) $, $ r\left( {{D_1}} \right) = r\left( {{D_2}} \right) $且$ {\Delta _{r\left( {{D_1}} \right)}} = {\Delta _{r\left( {{D_2}} \right)}} $.

证明. 当$ n = 2 $时, 定理4的结论显然成立. 设$ {D_1} = D\left( {{a_{ij}}} \right) $, $ {D_2} = D\left( {{b_{ij}}} \right) $, 下面证明$ n \ge 3 $时, 定理4的结论也成立.

设$ {d_s}( {{D_1}} ) = {d_s}( {{D_2}} ) $, $ r( {{D_1}} ) = r( {{D_2}} ) $ 且 $ {\Delta _{r( {{D_1}} )}} = {\Delta _{r( {{D_2}} )}}. $ 当$ {d_s}( {{D_1}} ) = {d_s}( {{D_2}} ) $ 时, 由定义10可得, $ d( {{G_1}} ) = d( {{G_2}} ) $, $ \sum\nolimits_{s = 1}^{d( {{G_1}} )} {{m_s}{s^2}} = \sum\nolimits_{i,j}^n {a_{ij}^2} $, $\sum\nolimits_{s = 1}^{d( {{G_2}} )} {{m_s}{s^2}} = \sum\nolimits_{i,j}^n {b_{ij}^2}$, $ \sum\nolimits_{i,j}^n {a_{ij}^2} = \sum\nolimits_{i,j}^n {b_{ij}^2}.$ 因$ {D_1} $和$ {D_2} $均是对称矩阵和素矩阵, 故当$ r( {{D_1}} ) = r( {{D_2}} ) = m $且$ {\Delta _{r( {{D_1}} )}} = {\Delta _{r( {{D_2}} )}} = \Delta $时, 可设$ {D_1} $的非零特征值和特征多项式分别为

$ {D_2} $的非零特征值和特征多项式分别为

由$ \sum\nolimits_{i,j}^n {a_{ij}^2} \;=\; \sum\nolimits_{i,j}^n {b_{ij}^2} $和引理7可得, $ \sum\nolimits_{i = 1}^m {\lambda _i^2} \;= \sum\nolimits_{i = 1}^m {\mu _i^2} $. 因$ {D_1} $和$ {D_2} $ 的对角线元素全为零, 故由特征值和特征多项式系数之间的关系可得, $ \sum\nolimits_{i = 1}^m {{\lambda _i}} = \sum\nolimits_{i = 1}^m {{\mu _i}} = 0 $, $\prod\nolimits_{i = 1}^m {{\lambda _i} = \prod\nolimits_{i = 1}^m {{\mu _i} = \Delta } }$. 如此,

不难发现, $ {\lambda _i} = {\mu _i} $$ \left( {1 \le i \le m} \right) $是上述3个方程的一组公共解. 下面分4步证明该组解是唯一解.

1) $ \forall n \ge 3 $ 和 $ 1 \le i \le m $, 设$ {\bar \lambda _i} = - {\mu _i} .$ 因已假设$ {\mu _1} \le \cdots \le {\mu _{m - 1}} < {\mu _m}( {{\mu _1} < 0} ) $, 且$ \forall i \ne m $, $| {{\mu _i}} | < {\mu _m}= \rho ( {{D_2}} ) > 0$; 故$ {\bar \lambda _1} \ge \cdots \ge {\bar \lambda _{m - 1}} > {\bar \lambda _m} $, $ {\bar \lambda _1} > 0 $且$ {\bar \lambda _m} < 0 $. 因$ {\bar \lambda _1} = | {{\mu _1}} | < {\mu _m} = | {{{\bar \lambda }_m}} | $, 即$ {\bar \lambda _1} < | {{{\bar \lambda }_m}} | $, 由引理6可知, $ {\bar \lambda _i}{\text{ }}( 1 \le i \le m ) $不是或不全是对称素矩阵$ {D_1} $的特征值. 如此, $ {\bar \lambda _i} = - {\mu _i} $ $ ( {1 \le i \le m} ) $不可能是式$ ( 1 ) $, $ ( 2 ) $, $ ( 3 ) $的公共解.

2) $ \forall n \ge 3 $和$ \forall l \in \{ 1, \cdots , m - 1\} $, 若设$ {\bar \lambda _i} = - {\mu _i} $ $ ( {1 \le i \le l} ) $, $ {\bar \lambda _j} = {\mu _j} $$ ( l + 1 \le j \le m ) ,$ 则$ {\bar \lambda _i} $和$ {\mu _i} $ 是式(1)的解, $ \sum\nolimits_{i = 1}^m {{{\bar \lambda }_i}} = \sum\nolimits_{i = 1}^m {{\mu _i}} - 2\sum\nolimits_{i = 1}^l {{\mu _i}} .$ 因 $ \sum\nolimits_{i = 1}^m {{\mu _i}} = 0 $ 且 $ l\; <\; m $, 故 $ \sum\nolimits_{i = 1}^l {{\mu _i}} \;\ne \; \sum\nolimits_{i = 1}^m {{\mu _i}}, $ $ \sum\nolimits_{i = 1}^m {{{\bar \lambda }_i}}\; = - 2\sum\nolimits_{i = 1}^l {{\mu _i}} \ne 0 $. 如此, $ {\bar \lambda _i} $$ ( 1 \le i \le m ) $不是或不全是$ {D_1} $的特征值, 式$ ( 2 ) $和式$ ( 3 ) $均不成立.

3) $ \forall \varepsilon \in {\bf{R}} $且$ \varepsilon \ne 0 $; $ \forall i \ne j $, $ t \ne i $且$ t \ne j $; 设$ {\bar \lambda _t} = {\lambda _t} $, $ {\bar \lambda _i} = {\lambda _i} - \varepsilon $, $ {\bar \lambda _j} = {\lambda _j} + \varepsilon $, $ {\bar \mu _t} = {\mu _t} $, $ {\bar \mu _i} = {\mu _i} - \varepsilon $, $ {\bar \mu _j} = {\mu _j} + \varepsilon $, 则$ {\bar \lambda _t} $和$ {\bar \mu _t} $ $ ( {1 \le t \le m} ) $满足式$ ( 2 ) $, 但不能同时满足式$ ( 1 ) $和式$ ( 3 ) $.

4) 若有奇数个$ | {{\lambda _i}} | \ne | {{\mu _i}} | $ $ ( {1 \le i \le m} ) $, 则式(1) ~ (3)均不成立; 若有偶数个$ | {{\lambda _i}} | \ne | {{\mu _i}} | $(如$ {\lambda _i} = \alpha {\mu _i} $, $ {\lambda _j} = {\alpha ^{ - 1}}{\mu _j} $, $ \alpha \ne 1 $)使得式$ ( 3 ) $成立, 则式$ ( 1 ) $和式$ ( 2 ) $均不成立.

综合上述4种情况可知, $ {\lambda _i} = {\mu _i} $$ ( {1 \le i \le m} ) $是同时满足式(1) ~ (3)的一组唯一解. 如此, $ \forall n \ge 3 $, $ \det ( \lambda {I_n} - {D_1} ) = \det ( {\lambda {I_n} - {D_2}} ) $.

总之, $ \forall n \ge 2 $, 当 $ {d_s}( {{D_1}} ) = {d_s}( {{D_2}} ) $, $ r( {{D_1}} ) = r( {{D_2}} ) $ 并且 $ {\Delta _{r( {{D_1}} )}}\; = \;{\Delta _{r( {{D_2}} )}} $ 时, $\det ( {\lambda {I_n} - {D_1}} ) \;= \det ( \lambda {I_n} - {D_2} )$. 由定理3可知, $ {G_1} \cong {G_2}. $

设$ {G_1} \cong {G_2} .$ 由定理1可知, 当$ {G_1} \cong {G_2} $ 时, 存在$ n $阶置换矩阵$ P \in \Omega $, 使得$ {D_1} = {P^{\text{T}}}{D_2}P $. 因$ {d_s}( D ) $, $ r( D ) $和$ {\Delta _{r( D )}} $均在矩阵同构变换下保持不变, 故当$ {D_1} = {P^{\text{T}}}{D_2}P $时, $ {d_s}( {{D_1}} ) = {d_s}( {{D_2}} ) $, $ r( {{D_1}} ) = r( {{D_2}} ) $且$ {\Delta _{r( {{D_1}} )}} = {\Delta _{r( {{D_2}} )}} $. □

当图的顶点数$ n $很大且$ r\left( D \right) $接近 $ 0.5n $时, 求解$ {\Delta _{r\left( D \right)}} $的计算量将异常大. 因此, 还需寻找更易计算的同构判定条件.

定理 5. 设$ {G_{\text{1}}} = \left\langle {{V_{\text{1}}},{E_{\text{1}}}} \right\rangle $和$ {G_{\text{2}}} = \left\langle {{V_{\text{2}}},{E_{\text{2}}}} \right\rangle $是两个简单无向连通图, $ \left| {{V_1}} \right| = \left| {{V_2}} \right| = n \ge 2 $, $ {D_1} $与$ {D_2} $分别是$ {G_1} $和$ {G_2} $的距离矩阵, 则$ {G_1} \cong {G_2} $的充要条件是$ r\left( {{D_1}} \right) = r\left( {{D_2}} \right) $且$ {d_o}\left( {{D_1}} \right) = {d_o}\left( {{D_2}} \right) $.

证明. 当$ n = 2 $时, 定理5的结论显然成立. 下面证明$ n \ge 3 $时, 定理5的结论也成立. 为方便起见, 下面仍使用证明定理4时所用的符号和术语.

设$ r( {{D_1}} ) = r( {{D_2}} ) $且$ {d_o}( {{D_1}} ) = {d_o}( {{D_2}} ) $, 但$ {G_1} $和$ {G_2} $不同构. 由定理4的证明可知, 若$ r( {{D_1}} ) = r( {{D_2}} ) = m $ 且 $ {d_o}( {{D_1}} ) = {d_o}( {{D_2}} ) $时, $ {G_1} $ 和 $ {G_2} $不同构, 则对称素矩阵$ {D_1} $与$ {D_2} $的非零特征值的绝对值 $ | {{\lambda _i}} | $ 和 $ | {{\mu _i}} | $$ ( {1 \le i \le m} ) $不全部相等, $ \sum\nolimits_{i = 1}^m {\lambda _i^2} \ne \sum\nolimits_{i = 1}^m {\mu _i^2} $. 由引理7可知, 当$ \sum\nolimits_{i = 1}^m {\lambda _i^2} \ne \sum\nolimits_{i = 1}^m {\mu _i^2} $时, $ \sum\nolimits_{i,j}^n {a_{ij}^2} \ne \sum\nolimits_{i,j}^n {b_{ij}^2} $. 由定义7和定义10可知, 当$ \sum\nolimits_{i,j}^n {a_{ij}^2} \ne \sum\nolimits_{i,j}^n {b_{ij}^2} $时, $ \sum\nolimits_{s = 1}^{d( {{G_1}} )} {{m_s}{s^2}} \ne \sum\nolimits_{t = 1}^{d( {{G_2}} )} {{m_t}{t^2}} $, ${d_s}( {{D_1}} ) \ne {d_s}( {{D_2}} )$, $ \sum\nolimits_{i,j}^n {{a_{ij}}} \ne \sum\nolimits_{i,j}^n {{b_{ij}}} $. 如此, $ {d_o}( {{D_1}} ) \ne {d_o}( {{D_2}} ) $, 与假设矛盾, $ {G_1} $和$ {G_2} $不同构的假设不成立. 换言之, 若$ r( {{D_1}} ) = r( {{D_2}} ) $且$ {d_o}( {{D_1}} ) = {d_o}( {{D_2}} ) $, 则 $ {G_1} \cong {G_2} $.

设$ {G_1} \cong {G_2}. $ 由定理1可知, 当$ {G_1} \cong {G_2} $时, 存在$ n $阶置换矩阵$ P \in \Omega $, 使得$ {D_1} = {P^{\text{T}}}{D_2}P $. 因$ r\left( D \right) $和$ {d_o}\left( D \right) $均是矩阵同构变换下的不变量, 故当$ {D_1} = {P^{\text{T}}}{D_2}P $时, $ r\left( {{D_1}} \right) = r\left( {{D_2}} \right) $且$ {d_o}( {{D_1}} ) = d_o( {{D_2}} ). $ □

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

定理5主要涉及3种运算, 求解距离矩阵$ D \in {{\bf{R}}^{n \times n}} $, $ r( D ) $以及$ {d_o}( D ) .$ 现对定理5的算法复杂度做一些简要说明: 1) 用Floyd算法^[14]求解$ D $的算法复杂度是 $ {\text{O}}( {{n^4}} ) $, 用Warshall算法^[14]求解$ D $的算法复杂度是$ {\text{O}}( {{n^3}} ) $; 2) 求解$ r( D ) $的算法复杂度是$ {\text{O}}( {{n^3}} ) $^[11]; 3) 由定义8和排序算法可知, 求解$ {d_o}( D ) $的算法复杂度是$ {\text{O}}( {1.5{n^2}} ) $; 4) 比较$ {d_o}( {{D_1}} ) $和$ {d_o}( {{D_2}} ) $是否相等的算法复杂度是$ {\text{O}}( n ) $. 总之, 使用定理5判定两个简单无向连通图是否同构的算法复杂度不会超过$ {\text{O}}( {2{n^4}} ) $.

引理 8^[18]. 设$ A \in {{\bf{R}}^{n \times n}}\; ( {n \ge 2} ) $具有如下分块形式:

其中, $ {A_{11}} $是$ k \times k $$ \left( {1 \le k \le n - 1} \right) $ 阶子矩阵, $ {A_{22}} $ 是$ \left( {n - k} \right) \times \left( {n - k} \right) $ 阶子矩阵. 若$ {A_{11}} $可逆, 则$ \det \left( A \right) = \det \left( {{A_{11}}} \right)\det \left( {{A_{22}} - {A_{21}}A_{11}^{ - 1}{A_{12}}} \right) .$

定理 6. 设$ G = \langle {V, E} \rangle $是无向树, $ | V | = n \ge 2, $ $ D $是$ G $的距离矩阵, 则$\det ( D ) = {( { - 1} )^{n - 1}} ( n - 1){2^{n - 2}}$.

证明. 1) 设$ {D_k} \in {{\bf{R}}^{k \times k}} $$ \left( {k \ge 2} \right) $为无向树的距离矩阵. 经直接验证可得^[16]: $ n = 2 $时, $ r\left( {{D_2}} \right) = 2 $, $ \det \left( {{D_2}} \right) = - 1 $; $ n = 3 $时, $ r\left( {{D_3}} \right) = 3 $, $ \det \left( {{D_3}} \right) = 4 $(2顶点和3顶点无向树只有1个自同构类); $ n = 4 $时, $ r\left( {{D_4}} \right) = 4 $, $ \det \left( {{D_4}} \right) = - 12 $(4顶点无向树有2个自同构类). 上述结果表明, $ 2 \le n \le 4 $时, $ \det \left( D \right) = {\left( { - 1} \right)^{n - 1}}\left( {n - 1} \right){2^{n - 2}} $, $ r\left( D \right) = n $且与树的拓扑结构无关.

2) 设$ n = k $$ \left( {k \ge 5} \right) $时, $ r\left( {{D_k}} \right) = k $, $\det \left( {{D_k}} \right) = $ $ {\left( { - 1} \right)^{k - 1}}\left( {k - 1} \right){2^{k - 2}}$且与树的拓扑结构无关; 下面证明, $ n = k + 1 $时, $ r\left( {{D_{k + 1}}} \right) = k + 1 $, $ \det \left( {{D_{k + 1}}} \right) = {\left( { - 1} \right)^k}k\times{2^{k - 1}} $且与树的拓扑结构无关. 设$ n = k + 1 $时, $ G $的距离矩阵为

其中, ${\varsigma ^{\text{T}}} = [ {{\varsigma _1}}\;\;{{\varsigma _2}}\;\; \cdots \;\;{{\varsigma _k}} ]$, $ {\varsigma _i} $$ \left( {1 \le i \le k} \right) $为正整数. 因已假设$ r\left( {{D_k}} \right) = k $, 故$ \det \left( {{D_k}} \right) \ne 0 $, $ {D_k} $可逆. 由引理8可得, $ \det \left( {{D_{k + 1}}} \right) = - \det \left( {{D_k}} \right)\det \left( {{\varsigma ^{\text{T}}}D_k^{ - 1}\varsigma } \right) $. 因$ \varsigma $为正整数向量并且$ D_k^{ - 1} \ne 0 $, 故$ \det \left( {{\varsigma ^{\text{T}}}D_k^{ - 1}\varsigma } \right) \ne 0 $, $ \det \left( {{D_{k + 1}}} \right) = {\left( { - 1} \right)^k}k\times{2^{k - 1}} $, $ r\left( {{D_{k + 1}}} \right) = k + 1 $, 且与树的拓扑结构无关.

由归纳步骤1)和步骤2)可得, 对一切无向树的距离矩阵$ D \in {{\bf{R}}^{n \times n}} $$ \left( {n \ge 2} \right) $, $\det \left( D \right) = {\left( { - 1} \right)^{n - 1}}( n\; - 1){2^{n - 2}}$. □

推论 4. 设$ {G_{\text{1}}} = \left\langle {{V_{\text{1}}},{E_{\text{1}}}} \right\rangle $和 $ {G_{\text{2}}} = \left\langle {{V_{\text{2}}},{E_{\text{2}}}} \right\rangle $是两个无向树, $ \left| {{V_1}} \right| = \left| {{V_2}} \right| = n \ge 2 $, $ {D_1} $与$ {D_2} $ 分别是$ {G_1} $和$ {G_2} $的距离矩阵, 则$ {G_1} \cong {G_2} $的充要条件是$ {d_s}\left( {{D_1}} \right) = {d_s}\left( {{D_2}} \right) $.

证明. 因$ {G_1} $和$ {G_2} $均是无向树且 $\left| {{V_1}} \right| = \left| {{V_2}} \right| = n \ge 2$, 故由定理6可知, $ r\left( {{D_1}} \right) = r\left( {{D_2}} \right) = n $, 且

恒成立, 即$ r( {{D_1}} ) = r( {{D_2}} ) $ 且$ {\Delta _{r( {{D_1}} )}} = {\Delta _{r( {{D_2}} )}} $ 恒成立. 如此, “$ {d_s}( {{D_1}} ) = {d_s}( {{D_2}} ) $、$ r( {{D_1}} ) = r( {{D_2}} ) $ 且$ {\Delta _{r( {{D_1}} )}} = {\Delta _{r( {{D_2}} )}} $”与“$ {d_s}( {{D_1}} ) = {d_s}( {{D_2}} ) $”等价. 因无向树是简单无向连通图, 由定理4立即可得, 无向树$ {G_1} \cong {G_2} $的充要条件是$ {d_s}( {{D_1}} ) = {d_s}( {{D_2}} ) $. □

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

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

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

图 1  例1各对应图

Fig. 1  Corresponding figures of Example 1

下载: 全尺寸图片 幻灯片

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

由$ {D_1} $和$ {D_2} $可得,

因$ {d_s}\left( {{D_1}} \right) \ne {d_s}\left( {{D_2}} \right) $, 由推论3或推论4均可判定$ {G_1} $和$ {G_2} $不同构.

此外, $ {G_1} $和$ {G_2} $ 的邻接矩阵同谱, 即 $ \phi \left( {{G_1},\lambda } \right) = \phi \left( {{G_2},\lambda } \right) = {\lambda ^{10}} - 9{\lambda ^8} + 26{\lambda ^6} - $$ 27{\lambda ^4} \;+ \;8{\lambda ^2} $. 若将邻接矩阵特征多项式相等作为判据来判定$ {G_1} $和$ {G_2} $是否同构^{[16, 19]}, 就会得出错误的结果.

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

因为$ \det \left( {\lambda {I_8} - {D_3}} \right) \;=\; \det \left( {\lambda {I_8} - {D_4}} \right) \;= ( \lambda \;- 11) ( \lambda + 1){\left( {\lambda + 3} \right)^2}{\left( {{\lambda ^2} + 2\lambda - 1} \right)^2} $, 故由定理3可以判定$ {G_3} \cong {G_4} $.

另一方面, 因$ r\left( {{D_3}} \right) = r\left( {{D_4}} \right) = 8 $; ${d_o}\left( {{D_3}} \right) = [ {11} \;\;{11} \;\;{11}\;\;{11}\;\;{11}\;\;{11}\;\;{11}\;\;{11} ]$, ${d_o}\left( {{D_4}} \right) = [ {11}\;\;{11}\;\;{11}\;\;{11}\;\;{11} \;\;{11}\;\;{11}\;\;{11} ]$, $ {d_o}\left( {{D_3}} \right) = {d_o}\left( {{D_4}} \right) $; 由定理5可轻松判定$ {G_3} \cong {G_4} $.

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

经计算可得, $ \det \left( {{D_5}} \right) = 0 $, $ \det \left( {{D_6}} \right) = - 4\;352 $. 因$ \det \left( {{D_5}} \right) \ne \det \left( {{D_6}} \right) $, 由定理3可以判定$ {G_5} $和$ {G_6} $不同构.

因${d_s}\left( {{D_5}} \right) = {d_s}\left( {{D_6}} \right) = [ {30}\;\;{40}\;\;{20} ]$, 但$ r\left( {{D_5}} \right) \ne r\left( {{D_6}} \right) $, 故由推论2或定理5亦可判定$ {G_5} $和$ {G_6} $不同构.

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

因$ {D_7} = {D_8} $, 由定理1、定理3或定理5均可判定 $ {G_7} \cong {G_8} $.

此外, 因图的距离谱不同, 故由定理5可轻松判定$ {G_7} $和$ {G_8} $与$ {G_5} $或$ {G_6} $不同构.

5) $ {G_9} $和$ {G_{10}} $均是简单无向连通图, 按图中标号可得$ {G_9} $和$ {G_{10}} $的距离矩阵分别为

经计算可得, $ \det ( {{D_9}} ) = 37 $, $ \det ( {{D_{10}}} ) = - 7 $. 因$ \det ( {{D_9}} )\, \ne \,\det ( {{D_{10}}} ) $, 故 $ \det ( {\lambda {I_8}\, -\, {D_9}} ) \,\ne \,\det ( \lambda {I_8} \;- $ ${D_{10}} ). $ 由定理3可以判定$ {G_9} $和$ {G_{10}} $不同构.

此外, 经计算还可得, ${d_o}\left( {{D_9}} \right) = [ {10}\;\;{10}\;\;{10}\;\;{10} \;\;{11}\;\;{11}\;\;{11}\;\;{11} ],$ ${d_o}\left( {{D_{10}}} \right) = [7 \;\,{11}\;\,{11}\,\;{11}\,\;{11}\,\;{11} \;\,{11} \,\;{11} ],$ $ {d_o}\left( {{D_9}} \right) \ne {d_o}\left( {{D_{10}}} \right) $. 由推论1或定理5亦可判定$ {G_9} $和$ {G_{10}} $不同构.

3.   结束语

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

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

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

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