似星树和双似星树的零度算法似星树和双似星树的零度算法
开篇：润墨网以专业的文秘视角，为您筛选了一篇似星树和双似星树的零度算法似星树和双似星树的零度算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
【摘要】只有一个顶点度是大于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）。