汪小黎，王 曉

(商洛學(xué)院 數(shù)學(xué)與計(jì)算科學(xué)系,陜西商洛 726000)

1引言及引用定理

本文所研究的圖均為有限、無向、簡單圖。設(shè)G=(V(G),E(G))表示一個(gè)圖，V(G)和 E(G)分別表示圖G的頂點(diǎn)集和邊集。圖Pn表示n個(gè)頂點(diǎn)的路，圖Cn表示n個(gè)頂點(diǎn)的圈，聯(lián)圖G1∨G2表示用G1中的每一個(gè)頂點(diǎn)連結(jié)G2中所有頂點(diǎn)且G1和G2各自的邊保持不變所得到的圖。聯(lián)圖K1∨Cn稱為輪形圖，聯(lián)圖K1∨Pn稱為扇形圖。其它涉及到的概念和定義可參見文獻(xiàn)[1]。

Randic[2]在1979年提出圖 G的解析（Dissection）的這一圖的化學(xué)指標(biāo)的概念，可以用來描述有機(jī)物的分子結(jié)構(gòu)，和其他化學(xué)指標(biāo)有著密切的聯(lián)系[3-4]。它是一個(gè)關(guān)于圖G的二元向量(a,b)，記圖G的解析為 D(G)=(a(G),b(G))，在文獻(xiàn)[3,5]中有如下遞歸定義：

1)若 G=K1，則 D(G)=(1,0)；

2)若 G=K2,則 D(G)=(1,0)；

由此遞歸定義，在文獻(xiàn)[6]中，有如下關(guān)于圖的解析的另一種計(jì)算方法。

設(shè)G為一個(gè)至少有三個(gè)頂點(diǎn)的連通圖，V(G)={v1,v2,…,vn}，對于給定 v∈V(G)，在 V(G){v}中的頂點(diǎn)序列vi1vi2…vik若滿足

1)在G-vi1-vi2-…-vik-1中包含v的連通分支至少有三個(gè)頂點(diǎn)；

2)在G-vi1-vi2-…-vik中v是孤立點(diǎn)；

3)對每個(gè) j∈(2,3,…,k)，v 和 vij都在 G-vi1-vi2-…-vij-1的同一個(gè)連通分支中。則稱序列vi1vi2…vik為相對于頂點(diǎn)v的一個(gè)鏈。圖G中相對于v的鏈的數(shù)目記為a(G,v)。

對于給定邊 e=vivj∈E(G)，在 V(G){vi,vj}中的頂點(diǎn)序列vi1vi2…vik滿足

1)在G-vi1-vi2-…-vik-1中包含e的連通分支至少有三個(gè)頂點(diǎn)；

2)在G-vi1-vi2-…-vik中e是孤立邊；

3)對每個(gè) j∈(2,3,…,k)，e 和 vij都在 G-vi1-vi2-…-vij-1的同一個(gè)連通分支中。則稱序列vi1vi2…vik為相對于邊e的一個(gè)鏈。圖G中相對于e的鏈的數(shù)目記為b(G,e)。

定理1[6]設(shè)G是一個(gè)至少有4個(gè)頂點(diǎn)的連通圖，則有

在文獻(xiàn)[5]中給出一些關(guān)于圖的解析的基本性質(zhì)，并給出一些常見圖的解析值。

命題1[5]設(shè)n為一個(gè)正整數(shù)，則有

在文獻(xiàn)[7]中給出樹圖的解析的上下界，圖的解析的性質(zhì)研究參見文獻(xiàn)[5,8]。由其定義，可知道圖的解析的計(jì)算是一個(gè)NP問題，本文結(jié)合圖的解析兩種計(jì)算方法，給出輪形圖（圖1）和扇形圖（圖2）的解析值。

2 主要結(jié)論

定理2設(shè)圖G為輪形圖K1∨Cn，n≥5,則有

當(dāng) n=3，4 時(shí)，易計(jì)算得 D(K1∨C3)=D(K4)=(0,12)，D(K1∨C4)=(24,48)；D(K1∨P3)=(4,10)。

3定理的證明

3.1 定理2的證明

首先利用定理1來計(jì)算a(G)。如圖1，輪形圖G的中心點(diǎn)v0與圈中所有點(diǎn)都相連，所以去掉圈上的點(diǎn)，最后包含v0的子圖要么是C3要么是P3（此時(shí)v0為中間頂點(diǎn)），所以相對于中心點(diǎn)v0的鏈的數(shù)目a(G,v0)。由對稱性，圈上所有頂點(diǎn)的鏈的數(shù)目都相等?，F(xiàn)取v為圈上一個(gè)頂點(diǎn)，設(shè)在關(guān)于頂點(diǎn)v的鏈中v0排在第m位，由于頂點(diǎn)v的每一個(gè)鏈必含有v0，故現(xiàn)對m進(jìn)行分類來計(jì)算G中相對于v的鏈的數(shù)目。

1)m=1中心點(diǎn)v0在鏈的第一位，即首先去掉v0剩余是Cn。在Cn中相對于每個(gè)點(diǎn)的鏈數(shù)目是相等的，由命題 1，得所以m=1時(shí)，G中相對于v的鏈的數(shù)目為2×3n-4。

2)m=2中心點(diǎn)v0在鏈的第2位，即先去掉圈中除v外的一個(gè)頂點(diǎn)，再去掉中心點(diǎn)v0時(shí)，得到含v的一條路Pn-1。當(dāng)鏈中第一個(gè)頂點(diǎn)取V(Cn){v}中不同點(diǎn)時(shí)，可得到頂點(diǎn)v位于長度為n-1的所有不同位置的路Pn-1由命題1，得中心點(diǎn)v0在第2位的鏈的數(shù)目為a(Pn-1)=2×3n-4。

3)3≤m≤n-2,中心點(diǎn)v0在鏈的第m位，即前面已去掉圈中的m-1個(gè)點(diǎn)。當(dāng)這個(gè)m-1頂點(diǎn)的導(dǎo)出子圖是一條路（也即這m-1個(gè)頂點(diǎn)在Cn中按一定次序依次相連）時(shí)，去掉中心點(diǎn)v0后，剩余的子圖為包含v的路Pn-m+1。而且這相鄰的

4)m=n-1中心點(diǎn)v0在鏈的第n-1位，即前面已去掉Cn中的n-2個(gè)頂點(diǎn)，剩余子圖要么為含v和v0的C3要么是含v和v0的P3。當(dāng)是C3時(shí)，由D(C3)=(0,3)，故這樣的鏈的數(shù)目為0；當(dāng)是P3時(shí)，與v0關(guān)聯(lián)的另外一個(gè)頂點(diǎn)是在除了頂點(diǎn)v在圈上的兩個(gè)臨點(diǎn)外的頂點(diǎn)，故這樣的鏈的數(shù)目為(n-2)!(n-3)。

5)m=n按這樣的頂點(diǎn)序列順序去掉頂點(diǎn)，最后剩余的子圖為含v的一條邊，故對a(G,v)的貢獻(xiàn)為零。

對于b(G)，應(yīng)用定理1，將輪形圖G的邊分為兩類 E1和E2，其中 E1={vivo|i=1,2,…,n}，E2={vivj|vivj∈E(G),i,j=1,2,…,n}。若 e∈E1，則圖G中相對于邊e的鏈?zhǔn)怯沙ミ卐的兩個(gè)端點(diǎn)，剩余n-1個(gè)頂點(diǎn)的任意排列，即b(G,e)=(n-1)!。若e∈E2，類似計(jì)算a(G)的分析，同理得到

至此定理2得證。

3.2 定理3的證明

[1]BONDY J A,MURTY U S R.Graph theory with applications[M].Macmillan,London and Elsevier,New York,1976.

[2]RANDIC M.On dissection of acyclic graphs[J].MATCH Commun Math Comput Chem,1979,5:135-148.

[3]RANDIC M,GUO X F,CALKINS P.Graph dissetion revisited:application to smaller alikanes[J].Acta Chim Slov,2000,47:489-506.

[4]RANDIC M,WOODWORTH W L.Characterization of acyclic graphs by successive dissection[J].MATCH Commun Math Comput Chem,1982,13:291-313.

[5]XU Z X,WU B,GUO X F.On dissection of graphs[J].MATCH Commun Math Comput Chem,2006,56:519-526.

[6]段 芳,王 曉.A New method in computing the dissection of some graphs[J].新疆大學(xué)學(xué)報(bào):自然科學(xué)版，2008，25(3)：293-297.

[7]王 曉,段 芳.On dissection of unicyclic graphs[J].華東師范大學(xué)學(xué)報(bào),2009,1(143):13-21.

[8]張 莉.樹的剖分值[J].應(yīng)用數(shù)學(xué)學(xué)報(bào),2008(31):852-860.