单圈图的谱矩公式

吴亚平，周理泳，薛振宇，董 娜，崔娟娟，李依婷

（江汉大学 人工智能学院，湖北 武汉 430056）

0 引言

图的谱理论是代数图论的一个重要研究领域［1］，其研究的主要途径是通过图的矩阵表示，建立图的拓扑结构和图的矩阵表示的相似不变量之间的联系，从而刻画图的结构特征。

20世纪上半叶以来，图的研究与化学的分子结构发生了新的联系。分子轨道理论与图的邻接谱之间存在着明确的对应关系，图的邻接谱对应于分子能量级，特征向量对应于分子轨道，而邻接矩阵的所有特征值的绝对值之和（定义为图的能量）可用来近似分子的总π-电能。在一定程度上，它反映了其对应分子的稳定性等物理化学性质。图的邻接矩阵的谱矩已成为研究共轭分子拓扑理论的常用工具，其中一个重要的应用是在计算分子的总π-电能及不同的共振能方面；另一个重要应用是在研究固体的物理化学性质方面。

1 预备知识

本文中只考虑简单图。本文中出现而未介绍的定义参照文献［1］。设G=(V(G),E(G))，其中V(G)表示G的顶点集，E(G)表示G的边集，称G是一个|V(G)|-阶图。若G中由顶点和边构成的一个交替序列v0e1v1e2v2…v m-1e m v m满足边e i的两个端点为v i-1和v（ii=1,2,…,m），称此序列为G的一条(v0,v m)-途径。若v0=v m，则称它是一条闭途径。分别用P n,C n,K1,n表示n个点的路、圈和星树。一个连通无圈图称其为一棵树。若G是一个连通图，满足|E(G)|=|V(G)|,称G是一个单圈图。令C k是单圈图G中唯一的圈，G-E(C k)中每个连通分支称为G的一棵悬挂树。若一棵悬挂树边数大于0，称其是非平凡的；否则称其为平凡的。

n阶图G的邻接矩阵A(G)=[a i j]n×n，这里a i j=1,v i与v j相邻；否则a i j=0(i,j=1,2,…,n)。由于邻接矩阵A(G)是n阶实对称矩阵，则其n个特征值λ1≥λ2≥…≥λn均为实数。图G的第k阶谱矩称为图G的谱矩序列。关于谱矩序列进行排序研究也是一个非常有趣的问题，文献［8-14］对树、单圈图及双圈图进行了谱矩序列全序排序研究。

当一条长为k的闭途径W经过图H每条边至少一次时，我们称图H能生成闭途径W。用记号ϕk(H)表示H生成长为k的不同闭途径条数，在不引起混淆情况下，用记号ϕ(H)表示。本文中我们将给出单圈图前10阶谱矩计算公式。树子图只能生成长为偶数的闭途径，且闭途径长度至少是树子图边数的2倍。边数至多是5的非平凡树有：P2,P3,P4,P5,P6,K1,3,K1,4,K1,5,T1,T2,T3,T4,T5（见图1）。

图1 T1,T2,T3,T4,T5（边数至多是5的非路及非星树）Fig.1 T1,T2,T3,T4,T5(Trees except for paths and stars,which edge numbers are at most 5)

图2给出能生成长为7或8的闭途径单圈子图（不含C n,C1n，C1n表示圈C n一个顶点与P2一个端点粘合所得图）。

图2 能生成长为7或8闭途径的含悬挂树单圈子图（不含）Fig.2 The unicyclic graphs which have the pendant trees and can generate the length of 7 or 8 closed walks(except Cn1)

要生成长为8的闭途径，树子图边数至多是4。根据文献［3-5］的结论，我们得到单圈图的前8阶谱矩计算公式如下。

命题1设G是n阶单圈图，则

下面给出证明本文主要结论时需要用到的几个引理。

引理1［2］图G的第k阶谱矩等于G中长为k的闭途径的条数。

引理2二部图只能生成长为偶数的闭途径。

2 主要结果

本节中设计了基于深度优先的搜索算法，利用该算法求解对于任意给定一个子图，由这个子图生成长为k的不同闭途径条数。这个算法为得到任意阶谱矩公式提供一种可能。介绍算法之前，先给出一些定义。图的邻接表由图中每个顶点和顶点相邻的列表组成。设V(G)={v1,v2,…,v n}，对于顶点v i，a[i][j]表示与顶点v i有边相连的第j个顶点。v i相邻的列表用数组a[i][j]表示，j=1,2,…,d(v i)。另外我们记a[i][0]=d(v i)(i=1,2,…,n)。令W是G中的一条闭途径，定义V i s i t e d[i][j]为W经过边v i v j的总次数，称数组V i s i t ed[i][j]为W的标记数组。

为了方便操作，我们将顶点v i记为i(i=1,2,…,n)。k为所求闭途径长度，y表示当前已搜索的途径长度，数组W[y]为存储途径上的第y+1个结点，V i s i t e d[i][j]为标记数组，S为长为k的闭途径的条数，初始状态令S=0，i,j,X（结点）均为中间变量。

基于深度优先搜索子图生成长为k的不同闭途径条数算法：

1）从结点v i出发搜索，若i不大于顶点数n，置X={v i}，令已搜索途径长y=0，i加1，否则程序结束；

2）置W[y]=X（即将当前搜索到的结点X存入数组W中），若当前途径长y与k相等，则执行步骤4），否则执行步骤3）；

3）选取与结点X有边相连且未被访问过的结点a[X][j]，用a[X][j]代替X，令已搜索途径长y加1，执行步骤2），若无则执行步骤1）；

4）若当前结点W[y]与W[0]相同，则执行步骤5），否则退回到步骤3）；

5）构建标记数组V i s i t ed[i][j]，并依据数组W的数据对V i s i t e d[i][j]各元赋值；

6）判断给定子图的每条边是否都已经在W中，即V i s i t e d[i][j]相应元是否都大于0，若是则执行步骤7），否则退回到步骤3）；

7）输出该闭途径W，闭途径条数S加1，退回到步骤3）。

任意k阶谱矩，只要能找到所有能生成k阶闭途径的子图，用上述算法就能找到k阶谱矩的公式。算法代码参看链接http：∥qr61.cn/oK6EzX/q3CuHpU。

下面我们将分别给出单圈图的第9阶谱矩和第10阶谱矩计算公式。图3给出能生成长为9的闭途径单圈子图（不含C n,C1n，H1,H2,H3）。

图3 能生成长为9闭途径的含悬挂树单圈子图（不含C1n,H1,H2,H3）Fig.3 The unicyclic graphs which have the pendant trees and can generate the length of 9 closed walks(except C1n,H1,H2,H3)

定理1G是单圈图，则

证明树子图、偶圈C4,C6,C8及分别以C4,C6,C8为基圈的单圈图，它们都是二部图。根据引理2，它们都不能生成长为9的闭途径。因此能生成长为9的闭途径子图一定含奇圈C t,t∈{3,5,7,9}。不含悬挂树的单圈图为C3,C5,C7,C9。下面考虑含悬挂树的单圈图。单圈图的基图C m，其中m∈{3,5,7}。当m=7时，根据引理3，所有悬挂树边数和不超过1。此时恰有1个悬挂树是非平凡的，则子图为C17。

根据算法，我们得到图G中长为9的闭途径的总条数，根据引理1，得到第9阶谱矩公式。故定理1成立。

下面给出图的第10阶谱矩计算公式。首先在图4中给出能生成长为10的闭途径单圈子图（不含C n,C1n，H1,H2,…,H7）。

图4 能生成长为10闭途径的含悬挂树单圈子图（不含C1n,H1,H2,…,H7）Fig.4 The unicyclic graphs which have the pendant trees and can generate the length of 10 closed walks(except C1n,H1,H2,…,H7)

定理2G是单圈图，则

证明对任意一棵树T，若1≤| |E(T)≤5，则它能生成长为10的闭途径。因此能生成长为10的闭途径树子图为：P2,P3,P4,P5,P6,K1,3,K1,4,K1,5,T1,T2,T3,T4,T5。

下面我们考虑能生成长为10的闭途径单圈子图。由于C7,C9生成最小偶数阶闭途径长分别为14和18，因此能生成长为10的闭途径不含悬挂树的单圈图为C3,C4,C5,C6,C8,C10。下面考虑含悬挂树的单圈图。由于树子图只能生成长为偶数的闭途径，C5,C7生成最小偶数阶闭途径长分别为10和14，因此能生成长为10的闭途径单圈子图的基图C m，满足m∈{3,4,6,8}。

当m=3时，根据引理3，所有悬挂树边数和不超过3。由于C3不能形成长为4的闭回路，因此所有悬挂树边数和不超过2。若恰有1个悬挂树是非平凡的，则子图为，H1,H3。若有2个悬挂树是非平凡的，则子图为H2。

当m=4时，根据引理3，所有悬挂树边数和不超过3。若恰有1个悬挂树是非平凡的，则子图为，H4,H7,H19,H20,H21,H22。若有2个悬挂树是非平凡的，则子图为H5,H6,H23,H24,H25,H26。若有3个悬挂树是非平凡的，则子图为H27。

当m=6时，根据引理3，所有悬挂树边数和不超过2。若恰有1个悬挂树是非平凡的，则子图为，H28,H29。若有2个悬挂树是非平凡的，则子图为H30,H31,H32。

当m=8时，根据引理3，所有悬挂树边数和不超过1。此时恰有1个悬挂树是非平凡的，则子图为。

根据算法，我们得到图G中长为10的闭途径的总条数，根据引理1，得到第10阶谱矩公式。故定理2成立。