1. 引言
图论起源于18世纪哥尼斯堡七桥问题,瑞士数学家Leonhard Euler在1736年发表了一篇解决七桥问题的论文,该论文被认为是图论的第一篇论文,Euler因此也被誉为图论之父。1936年匈牙利数学家König出版了第一本图论专著《Theory of Directed and Undirected Graphs》,标志着图论正式成为一门独立的学科。作为离散数学重要的分支之一,图论已发展成一门独立的学科,它主要研究某一集合元素间可用拓扑图形表示的二元关系。根据研究方法和内容的不同,图论已衍生出许多分支,如拓扑图论、代数图论、随机图论、结构图论、模糊图论、极值图论、超图论等。图谱理论作为代数图论中的一个重要分支,与群论、矩阵论、组合数学、多项式理论、线性代数等学科都有着密切的联系,它主要研究图的组合性质和图相关矩阵(如邻接矩阵,拉普拉斯矩阵,无符号拉普拉斯矩阵,距离矩阵)的代数性质之间的关系。
一个图的邻接矩阵的特征值称为图的特征值,图的所有特征值的多重集称为图的谱。1978年Cvetković D. [1] 第一次提出了图的主特征值的概念。若图的邻接矩阵A的特征值
存在一个特征向量x,满足x与元素全为1的向量e不正交,即
,那么就称
为图的一个主特征值。Cvetković D.在文献 [1] 中提出问题,如何刻画恰有
个主特征值的图。对于一个连通图G,因为其邻接矩阵是不可约的,故由著名的Perron-Frobenius定理可知G的最大特征值为主特征值。更一般的,恰有一个主特征值的图为正则图 [1]。已经有一系列论文对于恰有两个主特征值的图进行了刻画,如Cardoso [2],Hagos [3], Hayat [4],Hou et al. [5] [6] [7],Lepović [8],Shi [9] 等,然而这项工作还远未完成。2012年Godsil C. [10] 猜想:几乎所有图的全部特征值均为主特征值,2016年O’Rourke [11] 证明了这个猜想的正确性,该结论说明主特征值对于刻画图及研究图的性质都有重要的意义。
2. 预备知识
定义2.1 [12] 对于n个顶点的图,其邻接矩阵定义为
,其中
。
由上述定义可知邻接矩阵为实对称矩阵且主对角元素为0。
定义2.2 [12] 路图
表示从一个顶点
出发,依次将新点
与
相连所得到的图。
定理2.3 [13] 路图
的特征多项式为
,
,
。
推论2.4 当
时,
为偶函数;当
时,
为奇函数。
证明:
时结论显然成立,
时,
,
,成立。
时,
,
,成立。
以此类推,n为奇偶的情况可交替证明,故结论成立。
定义2.5 [14] 星形树
表示将一个顶点
分别与路
的一端相连所构成的图,见图1。
Figure 1.
图1.
定理2.6 [14] 对于正整数m,星形树
的特征值为:
定义2.7 [12] 若图G的顶点集可划分为两个非空子集X和Y,使得图G的任一条边都有一个端点在X中,另一个端点在Y中,则称图G为二部图。
推论2.8 [12] 若图G为二部图,顶点集可划分为X和Y,其中它们的阶数分别s和t,则其全部特征值关于原点对称。进一步若特征值
对应特征向量
,则
对应特征向量
。
3. 一类星形树的主特征值数目
定理3.1 星形树
的主特征值数目有以下情况:当m为偶数时,
的主特征值数大于等于
,其中0是单根且为非主特征值;当m为奇数时,非零特征值
同为主特征值或同为非主特征值,且0是二重根,进一步当
时,0为非主特征值;当
时,0为主特征值
。
证明:首先分析图
根的情况,因为
,而
当且仅当
,说明只有m为奇数即
为偶数时,0是
的二重根,m为偶数时0为单根。因为余弦值
在区间
上单调递减,故图
的非零特征值均为单根,且关于原点对称。
设图
的邻接矩阵为
,易见
。对其特征值
及对应特征向量x有
,令
,展开方程得到:
(1)
由(1)式可知,A的每一个特征向量x都可以由最后一个分量
表示,不妨设
。
若
,则代入(1)式可得:
故易见向量
是对应特征值0的特征向量,即满足
,由
知0是非主特征值,且该0特征值不由
贡献。
将(1)式左右两端相加得:
化简得:
因为
,
,故
即
为非主特征值当且仅当
(2)
下面讨论
的情况。
此时显然
,否则有
,向量x无意义。
由(1)式知
时,有
,故(2)式可表示为:
(3)
因为
,故当
时(3)式左端恒大于零,等式矛盾,说明
时
,对应特征值
为主特征值。
1) 当
为偶数时,
为奇数,对于特征值
,若对应
的特征向量为
,因为
为二部图,连接在中心点
的两个一度点和
中与
的距离为奇数的顶点可划分为一个顶点集,则由推论2.8可得对应
的特征向量为
,
和
的第一个分量异号且不等于0,则
至少有一个为主特征值,这就说明对于奇数个顶点的图
,其至少有
个主特征值。
2) 当
为奇数时,
为偶数,对于特征值
,若对应
的特征向量为
,同理可得对应
的特征向量为
,
和
的第一个分量同号且不等于0,说明对于偶数个顶点的图
,其特征值
同为主特征值(或非主特征值)。
最后讨论0作为二重根出现的情况。
由上面分析可知当
为奇数,0是二重根,且其中一个0对应特征向量
。
将
代入(1)式并化简得:
观察可得向量
的分量满足递推关系
,且初始值
,
。则对比路
的特征多项式可得:
故由
可得:
代入(2)式有
(此时
)。
由
的奇偶性可得,
故当
时,
,
为主特征值;当
时,
,
为非主特征值,其中
。
定义3.2 [1] 对于一个图
,若其顶点集可划分为
,
为空集,其中
中的每个顶点在
中的邻点个数相同,记为
,
,则称该划分为图G的一个公平划分,记为
。以
为顶点集,
到
有
条弧的有向多重图称为图G的商图,矩阵
称为商矩阵。
定理3.3 [1] 对于图G的任意商图H,H的谱包含G的全部主特征值。
对于任意图G的一个公平划分
来说,因为每个划分
内的顶点处于G自同构群中的同一轨道,故由定理3.3可知,对于恰有k个主特征值的图,其自同构群至少有k条轨道。
推论3.4 星形树
至多有
个主特征值,其中
的个数分别为
。
证明:显然星形树
的顶点数为
,我们可以找到其阶数最小的商图H,点集划分如下:首先将长度相同的
分为一组,其中每条路
中与中心点
距离相同的点处于同一轨道,故可将同一轨道中的
个顶点划分为一个顶点集,因此对每组
来说,其可划分为因子图H中的
个顶点。同理每组
均可划分为H中的
个顶点,又中心点
自处一个轨道,故H的阶为
。由定理3.3知,任意商图的谱包含原图的全部主特征值,故星形树
至多有
个主特征值。
参考文献