劉晚喬,趙 飚

(1.中國國際航空股份有限公司新疆分公司,新疆 烏魯木齊 830026)(2.新疆大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院,新疆 烏魯木齊 830046)

對于分子的描述,在化學(xué)、物理和藥理學(xué)等方面起著重要的作用[1]. 其中,一個(gè)能描述分子圖的一些性質(zhì)的數(shù)被稱為拓?fù)渲笜?biāo),對于分子圖的拓?fù)渲笜?biāo)能反應(yīng)分子的一些物理和化學(xué)性質(zhì),所以通過計(jì)算分子圖的某種拓?fù)渲笜?biāo)的數(shù)值,可以統(tǒng)計(jì)出分子的某些物理化學(xué)性質(zhì). 特別是在 QSPR/QSAR 研究中,發(fā)現(xiàn)了許多拓?fù)渲笜?biāo)在化學(xué)中應(yīng)用廣泛[2-5].

設(shè)G是一個(gè)簡單圖,對于沒有說明的術(shù)語和概念可參考文獻(xiàn)[6-7].記圖G的點(diǎn)集為V(G),邊集為E(G),dG(u)(dG(v))為圖G中點(diǎn)u(v)的度數(shù).則圖G的GA指標(biāo)定義如下[8-9]:

令e=uv是圖G的一條邊,連接點(diǎn)uv,則定義:

N(e,u,G)={x∈V(G)|dG(x,u)

N(e,v,G)={x∈V(G)|dG(x,u)>dG(x,v)},

u的鄰點(diǎn)記為NG(u),v的鄰點(diǎn)記為NG(v)[10].同時(shí)

nu(e)=nu(e,G)=|N(e,u,G)|,

nv(e)=nv(e,G)=|N(e,v,G)|,

式中,n(u)表示圖G中的點(diǎn)到頂點(diǎn)u的距離小于到頂點(diǎn)v的距離的數(shù)目,n(v)同理.

2010年,文[11]定義了第二類拓?fù)渲笜?biāo)GA2指標(biāo),定義如下:

同時(shí),確定了完全圖中的GA2指標(biāo)上下界,以及樹圖中具有最小和最大GA2指標(biāo)的樹圖,分別是星圖和路.Tang等[12]在2011年巧妙采用了圖變換的方法,進(jìn)一步確定了樹圖中具有GA2指標(biāo)第二大及第二小的圖,同時(shí)得出了具有最大GA2指標(biāo)和最小GA2指標(biāo)的單圈圖.本文主要描述了在n個(gè)頂點(diǎn)的雙圈圖中,利用圖形的變換,進(jìn)而確定具有最小GA2指標(biāo)的圖.

1 引理

圖G是一個(gè)連通雙圈圖,且有n個(gè)頂點(diǎn),n+1 條邊,下面將雙圈圖進(jìn)行了3種分類:

(1)當(dāng)n≥5時(shí),圈Cm,Cp共享一個(gè)公共點(diǎn),見圖(a).

(2)當(dāng)n≥6時(shí),圈Cm,Cp中間連接一條長度大于等于1的路,見圖(b).

(3)當(dāng)n≥4時(shí),3條內(nèi)部不相交的路P1,P2和P3具有公共的端點(diǎn)u,v,見圖(c).

令G=(V,E)是一個(gè)雙圈圖,其中圈Cm和圈Cp的長度分別為q和p,且T1,T2,…,Tk(0≤k≤p+m)表示圈上懸掛的樹,T1,T2,…,Tk為G-E(Cm,Cp)的非平凡分支.令N(Ti)=li,i=1,2,…,k,且l=l1+l2+…+lk=n-p-q+1,其中N(Ti)表示為樹Ti點(diǎn)的個(gè)數(shù),記雙圈圖為G=CG(T1,T2,…,Tk),則有下面的引理.

圖1 雙圈圖主要分類

引理1若圖G是一個(gè)有n個(gè)頂點(diǎn),且n≥4的雙圈圖,則

G1=CG(S1,S2,…,Sk),

G2=CG(P1,P2,…,Pk),

雙圈圖G1中,u1,u2,…,uk是圈Cm,Cp上的點(diǎn),且S1,S2,…,Sk是點(diǎn)u1,u2,…,uk的懸掛邊.

雙圈圖G2中,u1,u2,…,uk是圈Cm,Cp上的點(diǎn),且P1,P2,…,Pk是點(diǎn)u1,u2,…,uk的懸掛路,

則可以得到

GA2(G1)≤GA2(G)≤GA2(G2),

式中,G=CG(T1,T2,…,Tk),N(Ti)=li(i=1,2,…,k).

為了找到雙圈圖中具有最小GA2指標(biāo)的圖,只需要考慮有懸掛邊的雙圈圖.

2 結(jié)果與分析

圖2 圖G1變換到圖Gi

證明將E(G1)里的邊分成七部分,其表示為:

(1)E1={e=uv∈Gi|degGi(v)=1,degGi(u)≥3};

(2)E2={e=uv∈Cp|d(u,u1)

(3)E3={e=uv∈Cp|d(u,u1)>d(v,u1),d(u,ui)>d(v,ui)};

(4)E4={e=uv∈Cp|d(u,u1)d(v,ui)};

(5)E5={e=uv∈Cp|d(u,u1)>d(v,u1),d(u,ui)

(6)E6={e=uv∈Cp|d(u,u1)>d(v,u1),d(u,ui)=d(v,ui),d(u,u1)=d(v,u1),d(u,ui)>d(v,ui)};

(7)E7={e=uv∈Cp|d(u,u1)

根據(jù)GA2的定義,可以得到

(1)

當(dāng)邊uv∈E4時(shí)

所以,當(dāng)邊e∈E4,可以得到,

(2)

同樣對于邊uv∈E5可以得到在圖Gi中,

當(dāng)邊e∈E5,則有

(3)

對于連通圖Gi,單圈圖Cp的圈長p為奇數(shù)時(shí),所有的邊e∈Ej(1≤j≤5).由式(1-3)可得,

GA2(G1)≥GA2(Gi).

當(dāng)圈Cp的長度為偶數(shù)時(shí),接下來考慮,當(dāng)邊uv∈E6時(shí),則有

所以,當(dāng)邊e∈E6,則有

(4)

當(dāng)邊uv∈E7時(shí),則有

所以,當(dāng)邊e∈E7,則有

(5)

由式(1)-(5)可得

由圖G1轉(zhuǎn)換的圖Gi可以得到GA2(G1)≥GA2(Gi).

圖3 圖

圖4 雙圈圖類型Ⅰ圖

通過計(jì)算:

式中,t=[p/2],k=p-2t,d=n-q-p+1.

當(dāng)p=2t(t≥2) 時(shí),

(6)

當(dāng)p=2t+1 (t≥1) 時(shí),

(7)

當(dāng)p=4和p=3時(shí)

(8)

2.1 雙圈圖類型I

2.2 雙圈圖類型Ⅱ

圖5 圖變換到圖

圖6 圖變換到圖

即

(9)

(10)

則

式中,S=d1+d2+l+t.

2.3 雙圈圖類型Ⅲ

圖7 雙圈圖類型Ⅲ 圖

3 結(jié)論