强正则图与完全图字典积的平均首达时间及其应用

倪湘钧，徐 慧，潘向峰

（安徽大学 数学科学学院，安徽 合肥 230601）

平均首达时间是有限马尔可夫链中的一个重要参数，广泛应用于物理、化学、统计学上。国内外学者致力于寻找平均首达时间的简约表达式与数值计算。陈海燕等[1]给出了强正则图及其与带自环的完全图、完全图等经过二元运算（弱直积、直积、卡氏积）后所得到图的平均首达时间表达式和对于赋权有向图上的随机游走，利用最小多项式刻画了任意两顶点间的平均首达时间计算公式。文献[2]给出了强正则图的特征值与其对应重数的完整信息。王志俊等[3]刻画了连通图G与正则图H作字典积对应的谱。文献[4]给出了正则图最小多项式与其特征值重数之间的关系。受到上述文献的启发，本文考虑强正则图与完全图字典积的平均首达时间表达式及其应用，且本文只考虑简单的无向连通图，所涉及的其他图论术语可参见文献[5]。

1 预备知识

定义1 设G=(V,E)是一个阶为d的k正则图，若G满足任意两个相邻顶点的公共邻点个数为λ，任意两个不相邻顶点的公共邻点个数为μ，其中λ，μ(μ＞1)是常数，则称之为具有参数(d,k,λ,μ)的强正则图。

这里Aij(2)表示A2的ij元素。

命题[7]设H是m阶完全图，其邻接矩阵特征值为-1，m-1，对应重数分别为m-1，1。

定义2图G和图H的字典积G[H]指顶点集为V(G)×V(H)的简单图，其中(u,v)与(u′,v′)相邻当且仅当uu′∈E(G)，或者u=u′且vv′∈E(H)。

下面利用图G和正则图H的特征值来表示其字典积G[H]的特征值。

定理1[3]设图G的特征值为λ1,λ2,λ3,…,λn(λ1≥λ2≥λ3≥…≥λn)，正则图H的特征值为μ1,μ2,μ3,…,μm(μ1≥μ2≥μ3≥…≥μm)，则相应字典积图G[H]的特征值为λ1m+μ1,λ2m+μ1,λ3m+μ1,…,λn m+μ1,μ2,μ3,…,μm，且μ2,μ3,…,μm的重数均为n。

图1 字典积图G1[H1]

定理2[1]设P是图G上随机游走的概率转移矩阵，若多项式f(x)=xn+a1xn-1+a2xn-2+…+an-1x+an，满足f(1)≠0且f(P)是一个具有相同行向量的矩阵，那么对于任意i,j∈V，有

其中，πj是图G上随机游走的平稳分布π的第j个分量。

因为P是概率转移矩阵，即非负不可约的随机矩阵，所以1是P重数为1的最大特征值。由文献[1]可知P的最小多项式q(x)=(x-1)f(x)，故只需研究P的最小多项式即可得到满足具有相同行向量的矩阵f(P)且f(1)≠0的f(x)，进一步研究平均首达时间。

定理4[9]设G是一个具有m条边n个点的连通图，则Kf*(G)=2mKe(G)。

现利用强正则图与完全图字典积中任意两点的平均首达时间来表示图中任意两点间的电阻距离。

定理5[9]设G是一个具有m条边的连通图，则对任意i,j∈VG，有EiTj(G)+EjTi(G)=2mrij(G)。

2 主要结果

下面给出强正则图与完全图字典积中任意两点间的平均首达时间。设G是一个具有参数(d,k,λ,μ)的强正则图，A为G的邻接矩阵。设H是m阶完全图，则G[H]是一个阶为dm的m+mk-1正则连通图。由文献[3]知，G[H]的邻接矩阵为A(G[H])=A(G)⊗J+I⊗A(H)，这里⊗表示张量积，J表示全1矩阵。由定理1可知，G[H]只有4个不同的特征值：m+mk-1，m+mr-1，m+ms-1，-1。它的最小多项式[4]为

因为H是m阶完全图，所以对于∀v1,v2∈V(H)，它们均是邻接的，故只需对u1，u2的情况进行分类讨论。利用定理2，可以得到以下结论。

定理6对于G[H]上的简单随机游走，对∀i=u1v1，j=u2v2∈V(G[H])，有

接下来，根据字典积图G[H]和图G特征值之间的关系，计算一些与G[H]有关的图不变量，给出G[H]的度积基尔霍夫指数和凯梅尼常数的公式。此外，基于G[H]任意两个顶点之间的平均首达时间，建立G[H]上任意两个顶点之间的电阻距离。这些图不变量均由图G和图H的参数和相关不变量决定。对于度积基尔霍夫指数，文献[8]给出了它与N(G)特征值之间的良好关系。

3 结束语

近年来，有限图上的随机游走在近似算法设计上的应用受到了国内外学者的广泛关注，算法的相关性能又与随机游走上的平均首达时间、通勤时间等紧密相关。通过研究文献[1]中关于强连通非周期有向图上随机游走平均首达时间的新表达式，结合文献[4]中两图的谱与二者字典积图的谱的关系，本文得到强正则图与完全图字典积的谱与邻接矩阵，再利用代数方法进一步研究对应字典积图上任意两点间的平均首达时间、电阻距离、度积基尔霍夫指数和凯梅尼常数。另外，随机游走与电网络之间有着紧密的联系，这也是今后研究的重点方向。