似星樹和雙似星樹的零度算法似星樹和雙似星樹的零度算法

趙寧 吳廷增 郭承志

【摘要】只有一個頂點度是大于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）。