两棵Π-型树同谱的求解算法

王义宗; 李敬文; 文飞

doi:10.13718/j.cnki.xdzk.2018.08.013

两棵Π-型树同谱的求解算法

1.
兰州交通大学电子与信息工程学院, 兰州 730070

2.
兰州交通大学应用数学研究所, 兰州 730070

基金项目: 国家自然科学基金项目（11461038）；兰州交通大学青年基金项目（2016014）

详细信息

作者简介:
王义宗(1990-), 男, 硕士研究生, 主要从事图论算法及应用的研究 .

通讯作者: 李敬文, 教授;

中图分类号: O157.6;TP301

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

1.
School of Electronic & Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China

2.
Institute of Applied Mathematics, Lanzhou Jiaotong University, Lanzhou 730070, China

摘要: Π-型树是最大度为3的且恰有2个顶点的树.针对Π-型树与自身的同谱特征设计了一种同谱偶求解算法.确切地，根据Π-型树生成算法生成所有给定阶数的非同构Π-型树，然后利用同谱特征寻找同谱偶，直到找出Π-型树内部所有的同谱偶为止.通过该算法得到了给定点数的Π-型树内部的所有同谱偶，并给出了算法的详细描述和结果.
- Π-型树 /
- 同谱图 /
- 算法
Abstract: 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.
- Π-shaped tree /
- cospectral graph /
- algorithm .

表 1 图结构以及对应特征值

图序号	图结构	特征值
图1		r1-r3	-1.902 11	-1.618 03	-1.175 57
		r4-r6	-0.618 03	0	0.618 03
		r7-r9	1.175 57	1.618 03	1.902 11
图2		r1-r3	-2	-1.618 03	-1
		r4-r6	-0.618 03	0	0.618 03
		r7-r9	1	1.618 03	2
图3		r1-r3	-2.015 32	-1.548 01	-1.142 88
		r4-r6	-0.485 78	0	0.485 78
		r7-r9	1.142 88	1.548 01	2.015 32
图4		r1-r3	-1.961 57	-1.662 94	-1.111 14
		r4-r6	-0.390 18	0	0.390 18
		r7-r9	1.111 14	1.662 94	1.961 57
图5		r1-r3	-2.083 97	-1.571 84	-1
		r4-r6	-0.431 73	0	0.431 73
		r7-r9	1	1.571 84	2.083 97
图6		r1-r3	-2.060 82	-1.598 42	-1.094 56
		r4-r6	0	0	0
		r7-r9	1.094 56	1.598 42	2.060 82
图7		r1-r3	-2.035 65	-1.690 69	-0.884 13
		r4-r6	-0.464 76	0	0.464 76
		r7-r9	0.884 13	1.690 69	2.035 65
图8		r1-r3	-2	-1.732 05	-1
		r4-r6	0	0	0
		r7-r9	1	1.732 05	2
图9		r1-r3	-2.111 99	-1.496 37	-1
		r4-r6	-0.548 06	0	0.548 06
		r7-r9	1	1.496 37	2.111 99
图10		r1-r3	-2.074 31	-1.618 03	-0.835
		r4-r6	-0.618 03	0	0.618 03
		r7-r9	0.835	1.618 03	2.074 31
图11		r1-r3	-2.052 88	-1.414 21	-1.208 64
		r4-r6	-0.569 97	0	0.569 97
		r7-r9	1.208 64	1.414 21	2.052 88
图12		r1-r3	-2.042 08	-1.520 23	-1
		r4-r6	-0.720 28	0	0.720 28
		r7-r9	1	1.520 23	2.042 08
图13		r1-r3	-2.119 17	-1.414 21	-1.159 04
		r4-r6	-0.407 13	0	0.407 13
		r7-r9	1.159 04	1.414 21	2.119 17
图14		r1-r3	-2.083 97	-1.571 84	-1
		r4-r6	-0.431 73	0	0.431 73
		r7-r9	1	1.571 84	2.083 97
图15		r1-r3	-2.135 78	-1.414 21	-1
		r4-r6	-0.662 15	0	0.662 15
		r7-r9	1	1.414 21	2.135 78

下载: 导出CSV

表 2 10≤n≤30时Π型树的同谱对

点数	Π-型树的同谱对
10	Π(1，1，0，1，5)和Π(1，2，1，1，3)，Π(1，1，0，2，4)和Π(1，3，0，1，3)
11	Π(1，1，0，1，6)和Π(1，1，2，2，3)，Π(1，2，0，1，5)和Π(1，2，1，2，3)
12	Π(1，1，0，2，6)和Π(1，3，1，2，3)，Π(1，1，2，2，4)和Π(1，2，1，1，5)，Π(1，1，2，3，3)和Π(1，3，1，1，4)，Π(1，1，3，2，3)和Π(1，3，2，1，3)，Π(1，1，4，2，2)和Π(1，2，3，1，3)，Π(1，2，1，3，3)和Π(1，3，0，1，5)
13	Π(1，1，0，1，8)和Π(1，1，3，2，4)，Π(1，1，1，2，6)和Π(1，1，2，3，4)，Π(1，2，0，3，5)和Π(1，4，0，2，4)，Π(1，2，1，3，4)和Π(1，4，0，1，5)，Π(1，3，0，1，6)和Π(1，3，1，2，4)
14	Π(1，1，0，1，9)和Π(1，3，2，1，5)，Π(1，1，1，2，7)和Π(1，4，1，1，5)，Π(1，1，5，2，3)和Π(1，3，3，1，4)，Π(1，2，0，1，8)和Π(1，2，2，3，4)，Π(1，2，0，2，7)和Π(2，3，1，2，4)，Π(1，2，1，3，5)和Π(1，5，0，1，5)
15	Π(1，1，0，1，10)和Π(1，1，4，2，5)，Π(1，1，1，2，8)和Π(1，1，3，4，4)，Π(1，1，3，3，5)和Π(1，3，1，1，7)，Π(1，2，1，3，6)和Π(1，5，0，1，6)，Π(1，4，0，1，7)和Π(1，4，1，2，5)
16	Π(1，1，0，2，10)和Π(1，3，2，3，5)，Π(1，1，0，5，7)和Π(1，3，1，4，5)，Π(1，1，4，2，6)和Π(1，3，2，1，7)，Π(1，2，1，2，8)和Π(1，2，2，4，5)，Π(1，2，5，3，3)和Π(1，3，4，2，4)
17	Π(1，1，0，1，12)和Π(1，1，5，2，6)，Π(1，1，1，2，10)和Π(1，1，4，4，5)，Π(1，1，2，3，8)和Π(1，1，3，4，6)
18	Π(1，2，0，1，12)和Π(1，2，3，4，6)
19	Π(1，1，0，1，14)和Π(1，1，6，2，7)，Π(1，1，1，2，12)和Π(1，1，5，4，6)，Π(1，1，2，3，10)和Π(1，1，4，5，6)
20	无
21	Π(1，1，0，1，16)和Π(1，1，7，2，8)，Π(1，1，1，2，14)和Π(1，1，6，4，7)，Π(1，1，2，3，12)和Π(1，1，5，6，6)，Π(1，1，3，4，10)和Π(1，1，4，5，8)
22	无
23	Π(1，1，0，1，18)和Π(1，1，8，2，9)，Π(1，1，1，2，16)和Π(1，1，7，4，8)，Π(1，1，2，3，14)和Π(1，1，6，6，7)，Π(1，1，3，4，12)和Π(1，1，5，6，8)
24	无
25	Π(1，1，0，1，20)和Π(1，1，9，2，10)，Π(1，1，1，2，18)和Π(1，1，8，4，9)，Π(1，1，2，3，16)和Π(1，1，7，6，8)，Π(1，1，3，4，14)和Π(1，1，6，7，8)，Π(1，1，4，5，12)和Π(1，1，5，6，10)
26	无
27	Π(1，1，2，3，18)和Π(1，1，8，6，9)，Π(1，1，3，4，16)和Π(1，1，7，8，8)，Π(1，1，4，5，14)和Π(1，1，6，7，10)
28	无
29	Π(1，1，5，6，14)和Π(1，1，6，7，12)
30	无

下载: 导出CSV

[1]	BONDY J A, MURTY U S R. Graph Theory with Application[M]. North-Holland:Amsterdam, 1976.
[2]	方富贵.图论的算法和应用研究[J].计算机与数字工程, 2012, 40(2):115-117. doi: http://www.wanfangdata.com.cn/details/detail.do?_type=degree&id=Y1348038
[3]	文飞. 若干图类的谱特征问题研究[D]. 乌鲁木齐: 新疆大学, 2015.http://cdmd.cnki.com.cn/Article/CDMD-10755-1015801274.htm
[4]	刘奋进. 图邻接谱确定问题的一些研究[D]. 乌鲁木齐: 新疆大学, 2012.http://cdmd.cnki.com.cn/Article/CDMD-10755-1012433701.htm
[5]	汪小玲.点圈并图的匹配等价图数[J].西南大学学报(自然科学版), 2016, 38(8):35-39. doi: http://xbgjxt.swu.edu.cn/jsuns/jsuns/ch/reader/view_abstract.aspx?file_no=201608007&flag=1
[6]	王文霞.无向无权图同构判别算法[J].西南师范大学学报(自然科学版), 2017, 42(3):141-145. doi: http://cs.tju.edu.cn/faculty/hyh/discrete%20mathematics/07%20图的基本概念.pdf
[7]	GODSIL C D, MCKAY B D. Constructing Cospectral Graphs[J]. Aequa Math 1982, 25(1):257-268. doi: 10.1007/BF02189621
[8]	SCHWENK A J. Almost All Trees Are Cospectral[J]. New Directions in the Theory of Graphs, 1973(1):275-307.
[9]	王卫, 徐成贤. T-型树T(1, l, m)可由其谱唯一决定[J].应用数学, 2005(S1):34-38.
[10]	王忠.一种由邻接谱确定的树[J].青海师范大学学报(自然科学版), 2011, 27(3):5-9. doi: http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=qhsfdxxb-zrkx201103002
[11]	刘翼举, 侯耀平.一些由它的邻接谱和角确定的图[J].邵阳学院学报(自然科学版), 2009, 6(2):5-7. doi: http://www.cnki.com.cn/Article/CJFDTOTAL-CUXI201109047.htm
[12]	DAM E R V, HAEMERS W H. Which Graphs Are Determined by Their Spectrum[J]. Linear Algebra Appl, 2002, 373:241-272.
[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
[14]	HU S B. On the Spectral Characterization of H-Shape Trees[J]. Advances in Linear Algebra & Matrix Theory, 2014, 4(2):79-86.
[15]	王卫, 徐成贤. T-型树谱唯一性的一个简单刻画[J].数学研究, 2006, 39(1):68-76. doi: http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=sxyj200601012

表( 2)

计量

文章访问数: 1108
HTML全文浏览数: 694
PDF下载数: 135
施引文献: 0

全文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个点以内的Π-型树内部的同谱偶，如果增加计算能力，可以利用本算法求解得到更大点数的Π-型树的同谱偶，为以后的图论研究提供可靠的数据.同时可以利用本算法思想，设计针对其它特殊图的同谱偶算法.但是仍然有一个问题，就是本算法的复杂度随着点数的增大而增大，希望以后的读者给予改进.

参考文献 (15)

姓名
	姓名不能为空！
邮箱
	邮箱不能为空！非法的邮箱地址。
手机号码
	电话不能为空！请输入有效手机号!
标题
	标题不能为空！
留言内容
	内容不能为空！
验证码
	验证码不能为空！验证码错误！

留言板

两棵Π-型树同谱的求解算法

1.
兰州交通大学电子与信息工程学院, 兰州 730070

2.
兰州交通大学应用数学研究所, 兰州 730070

作者简介:
王义宗(1990-), 男, 硕士研究生, 主要从事图论算法及应用的研究 .

通讯作者: 李敬文, 教授;

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

1.
School of Electronic & Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China

2.
Institute of Applied Mathematics, Lanzhou Jiaotong University, Lanzhou 730070, China

计量

两棵Π-型树同谱的求解算法

通讯作者: 李敬文, 教授;

作者简介: 王义宗(1990-), 男, 硕士研究生, 主要从事图论算法及应用的研究
1. 兰州交通大学电子与信息工程学院, 兰州 730070

2. 兰州交通大学应用数学研究所, 兰州 730070

English Abstract

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

Corresponding author: Jing-wen LI ;

全文HTML

目录

留言板

两棵Π-型树同谱的求解算法

1. 兰州交通大学 电子与信息工程学院, 兰州 730070 2. 兰州交通大学 应用数学研究所, 兰州 730070

作者简介: 王义宗(1990-), 男, 硕士研究生, 主要从事图论算法及应用的研究 .

通讯作者: 李敬文, 教授;

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

1. School of Electronic & Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China 2. Institute of Applied Mathematics, Lanzhou Jiaotong University, Lanzhou 730070, China

计量

出版历程

两棵Π-型树同谱的求解算法

通讯作者: 李敬文, 教授;

作者简介: 王义宗(1990-), 男, 硕士研究生, 主要从事图论算法及应用的研究 1. 兰州交通大学 电子与信息工程学院, 兰州 730070 2. 兰州交通大学 应用数学研究所, 兰州 730070

English Abstract

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

Corresponding author: Jing-wen LI ;

全文HTML

目录

1.
兰州交通大学电子与信息工程学院, 兰州 730070

2.
兰州交通大学应用数学研究所, 兰州 730070

作者简介:
王义宗(1990-), 男, 硕士研究生, 主要从事图论算法及应用的研究 .

1.
School of Electronic & Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China

2.
Institute of Applied Mathematics, Lanzhou Jiaotong University, Lanzhou 730070, China

作者简介: 王义宗(1990-), 男, 硕士研究生, 主要从事图论算法及应用的研究
1. 兰州交通大学电子与信息工程学院, 兰州 730070

2. 兰州交通大学应用数学研究所, 兰州 730070