A Solution Algorithm for the Same Spectrum of Two Π-Shaped Trees

Yi-zong WANG; Jing-wen LI; Fei WEN

doi:10.13718/j.cnki.xdzk.2018.08.013

A Π-shaped tree is a tree with a maximum degree of 3 and two vertices. In this paper, an algorithm for the same spectrum is proposed for the characteristics of the Π-shaped tree with its own spectrum. Exactly, the Π-shaped tree generation algorithm is employed to generate all the given order of non-isomorphic Π-shaped trees, and then the same spectrum characteristics are used to search for the same spectrum couple until all the internal spectrum couples of the Π-shapes trees are found. We give all the same spectrum couples of a given number of points of the Π-shaped trees, and give a detailed description of the algorithm and study results.

HTML

图谱理论是图论研究的一个重要分支，广泛地应用于复杂网络、聚类算法、机器学习、人脸表情识别及网络可靠性等领域的研究，同时在物理、化学等领域中也有广泛的应用.因此图谱理论的研究就显得尤为重要^[1-2].

图谱理论主要通过图矩阵的数量特征来研究图的组合结构，所涉及的图矩阵主要包括邻接矩阵、关联矩阵、拉普拉斯矩阵、广义邻接矩阵、距离矩阵等^[3-4].设图G为简单连通图，其邻接矩阵定义为为A=[a_ij]_n×n，其中${a_{ij}} = \left\{ \begin{gathered} 0\;\;\;\;\;i \ne j \hfill \\ 1\;\;\;\;\;i = j \hfill \\ \end{gathered} \right.$.令P_G(λ)=|λI－A|为A的邻接特征多项式，其中I为单位矩阵.方程|λI－A|=0的所有值以及重数称为图的谱，具有相同谱的图称为同谱图，同谱但不同构的图称为同谱偶.对于给定的图G，若“任意的图H与G同谱”蕴含着“H与G同构”，则称G是谱确定的^[5-6].

早在20世纪，Gunthard和Primas在研究化学中的Huckel理论时提出了“哪些图是谱确定的？”，近年来，这一问题引起了学者们的广泛关注.如果直接从谱确定的定义出发来回答这一问题，显然是困难的.相反地，对于某个给定的图，如果我们能找到它的一个同谱偶，则说明这个图一定不是谱确定的，因此关于谱确定的研究主要围绕两个问题展开：(a)判断哪些图是谱确定的；(b)如果不是谱确定的，寻找其所有的同谱偶.对于同谱偶的研究，从目前已知的结果来看，常用方法有：GM-变换^[7]和Schwenk-方法^[8].遗憾的是，通过设计算法来寻找同谱偶的研究甚少.文献[9-12]主要研究了谱确定性问题，提到了“同谱”，同时给了相关证明，但没有具体涉及同型图内部同谱偶的研究.文献[13]针对Π-型树的谱做了研究，将其分为6个类型，分别研究每个类型的特殊性质，同时给出了与Π-型树同谱的其它图的结构以及相关的数学证明.文献[14-15]给出了类似于Π-型树的H-型树和T-型树，结论与文献[13]的结论类似.

以上文献都没有研究在点边数相同的情况下Π-型树、H-型树之间的性质.本文针对此情况设计了一种新的算法，此算法设计生成了Π-型树，并求得了给定点数的Π-型树内部的同谱偶，同时给出了算法的详细描述和实验结果.

1. Π型树的相关概念

定义1 对于一棵树，如果最大度为3，且最大度顶点个数为2，则称该树为Π-型树，简记为Π(L1，L2，L3，L4，L5)，其结构为：

下面给出3个重要引理，这些引理对本文的算法设计起到重要作用.

引理1^[13] 假设H是与Π-型树同谱的图，那么H最多有2部分含圈.

引理2^[12] 对于图G，可以从其邻接谱推导出如下结论：(a)图的点数；(b)图的边数；(c)特征多项式；(d)特征值；(e)图是否正则；(f)图是否具有固定围长.

引理3^[4] Π-型树Π₂₂=Π(L₁，1，L₃，1，1)是由它的谱确定的，其中L₁＞1，L₃＞0.

2. 算法的详细描述

针对Π-型树设计了算法.在算法中，首先按照目标生成不同的Π-型树，然后求解出树对应矩阵的特征值，最后将所有的特征值进行两两比较，找出相等的特征值所对应的树图.

本算法包含算法1、算法2和算法3.算法1是Π-型树的生成算法，算法2是求Π-型树对应矩阵的特征值的算法，算法3是比较矩阵特征值并找出对应相等的参数L_p(p=1，2，3，4，5)的值的算法.

算法1 Π-型树生成算法

输入：总点数N

输出：点数为N的所有非同构Π-型树图的邻接矩阵

当给定总点数时，通过循环变量依次控制L_p(p=1，2，3，4，5)的值，使得其满足条件，最终输出Π-型树的矩阵A[][].算法伪代码如下所示：

Begin

For i=1 to N

  For j=1 to N

   If ∑L_p=N /*保证生成树图的点数为N*/

   and L1＜=L2 and L4＜=L5 and L1＜=L4 and L2＜=L5 /*保证生成的树与已有的不同*/

   Then开始生成图

   If (L_p!=0)

    Then A[][]=1

    For j=start L_p to end L_p/*start L_p和end L_p分别表示开始点和结束点*/

     A[j][j+1]=A[j+1][j]=1

    Else break

   End If

   memset(A)/*对A[][]清零，保证树图中不出现环*/

   If A[][]中有对应的树图同构

     Then不生成

   Else Then生成

  End For

End For

算法2 求矩阵的特征值的算法

输入：矩阵A[][]

输出：A[][]的特征值

首先对A[][]进行三角化(triangle(A))，对三角化后的矩阵按照QR分解法求其特征值，并将特征值分为实部和虚部存储在矩阵tzz[][]中.求的过程中设置一定的迭代次数L，保证求得解满足预设精度.同时求出A[][]矩阵的所有特征值.算法伪代码如下所示：

Begin

L：迭代次数：2 000

预设精度：ac=1.0e-12

M=N-1

triangle(A)/*对矩阵进行三角化*/

For i=0 to N-1

  For j=0 to 1

   tzz[i][j]=0

  End for

End for

For k=0 to L

  If (fabs(A[M][M-1]＜=ac))

  Then tzz[][0]=A[M][M] M--

  Else if (M==0) Then tzz[][0]=A[0][0]

  Else if (M==1)

  Then a=1，b=-(A[m-1][m-1]+A[m][m])，

   c=A[m-1][m-1]*A[m][m]-A[m-1][m]*A[m][m-1]

   root(a，b，c)/*求解一元二次方程*/

  If (fabs(A[M-1][M-2]＜=ac))

   Then root(a，b，c)

  Else Then

   For i=0 to N-1

    For j=0 to N-1

     If ((i＞=m+1)||(j＞=m+1))

      Then A[][]=0

    End for

   End for

  QR(M)/*求矩阵全部特征值的方法*/

End for

算法3 比较矩阵特征值并找出对应相等的参数L_p的算法

输入：矩阵特征值

输出：对应矩阵的参数对

将求出的矩阵特征值进行排序处理，然后对应比较，当出现两个矩阵的特征值相等时，输出矩阵对应的参数值L_p.算法伪代码如下：

Begin

For i=1 to N

  For w=1 to N-1-i

   sort(tzz[][])

  End for

End for

For i=i to s/*s表示Π-型树的个数*/

  For k=i+1 to s

   For j=1 to N

    If (tzz[k][j]==tzz[i][j])

    Then output L_p对

   End for

  End for

End for

3. 算法求解结果

本文采用算法针对n(n=30)个点以内的所有Π-型树进行求解.

(a) 当n≤8时，Π-型树内部没有同谱偶.

(b) 当n=9时，Π-型树及特征值如表 1所示.

根据表 1的结果，可以得出图5和图14的特征值相同.

c) 当10≤n≤30时，Π-型树的同谱偶结果见表 2.

从上述运行结果来看，特殊的Π-型树Π(L₁，1，L₃，1，1)内部不存在同谱偶，显然与引理3的结果相符.

4. 算法时间复杂度分析

本算法是在Windows 64位操作系统、4G内存、VS2010的环境下，针对Π-型树专门设计的.

1) 生成图.用n×n的矩阵来存储生成图，所以对于n个点的树而言，时间复杂度只与点数有关：T₁(Π)=Ο(n²)；

2) 求谱.是针对矩阵进行的，需要双层循环，同时令最大迭代次数为L，时间复杂度为T₂(Π)=Ο(L*n²)；

3) 比较特征值.由于每个矩阵有n个特征值且要进行两两比较，所以设置3层循环比较对应的值，时间复杂度为T₃(Π)=Ο(n³)；

综上分析，此算法的时间复杂度只与点数有关，所以为T(Π)=Ο(n³).

5. 结束语

本算法具有创新性和实用性，在之前的图论研究中没有类似的算法，可以用来解决化学领域的同分异构问题.由于计算机计算能力限制，本文求解得到了30个点以内的Π-型树内部的同谱偶，如果增加计算能力，可以利用本算法求解得到更大点数的Π-型树的同谱偶，为以后的图论研究提供可靠的数据.同时可以利用本算法思想，设计针对其它特殊图的同谱偶算法.但是仍然有一个问题，就是本算法的复杂度随着点数的增大而增大，希望以后的读者给予改进.

Table (2) Reference (15)

Name
	Name cannot be empty!
E-mail
	Mailbox cannot be empty! Mailbox cannot be empty!
Telephone
	Mobile number cannot be empty! Please enter a valid mobile number!
Title

Content
Verification Code

[1]	BONDY J A, MURTY U S R. Graph Theory with Application[M]. North-Holland:Amsterdam, 1976. Google Scholar
[2]	方富贵.图论的算法和应用研究[J].计算机与数字工程, 2012, 40(2):115-117. Google Scholar
[3]	文飞. 若干图类的谱特征问题研究[D]. 乌鲁木齐: 新疆大学, 2015.http://cdmd.cnki.com.cn/Article/CDMD-10755-1015801274.htm Google Scholar
[4]	刘奋进. 图邻接谱确定问题的一些研究[D]. 乌鲁木齐: 新疆大学, 2012.http://cdmd.cnki.com.cn/Article/CDMD-10755-1012433701.htm Google Scholar
[5]	汪小玲.点圈并图的匹配等价图数[J].西南大学学报(自然科学版), 2016, 38(8):35-39. Google Scholar
[6]	王文霞.无向无权图同构判别算法[J].西南师范大学学报(自然科学版), 2017, 42(3):141-145. Google Scholar
[7]	GODSIL C D, MCKAY B D. Constructing Cospectral Graphs[J]. Aequa Math 1982, 25(1):257-268. doi: 10.1007/BF02189621 CrossRef Google Scholar
[8]	SCHWENK A J. Almost All Trees Are Cospectral[J]. New Directions in the Theory of Graphs, 1973(1):275-307. Google Scholar
[9]	王卫, 徐成贤. T-型树T(1, l, m)可由其谱唯一决定[J].应用数学, 2005(S1):34-38. Google Scholar
[10]	王忠.一种由邻接谱确定的树[J].青海师范大学学报(自然科学版), 2011, 27(3):5-9. Google Scholar
[11]	刘翼举, 侯耀平.一些由它的邻接谱和角确定的图[J].邵阳学院学报(自然科学版), 2009, 6(2):5-7. Google Scholar
[12]	DAM E R V, HAEMERS W H. Which Graphs Are Determined by Their Spectrum[J]. Linear Algebra Appl, 2002, 373:241-272. Google Scholar
[13]	LIU F J, HUANG Q X. On the Spectral Characterization of-Shape Trees[J]. Linear and Multilinear Algebra, 2013, 61(3):355-367. doi: 10.1080/03081087.2012.672569 CrossRef Google Scholar
[14]	HU S B. On the Spectral Characterization of H-Shape Trees[J]. Advances in Linear Algebra & Matrix Theory, 2014, 4(2):79-86. Google Scholar
[15]	王卫, 徐成贤. T-型树谱唯一性的一个简单刻画[J].数学研究, 2006, 39(1):68-76. Google Scholar

Message Board

A Solution Algorithm for the Same Spectrum of Two Π-Shaped Trees

Abstract

References

Access History

通讯作者: 陈斌, bchen63@163.com

Article Metrics

Access History

Other Articles By Authors