似星树和双似星树的零度算法似星树和双似星树的零度算法

赵宁 吴廷增 郭承志

【摘要】只有一个顶点度是大于2的一棵树叫做似星树，记作S=S（n1,n2,…，nΔ),S1=S(m1,m2,…,mΔ1-1）和S2=S(n1,n2,…,nΔ2-1)用一条路Pl把S1和S2的最大度点v,u连接起来得到的图形称为双似星树，记作G(l,S1,S2)。用η(G)表示图G的零度（零度是指图G的谱中零特征值的个数）。本文给出了似星树和双似星树的一个零度算法，并证明了这是一个好算法。

【关键词】似星树；双似星树；零度；算法

【中图分类号】O157。5【文献标识码】A

【基金项目】青海省自然科学基金项目资助(No。2011-Z-911)。教育部“春晖计划”项目资助(NO。Z20110。14)。

1币 言

本文仅考虑简单无向连通图。文中未定义的术语和符号参见文献［2］。令G=(V,E)表示一个图，V(E)为顶点集，E(G)为边集。令A(G)是图G的邻接矩阵，它的特征多项式记作φ(G,λ)。因为A(G)是实对称矩阵，所以它的特征根λi(G)(i=1,2，…，n)都是实数，可排序为：λ1(G)≥λ2(G)≥…≥λn(G)。n个特征根的重集称为图G的谱。把图的谱中零特征值的个数称为图的零度，记为η(G)。令r(A(G))表示图G对应的邻接矩阵A(G)的秩，则有η(G)=n-r(A(G))。图的零度有很好的化学应用背景，决定着化学分子的稳定性，参见［1，4～6］。

设Pn表示含有n个顶点的路，把只有一个顶点度是大于2的一棵树叫做似星树,如果用S=S(n1,n2,…,nΔ)表示似星树，那么有S=S(n1,n2,…,nΔ)-v=Pn1∪Pn2∪…∪PnΔ。这里d(v)=Δ,n1+n2+…+nΔ+1=n。将两棵似星树S1=S(m1,m2,…,mΔ1-1）和S2=S(n1,n2,…,nΔ2-1）用一条长为l的路Pl把S1和S2的最大度顶点u，v连接起来得到的图称为双似星树，记作G(l,S1,S2),对于任意的G(l,S1,S2)有：

G(l,S1,S2)-u-v=Pl-2∪Pm1∪Pm2∪…∪PmΔ1-1∪Pn1∪Pn2∪…∪PnΔ2-1。

这里d(u)=Δ1,d(v)=Δ2,l+m1+…+n1+…+nΔ2-1=n（见图1）。特别地，我们可以认为一条路是双似星树的最大度和次大度都等于2的特殊情形；同时似星树可以看成是双似星树的最大度大于2，次大度等于2的特殊情形。

基于零度的化学背景和实际应用的需要，许多研究人员希望给出一个有效的算法来计算图的零度。……