趙寧 吳廷增 郭承志

【摘要】只有一個頂點(diǎn)度是大于2的一棵樹叫做似星樹，記作S=S（n1,n2,…，nΔ),S1=S(m1,m2,…,mΔ1-1）和S2=S(n1,n2,…,nΔ2-1)用一條路Pl把S1和S2的最大度點(diǎn)v,u連接起來得到的圖形稱為雙似星樹，記作G(l,S1,S2)。用η(G)表示圖G的零度（零度是指圖G的譜中零特征值的個數(shù)）。本文給出了似星樹和雙似星樹的一個零度算法，并證明了這是一個好算法。

【關(guān)鍵詞】似星樹；雙似星樹；零度；算法

【中圖分類號】O157。5【文獻(xiàn)標(biāo)識碼】A

【基金項(xiàng)目】青海省自然科學(xué)基金項(xiàng)目資助(No。2011-Z-911)。教育部“春暉計(jì)劃”項(xiàng)目資助(NO。Z20110。14)。

1幣 言

本文僅考慮簡單無向連通圖。文中未定義的術(shù)語和符號參見文獻(xiàn)［2］。令G=(V,E)表示一個圖，V(E)為頂點(diǎn)集，E(G)為邊集。令A(yù)(G)是圖G的鄰接矩陣，它的特征多項(xiàng)式記作φ(G,λ)。因?yàn)锳(G)是實(shí)對稱矩陣，所以它的特征根λi(G)(i=1,2，…，n)都是實(shí)數(shù)，可排序?yàn)椋害?(G)≥λ2(G)≥…≥λn(G)。n個特征根的重集稱為圖G的譜。把圖的譜中零特征值的個數(shù)稱為圖的零度，記為η(G)。令r(A(G))表示圖G對應(yīng)的鄰接矩陣A(G)的秩，則有η(G)=n-r(A(G))。圖的零度有很好的化學(xué)應(yīng)用背景，決定著化學(xué)分子的穩(wěn)定性，參見［1，4～6］。

設(shè)Pn表示含有n個頂點(diǎn)的路，把只有一個頂點(diǎ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的最大度頂點(diǎn)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）。特別地，我們可以認(rèn)為一條路是雙似星樹的最大度和次大度都等于2的特殊情形；同時似星樹可以看成是雙似星樹的最大度大于2，次大度等于2的特殊情形。

基于零度的化學(xué)背景和實(shí)際應(yīng)用的需要，許多研究人員希望給出一個有效的算法來計(jì)算圖的零度。但迄今為止，還沒有給出一個覆蓋所有圖的零度算法，有些文獻(xiàn)給出了一些特殊圖類的零度算法，如單圈圖等。本文中我們給出了似星樹和雙似星樹零度的有效好算法，并給出了相應(yīng)算法框。

2幣恍┮理

為了后面研究的需要，我們首先給出一些引理。

引理1 設(shè)G為任意一個圖，若G中含有一條懸掛邊，則刪除這兩個點(diǎn)后，零度不變。

引理2 設(shè)v是圖G的一個頂點(diǎn)，G′是把頂點(diǎn)v和Pm的懸掛點(diǎn)用一條邊連接起來所得的圖，如果m是偶數(shù)，則η(G)=η(G′)。

引理3 對于任意的路Pn，當(dāng)n是奇數(shù)時，r(Pn)=n-1，否則，r(Pn)=n,η(Pn)=0。

引理4 設(shè)圖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敝饕結(jié)果

為便于后面給出零度算法，下面我們給出基礎(chǔ)母圖定義。

定義1 設(shè)G是一棵雙似星樹，如果G的最大度和次大度d(u)=d(v)=2，則稱為T1；如果G的最大度大于2，次大度等于2，最大度頂點(diǎn)粘結(jié)有j條懸掛邊,則稱為T2；如果G的最大度和次大度都大于2，最大度頂點(diǎn)和次大度頂點(diǎn)各粘結(jié)了j1,j2條懸掛邊，則稱為T3。把T1，T2和T3稱為雙似星樹G的基礎(chǔ)母圖（見圖2）。