1. 引言
图的谱包含了关于给定图的大量组合信息,可用于描述和分析各种复杂系统和结构,如网络、物理、生物等,因此长期以来一直是图谱理论中的一个有用工具。图谱领域中一个长期未解决的基本问题是:“哪些图是由它们的谱确定的?”事实表明,证明图是谱确定的比构造同谱图更具有挑战性。迄今为止,谱确定的许多证明都依赖于这些图的谱的一些特殊性质,因此不能推广到一般图上。关于这个问题的背景和一些已知的结果,可以参考文献 [1] [2] 。
当两个图同谱且补图也同谱时,则称它们为广义同谱图。当任何与G广义同谱的图都与G同构,则称图G是广义谱确定的。通过引入道矩阵(walk-matrix)这一重要工具,并研究其Smith标准型特征给出了判定一大类图广义谱确定的条件。其中图G的道矩阵定义为:
,
其中e为n维全一列向量,A为图G对应的邻接矩阵 [2] 。
Smith标准型是整系数矩阵的一种对角化形式(具体详细求解可见文献 [3] ),根据文献 [4] ,它具有存在性和唯一性,且有如下定理。
定理1 [4] 设R为具有同一性的交换环,Smith标准型将有如下性质:
(1) 如果R上所有矩阵都有Smith标准型,那它则是Bézout环。
(2) 当且仅当R是Bézout环,R上所有对角矩阵都有Smith标准型。
定理2 [4] 令R为唯一因式分解域,其中任意两个元素都有最大公因数。假设A是R上的m × n矩阵M是的Smith标准型,其中A为主对角线为
,其余地方为0的矩阵。则当
时,
等于所有A的k × k子式的最大公因数。其中如果所有k × k子式都为0,则最大公因数亦为0。
由此可见Smith标准型在代数与图论中有重要意义与应用。
1736年欧拉解决了著名的哥尼斯堡七桥问题,并将其一般化,证明了如下定理:一个非空连通图当且仅当它的每个顶点的度数都是偶数时是欧拉图(Euler Graph) [5] 。
关于道矩阵的Smith标准型,由于欧拉图的特殊性质,文献 [6] 给出了欧拉图中道矩阵的Smith标准型在某些条件下与图的道矩阵的某些参数之间的关系,即定理3。
定理3 [6] 设图G为n阶欧拉图,W为图G对应的道矩阵,若
,b为奇数且无平方因子,则W的Smith标准型为:
.
类似的,本文考虑图G对应的无符号拉普拉斯矩阵Q的Q-道矩阵,其定义如下:
.
本文给出在某些条件下欧拉图的Q-道矩阵的Smith标准型与图的Q-道矩阵的某些参数之间存在关联,并给出如下定理。
定理4 设G为n阶欧拉图,
为图G对应的Q-道矩阵,若
,b为奇数且无平方因子,则
的Smith标准型为:
.
结合文献 [7] ,本结论可简化对Smith标准型的Dynkin拓展矩阵
求解。还可结合文献 [8] ,让多维系统的缩减和多元多项式的约简的步骤更为简洁。
以下本文将主要围绕此定理进行证明。
2. 定义引入
为了叙述方便,给出如下定义:
.
其中n阶欧拉图是指n个顶点且具有欧拉回路的图,若为无向图,则各个顶点的度数皆为偶数;若为有向图,则各个顶点出度与入度相等。
设图G的度序列为d,令
。由在欧拉图中所有顶点的度都为偶数,易得
为整数列向量。因此引入矩阵:
.
由
可知
为整数矩阵。
定义5 [2] 对素数p,矩阵M在域Fp上的秩记为
。
引理6 [2] 设M为对称阵,u为任意向量。则:
(1)
(2)
。
其中
为矩阵M的主对角元构成的列向量。
引理7 对任意的整数矩阵M,存在幺模矩阵U、V,使得
,其中
。其中
称为矩阵M的不变因子,
称为矩阵M的Smith标准型。
3. 问题解决
为证明定理4,首先提出以下引理并对其证明。
引理8 设图G为欧拉图,其对应的无符号拉普拉斯矩阵为Q,则
,且对任意的整数
,有
。
证明:首先论证
成立。由
可知
。
其次,证明对任意的整数
,有
。
其中
,令
,则
,只需论证对任意的整数
有
,则引理得证。
再者,基于n的奇偶性进行分类讨论。
当n为偶数,则
;
当n为奇数,则
,
综上所述,
,引理得证。
引理9 设G为欧拉图,其对应的无符号拉普拉斯矩阵为Q,则
。且当
时,
;当
时,
。
证明:基于
对8的余数进行分类讨论。
当
,则
。
又由
可得当
时,有
。
同理,当
,则
。
再由
可得
。综上,引理得证。
引理10 设图G为n阶欧拉图,则
。
证明:本定理基于n的奇偶性进行分类讨论。
当n为偶数,令
,由引理8可得:
由定义
是由
的前两列乘2得到的矩阵,因此
,再由
及
可得
.
当n为奇数,基于
对8的余数再度进行分类讨论:
若
,由引理9可知
。再由引理8可得:
再由秩不等式可得
,即
。
若
,由引理9可知
。再由引理8可得:
同理,由秩不等式可得
,即
。综上所述,命题得证。
引理11 设图G为n阶欧拉图,则
。
证明:因为
,所以
对角线上的偶元素至少为
个,由此可得
。再由
的定义可知
。
定理12 设图
,则
,且
的Smith标准型为:
.
证明:因
,所以
为奇数且无平方因子。设
,其中
为互不相同的奇素数。
假设
的Smith标准型为
,其中
,
为奇数且无平方因子。
由引理10可知
,即
。
因此有
。
此外,由于
且
,可得
及
。
命题得证。
以下将对定理4进行证明:
证明:由定义
,
,
,
,可得不失一般性设
的Smith标准型为
,其中b为奇数且无平方因子。
因此存在幺模矩阵U、V,使得
,其中
。即:
其中,
,
,且a为一个整数,
和
为
维列向量,
为
阶方阵。
由
可得:
,
即:
(1)
其中
为整数矩阵。
注意
,此外有
。
对(1)两边同时取行列式可得
。由上式可知
为奇数,因此等式成立当且仅当
且
,即
为幺模矩阵。
由引理7可知
为
的Smith标准型。再由引理12可知:
.
由上述等式及
的定义可知
的Smith标准型为
,定理4得证。
4. 结论
本文对极端条件下n阶欧拉图的无符号拉普拉斯矩阵的道矩阵
的Smith标准型进行刻画,并给出如下结论:
当
的行列式满足
,其中b为奇数且无平方因子时,
的Smith标准型为
。
又因Smith标准型是图论中一个极为常用的工具,本结论可在相关领域中简化研究过程。例如,结合文献 [9] ,可更为快速计算非奇异整数矩阵的Smith标准型的乘子。