基于雙圈圖GA2指標的分析

劉晚喬,趙 飚

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

對于分子的描述,在化學、物理和藥理學等方面起著重要的作用[1]. 其中,一個能描述分子圖的一些性質的數被稱為拓撲指標,對于分子圖的拓撲指標能反應分子的一些物理和化學性質,所以通過計算分子圖的某種拓撲指標的數值,可以統計出分子的某些物理化學性質. 特別是在 QSPR/QSAR 研究中,發現了許多拓撲指標在化學中應用廣泛[2-5].

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

令e=uv是圖G的一條邊,連接點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的鄰點記為NG(u),v的鄰點記為NG(v)[10].同時

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

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

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

2010年,文[11]定義了第二類拓撲指標GA2指標,定義如下:

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

1 引理

圖G是一個連通雙圈圖,且有n個頂點,n+1 條邊,下面將雙圈圖進行了3種分類:

(1)當n≥5時,圈Cm,Cp共享一個公共點,見圖(a).

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

(3)當n≥4時,3條內部不相交的路P1,P2和P3具有公共的端點u,v,見圖(c).

令G=(V,E)是一個雙圈圖,其中圈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點的個數,記雙圈圖為G=CG(T1,T2,…,Tk),則有下面的引理.

圖1 雙圈圖主要分類

引理1若圖G是一個有n個頂點,且n≥4的雙圈圖,則

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

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

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

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

則可以得到

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

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

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

2 結果與分析

圖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)

根據GA2的定義,可以得到

(1)

當邊uv∈E4時

所以,當邊e∈E4,可以得到,

(2)

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

當邊e∈E5,則有

(3)

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

GA2(G1)≥GA2(Gi).

當圈Cp的長度為偶數時,接下來考慮,當邊uv∈E6時,則有

所以,當邊e∈E6,則有

(4)

當邊uv∈E7時,則有

所以,當邊e∈E7,則有

(5)

由式(1)-(5)可得

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

圖3 圖

圖4 雙圈圖類型Ⅰ圖

通過計算:

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

當p=2t(t≥2) 時,

(6)

當p=2t+1 (t≥1) 時,

(7)

當p=4和p=3時

(8)

2.1 雙圈圖類型I

2.2 雙圈圖類型Ⅱ

圖5 圖變換到圖

圖6 圖變換到圖

即

(9)

(10)

則

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

2.3 雙圈圖類型Ⅲ

圖7 雙圈圖類型Ⅲ 圖

3 結論