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

赵宁 吴廷增 郭承志

【摘要】只有一个顶点度是大于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的特殊情形。

基于零度的化学背景和实际应用的需要，许多研究人员希望给出一个有效的算法来计算图的零度。但迄今为止，还没有给出一个覆盖所有图的零度算法，有些文献给出了一些特殊图类的零度算法，如单圈图等。本文中我们给出了似星树和双似星树零度的有效好算法，并给出了相应算法框。

2币恍┮理

为了后面研究的需要，我们首先给出一些引理。

引理1 设G为任意一个图，若G中含有一条悬挂边，则删除这两个点后，零度不变。

引理2 设v是图G的一个顶点，G′是把顶点v和Pm的悬挂点用一条边连接起来所得的图，如果m是偶数，则η(G)=η(G′)。

引理3 对于任意的路Pn，当n是奇数时，r(Pn)=n-1，否则，r(Pn)=n,η(Pn)=0。

引理4 设图G(n1,n2,…，nΔ)是一棵似星树且G(n1,n2,…，nΔ)-v=Pn1∪Pn2∪…∪PnΔ,其中d(v)=Δ，n1+n2+…+nΔ+1=n,如果Pn1,Pn2，…，PnΔ中有p条偶路，q(q≥1)条奇路，p+q=Δ，则η(G)=q-1；若Pn1,Pn2，…，PnΔ中都是偶路，则η(G)=1。

引理5 令G=G1∪G2∪…∪Gt,这里G1,G2，…,Gt表示图G的连通分支，则η(G)=∑ti=1η(Gi)。

3敝饕结果

为便于后面给出零度算法，下面我们给出基础母图定义。

定义1 设G是一棵双似星树，如果G的最大度和次大度d(u)=d(v)=2，则称为T1；如果G的最大度大于2，次大度等于2，最大度顶点粘结有j条悬挂边,则称为T2；如果G的最大度和次大度都大于2，最大度顶点和次大度顶点各粘结了j1,j2条悬挂边，则称为T3。把T1，T2和T3称为双似星树G的基础母图（见图2）。