树的谱矩研究

李星宇

【摘要】谱矩序列作为图的一个非常不可或缺的重要特征，在重构猜想研究中，及寻求图中的不变量的完全组，起到了事关重要的作用。谱矩序列与通过研究树的结构特征，首先确定能生成长为8的闭途径的所有树子图，然后给出树的前8阶谱矩计算公式。

【关键词】树 星树 树的谱矩

【中图分类号】G64 【文献标识码】A 【文章编号】2095-3089（2018）50-0147-02

引言

1942年Kelly和Ulam提出重构猜想。重构猜想至今为止依然是三大著名图论里的难题之一。至今为止关于重构猜想是否是NP-C问题仍无定论。找出图中的不变量的完全组和一组特征或参数，是在重构猜想的研究中非常关键的一个步骤，从而可以准确确定一个图。目前图论里还存在了许多相关参数，如：连通度、最大匹配的边数、阶、度序列、最小度、 最大度等等。但关于图里的不变量的完全组的确定现在仍然有很多问题还在探索之中。由于图的k阶谱矩等于图中长为 k 的闭途径的条数，从而可知在谱矩序列中确定图的闭途径。因此图的谱矩序列的确定图的闭途径的条数，对研究重构猜想也是起到事关重要的意义的。（重构猜想）如果G是至少有3个顶点的简单图，则G由它的顶点删除子图序列唯一确定。20世纪以来图的排序问题成为代数图论中比较有趣的问题之一。在1987年，Cvetkovíc和Rowlinson分别给出图的前4阶谱矩的计算公式，同时给出树和单圈图依谱矩序排在最前和最后的图。2009年范琼等2010年吴亚平等分别给出图的第5阶和第6阶谱。2011年Pan X F等给出了最大度的树谱矩序排序。2012年Pan X F等伪树图谱矩序排序。本文将给出树的前10阶谱矩的计算公式。

1.预备知识

通常的我们将一个图定义为G=（V（G），E（G））其中我们一般令V（G）为图G的定点的个数，E（G）为图的边的个数，然而仅仅依靠定点和边的个数还不足以确定一个图的形状，其存在的不同形式类似于化学中的同分异构，如果能找出点和边的一般规律就可以很大程度上的去解决相关问题。然后是对于闭途径W的定义，闭途径为图的点边交替形成的一串序列，形如v0，e0，v1，e2，…ek ，vk其中v为不同的定点e为不同的边点边交替可以唯一确定一条路径如果此时v0=vk即图的首尾是相同的定点，那么该途径称之为图的闭途径。当此时如果其中所有闭途径的点都没有重复，那么形成的图可以称之圈。无论是对于途径圈亦或是路的长度都是指其中边的条数，列如v0、e0、v1、e0、v1就为一条闭途径。通常我们将圈和路分别令为Ck，Pk+1其长度均为k。我们又通常将连通且不成圈的图称之为树。其中又存在一种极为特殊的情况，当其存在一中心定点与其它所有定点均相邻的图我们称之为星树，并将中心点称之为星树的中心点n个顶点的星树称之为K1，n-1。

引理1 图的k阶谱矩为图的G的n个特征值的k次幂之和，其中特征值为图G的邻接矩阵A（G）=[aij]n*n其中若两定点相邻的话aij=1，反之若不相邻则aij=0，图的特征值就是图G的特征值，因此图的特征值为（G），由此可得知图的谱矩序列S=（S0（G），S1（G），…，Sn（G））。

引理2 图G的第k阶谱矩等于G中长为k的闭途径的个数

引理3 设G是n阶图，则S0（G）=n S1（G）=l S2（G）=2m S3（G）=6t S4（G）=2m+4p+8q，其中l，m，t分别表示图中环、边、三角形的个数，p、q分别表示相邻边对和四边形的个数。

引理4 设G是n阶图，则S6（G）=2p2+12p3+6p4+12k1，3+24c4+12c1+12c6+24a3，3+26b3，3其中c表示G中圈的个数，p则表示G中路的个数，k代表图中的星树个数，上下角标表示带有悬挂点的圈子图的个数。

2.主要结果

根据引理1-5可知，n 阶树 T 的任意奇数阶谱矩皆为0，前 8阶偶数阶谱矩为：

S0（T）=n

S2（T）=2（n-1）

S4（T）=2（n-1）+4p3

S6（T）=2（n-1）+12p3+6p4+12k1，4

S8（T）=2p2+28p3+32p4+8p5+16p14+72k1，3+48k1，4

下面给出树第10阶谱矩计算公式

S10（T）=2p2+60p3+114p4+60p6+10p6+120p14+18p15+288k1，3+480k1，4+240k1，5+40m1+60m2+24m3

p2左右两点分别标记为a、b，从两个顶点出发各有1条长为10的闭途径：ababcbabcba abcbababcba 所以共有2条闭途径。

p3从左到右依次标记为a、b、c，从a点出发的闭途径：ababababcba 等共计15条，同样从c点出发也有15条的闭途径。从b点出发长为10的闭途径：bababababcb等共计30条。共有60条长为10的闭途径。

p4从左到右依次标记为a、b、c、d，从a点出发的闭途径：abababcdcba a等共计18條，同理从d出发也有18条长为10的闭途径。从b出发长为10的闭途径：babababcdcb等共计39条，同理从c出发也有39条长为10的闭途径。共有114条闭途径。 p5从左到右依次标记为a、b、c、d、e，从a点出发长为10的闭途径：ababcdedcba 等共计7条，同理从e出发也有7条长为10的闭途径。从b出发长为10的闭途径：bababcdedcb等共计15条，同理从d出发也有15条长为10的闭途径。从c出发重复ab和bc的分别有长为10的闭途径分别是：cbababcdedc 等2条和cbcbabcdedc等共计6条，同理重复cd和de的也分别有2种和6种，所有从c出发共有16条长为10的闭途径。所以共有60条长为10的闭途径。

p6从左到右依次标记为a、b、c、d、e、f，从a出发有1条长为10的闭途径abcdefedcba，同理从f出发也只有1条长为10的闭途径。从b出发有2条长为10的闭途径babcdefedcb等2条，同理从e出发也只有2条长为10的闭途径。从c出发有2条长为10的闭途径cbabcdefedc等，同理从d出发也只有2条长为10的闭途径。所以共有10条长为10的闭途径。

p51从左到右从上到下依次标记为a、b、c、d、e、f，从a出发有2条长为10的闭途径。从b出发长为10的闭途径babcdedfdcb等共计4条。从c出发长为10的闭途径cbabcdedfdc等共计4条。从d出发长为10的闭途径dcbabcdedfd等共计4条。从e出发有2条长为10的闭途径，同理从f出发也有2条长为10的闭途径，所以共有18条长为10的闭途径。

p41从左到右从上到下依次标记为a、b、c、d、e，从a出发长为10的闭途径：ababcdcecba 等共计14条，从b出发长为10的闭途径bababcdcecb等共计28条，从c出发长为10的闭途径：cdcdcecbabc等共计48条，从d出发长为10的閉途径：dcdcecbabcd等共计15条，同理从e出发有15条长为10的闭途径。所以共有120条长为10的闭途径。

k1，3的中心点标记为a，其它的点从左到右从上到下依次标记为b、c、d，因为k1，3是树图，每条边必须走两次，那么令边ab、ac、ad分别为BCD，从a出发的长为10的闭途径，相当于BCD分别重复3次3A55/A33=60，分别重复2次BBCCD BBCDD BCCDD 3A55/A22×A22=90种，所以从a出发有150条长为10的闭途径。从b出发首先第一条和最后一条为确定值，所以只需考虑剩下四条边，若除这两次以外不走，ab这条边则分为CCCD CDDD CCDD 3种情况2A44/2A33+ A44/A22×A22=10种，若重复ab分为BCCD BCDD BBCD 3A44/A22=36种，所以从b出发有46条长为10的闭途径。同理从c、e出发有46条长为10的闭途径。所以共有288条长为10的闭途径。

k1，4的中心点为a，同理命名bcde，因为k1，4是树图，每条边必须走两次，那么令边分别为BCDE从a点出发的长为10的闭途径为四种情况全排列，根据排列组合原理4A55/A22=120种，从b点出发的长为10的闭途径为BCDE全排列A44=24种，如果重复走的为CDE任意一条则为CCDE CDDE CDEE全排列36种。共60种同理从c、d、e出发也有60条长为10的闭途径，所以共有480条。

k1，5的中心点标记为a同理命名bcdef，因为k1，5是树图，每条边必须走两次，根据排列组合原理从a点出发的长为10的闭途径有C51×C41×C31×C21=120种，从b点出发同样根据排列组合原理有C41×C31×C21=24种，从c、d、e、f出发同样有24条，所以共有240条。

m1从左到右从上到下依次标记为a、b、c、d、e、f，从a出发长为10的闭途径：acbcdedfdca等共计4条。同理从b、e、f出发也有4条长为10的闭途径。从c出发12长为10的闭途径：cacbcdedfdc等共计12条，同理从d出发也有12条长为10的闭途径。所以共有40条。

m2同理标记为a、b、c、d、e、f，从a出发长为10的闭途径：abcdcecfcba等共计6条。从b出发0的闭途径：babcdcecfcb等共计12条，从c出发长的闭途径：cdcecfcbabc等共计24条，从d出发长为10的闭途径：dcecfcbabcd等共计6条，同理从e、f出发也有6条长为10的闭途径。所以共有60条。

m3同理标记为a、b、c、d、e，从a出发有2条长为10的闭途径，从b出发有2条长为10的闭途径，同理从f出发有2条长为10的闭途径。从c出发长为10的闭途径：cbcdefedadc等共计4条。同理从e出发有4条长为10的闭途径，从d出发长为10的闭途径：dcbcdadefed等共计6条，所以共有24条闭途径。

参考文献：

[1]West D B.图论导引：英文版[M].2版.北京：机械工业出版社，2004.

[2]Cvetkovíc D，Rowlinson P.Spectra of unicyclic graphs[J].Graph and Combinatorics，1987（3）：7-23.

[3]范琼，吴亚平.图的谱矩序列与图的排序[J].武汉大学学报：理学版，2009（6）：1-4.

[4]吴亚平，吕康南，付捷.树的谱矩研究.江汉大学学报（自然科学版），2012（6）

[5]Wu Y P，Liu H Q.Lexicographical ordering by spectral moments of trees with a prescribed diameter[J].Linear Algebra and Its Application，2010（11/12）：1707-1713.