王力工 樊穩(wěn)茹，張 政,2

(1.西北工業(yè)大學(xué)應(yīng)用數(shù)學(xué)系，中國(guó) 西安 710072；2.西安航空技術(shù)高等?？茖W(xué)?；A(chǔ)部，中國(guó) 西安 710077)

設(shè)G是一個(gè)連通的簡(jiǎn)單圖，用V(G),E(G)分別表示圖的頂點(diǎn)集和邊集．圖G的頂點(diǎn)數(shù)即階數(shù)用n(G)表示．用d(v)表示圖G的一個(gè)頂點(diǎn)v的度數(shù).如果圖G的一個(gè)頂點(diǎn)v的度數(shù)d(v)=1，則稱頂點(diǎn)v為圖G的一個(gè)懸掛點(diǎn)．圖G的一個(gè)頂點(diǎn)v的距離是指圖G的頂點(diǎn)v到其他所有頂點(diǎn)的距離之和，用dG(v)表示．用G1∪G2表示兩個(gè)不相交的圖G1和G2的并圖．聯(lián)圖G1∨G2是指從并圖G1∪G2中連接圖G1的每個(gè)頂點(diǎn)和G2的每個(gè)頂點(diǎn)所得到的圖．n個(gè)頂點(diǎn)的路、圈和星圖分別用Pn,Cn和Sn表示．稱聯(lián)圖P1∨Pn為n+1階的扇形圖，記為Fn．稱聯(lián)圖P1∨(Pn1∪Pn2∪…∪Pnm)為n1+n2+…+nm+1階多扇圖，記為Fn1,n2,…,nm(見(jiàn)圖1)．設(shè)圖G是一個(gè)連通圖，用dG(u,v)表示圖G中頂點(diǎn)u和v的距離，即圖G中頂點(diǎn)u和v之間的最短路上的邊數(shù)．圖G的Wiener指數(shù)就是指圖G的任意兩點(diǎn)的距離之和，即

(1)

(1)中的Wiener指數(shù)W(G)一般應(yīng)用在化學(xué)中，它是化學(xué)圖論中最重要的拓?fù)渲笖?shù)之一．1947年物理化學(xué)家Harold Wiener[1]首次研究了無(wú)圈分子圖的Wiener指數(shù)，Hosoya在[2]中把Wiener指數(shù)定義為方程(1)的形式．Wiener指數(shù)自提出以后，便得到了廣泛的研究，一系列的結(jié)果相繼出現(xiàn)，有關(guān)結(jié)果參見(jiàn)文獻(xiàn)[3～13]．

本文我們考慮文獻(xiàn)[4]中提出的一個(gè)問(wèn)題：給定一個(gè)連通圖G,G中是否存在一棵子樹(shù)T，使得W(G)=W(T)？很明顯要求圖G含有圈，并且T不一定是G的生成樹(shù)．若存在圖G中一個(gè)子樹(shù)T，使得W(G)=W(T)，則稱T為G的一個(gè)保Wiener指數(shù)的樹(shù)．本文給出了多扇圖Fn1,n2,…,nm=P1∨(Pn1∪Pn2∪…∪Pnm)中具有無(wú)窮多的保Wiener指數(shù)的子樹(shù)，推廣了徐幼專、徐立新[9]的結(jié)果．

1 相關(guān)定義和引理

定義1[7]令樹(shù)T(n,k)表示一個(gè)具有n+k個(gè)頂點(diǎn)的似星圖,其中一個(gè)分支頂點(diǎn)的度為n-1，n-1個(gè)頂點(diǎn)的度為1及k個(gè)頂點(diǎn)的度為2,且分支頂點(diǎn)到每個(gè)1度頂點(diǎn)的距離為1或2,其中k≤n-1，即樹(shù)T(n,k)是在n階星圖Sn的k條邊上各插入一個(gè)頂點(diǎn)后所得到的圖(見(jiàn)圖2)．

圖1 n1+n2+…+nm+1階多扇圖Fn1,n2,…,nm 圖2 n+k階樹(shù)T(n,k)

引理2[9]m+1階扇形圖Fm的Wiener指數(shù)為：W(Fm)=m2-m+1．

引理3[9]樹(shù)T(n,k)的Wiener指數(shù)為：W(T(n,k))=n2+(3k-2)n+(2k2-5k+1)．

引理4[4]設(shè)G1和G2分別是階為n1和n2的任意兩個(gè)圖，v1∈V(G1)，v2∈V(G2)，圖G是將圖G1的頂點(diǎn)v1和圖G2的頂點(diǎn)v2重疊后得到的圖，則圖G的Wiener指數(shù)為：

W(G)=W(G1)+W(G2)+(n1-1)dG2(v2)+(n2-1)dG1(v1).

2 主要結(jié)果

在這一節(jié)里，我們給出了多扇圖Fn1,n2,…,nm的Wiener指數(shù)，并證明了多扇圖中具有無(wú)窮多個(gè)保Wiener指數(shù)的子樹(shù)T(l,k)．

定理1設(shè)n1+n2+…+nm=p，則p+1階多扇圖Fn1,n2,…,nm的Wiener指數(shù)為：

(2)

證對(duì)m用數(shù)學(xué)歸納法，由引理2和引理4即可證明．

定理2設(shè)p=n1+n2+…+nm.當(dāng)下面兩個(gè)條件中的一個(gè)成立時(shí)，多扇圖Fn1,n2,…,nm有保Wiener指數(shù)的子樹(shù)T(l,k)，這里k≤l-1,l+k≤p+1．

(2)p=(t2+5t+m-b2+b+2)/(2b)，l=(t2+5t+m+b2-b-6bt+2)/(2b),k=2t+1，其中b和m均為正整數(shù)，t是非負(fù)整數(shù)，且b|(t2+5t+m+2)．

證假設(shè)W(Fn1,n2,…,nk+1)=W(T(l,k))，且知n1+n2+…+nm=p，由引理3和定理1可得：

p2-p+m=l2+(3k-2)l+(2k2-5k+1)．

上式兩邊乘4，配方得：

(2l+3k-2)2-(2p-1)2=k2+8k+4m-1．

令x=2l+3k-2，y=2p-1，則有

x2-y2=k2+8k+4m-1．

由不定方程知識(shí)可知，上述不定方程有解當(dāng)且僅當(dāng)k2+8k+4m-1為奇數(shù)或者4的倍數(shù)．因此我們討論下面兩種情況：

基于上述分析，可明確實(shí)現(xiàn)地理信息生成與地圖制圖一體化概念模型的步驟：（1）強(qiáng)化制圖數(shù)據(jù)內(nèi)部的數(shù)據(jù)質(zhì)量，面向制圖與空間數(shù)據(jù)建立起共同的數(shù)據(jù)標(biāo)準(zhǔn)；（2）數(shù)據(jù)生產(chǎn)平臺(tái)的建立應(yīng)以符號(hào)化為基礎(chǔ)；（3）數(shù)據(jù)管理與生產(chǎn)流程均需與生產(chǎn)目標(biāo)相適應(yīng)。

(1)當(dāng)k=2t為偶數(shù)時(shí)，

(x+y)(x-y)=4t2+16t+4m-1．

因x+y和x-y均為奇數(shù)，令x-y=2a-1，這里a為正整數(shù)，當(dāng)(4t2+16t+4m-1)/(2a-1)是奇數(shù)時(shí)，可取

解得：

當(dāng)(4t2+16t+4m-1)/(2a-1)是奇數(shù)時(shí)，則

多扇圖Fn1,n2,…,nm有保Wiener指數(shù)的子樹(shù)T(l,k)，這里p=n1+n2+…+nm，且對(duì)任意的正整數(shù)t，均有2t=k≤l-1,l+k≤p+1．

(2)當(dāng)k=2t+1為奇數(shù)時(shí)，x+y和x-y均為偶數(shù)，則

(x+y)(x-y)=4t2+20t+4m+8．

令x-y=2b，這里b為正整數(shù)，當(dāng)b|(t2+5t+m+2)時(shí)，可?。?/p>

解得：

故多扇圖Fn1,n2,…,nm有保Wiener指數(shù)的子樹(shù)T(l,k)，這里p=n1+n2+…+nm，其中b和m均為正整數(shù)，t是非負(fù)整數(shù)，顯然對(duì)任意的非負(fù)整數(shù)t，均有2t+1=k≤l-1,l+k≤p+1．

推論1設(shè)p=n1+n2+…+nm，當(dāng)下面3個(gè)條件中的一個(gè)成立時(shí)，多扇圖Fn1,n2,…,nm有保Wiener指數(shù)的子樹(shù)T(l,k)，這里均有k≤l-1,l+k≤p+1．

(1)p=t2+4t+m,l=t2+t+m+1,k=2t，其中m和t均為正整數(shù)．

證由定理2，分別取a=1,b=1和b=2，即可證得此推論的(1)、(2)和(3)．

推論2[9]當(dāng)p=t2+4t+1,l=t2+t+2,k=2t時(shí)，其中t為任意一個(gè)正整數(shù)，扇形圖Fp有保Wiener指數(shù)的子樹(shù)T(l,k)，這里k≤l-1,l+k≤p+1．

注記1從定理2可知，在多扇圖Fn1,n2,…,nm中存在無(wú)窮多的保Wiener指數(shù)的子樹(shù)T(l,k)．

參考文獻(xiàn)：

[1] WIENER H. Structural determination of paraffin boiling points[J]. J Am Chem Soc, 1947，69(1)： 17-20.

[2] HOSOYA H. Topological index, a newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons[J]. Bull Chem Soc Jpn, 1971,44(9): 2332-2339.

[3] DOBRYNIN A. Branchings in trees and calculation of the Wiener index of a tree[J]. MATCH Commun Math Comput Chem, 2000, 41: 119-134.

[4] DOBRYNIN A, ENTRINGER R, GUTMAN I. Wiener index of trees: theory and applications[J]. Acta Appl Math, 2001，66(3): 211-249.

[5] DOBRYNIN A, GUTMAN I, KLAV?AR S，etal. Wiener index of hexagonal systems[J]. Acta Appl Math, 2002，72(3): 247-294.

[7] 鄧漢元,王紅專. 輪形圖中保Wiener 指數(shù)的樹(shù)[J]. 湖南師范大學(xué)自然科學(xué)學(xué)報(bào), 2005, 28(4): 1-4.

[8] 刑抱花，潘向峰.某類聯(lián)圖中保Wiener指數(shù)的樹(shù)[J]. 安慶師范學(xué)院學(xué)報(bào)：自然科學(xué)版，2008, 14(1): 3-5.

[9] 徐幼專，徐立新. 扇形圖P1∨Pm中保Wiener指數(shù)的樹(shù)[J]. 鄭州大學(xué)學(xué)報(bào)：理學(xué)版， 2006, 38(3): 32-34.

[10] 陳升平.由C6覆蓋的環(huán)狀纖維管的Wiener指數(shù)[J].湖南師范大學(xué)自然科學(xué)學(xué)報(bào)，2006， 29(3):32-35.

[11] 鄧漢元.一類化學(xué)圖及其線圖的Wiener指數(shù)(英文稿)[J].湖南師范大學(xué)自然科學(xué)學(xué)報(bào)，2009， 32(3):23-26.

[12] 高 云，王力工.兩類聯(lián)圖中保Wiener指數(shù)的樹(shù)[J].紡織高校基礎(chǔ)科學(xué)學(xué)報(bào)，2010, 23(4):468-472.

[13] 楊 光,劉淑芳.聯(lián)圖Pm∨P2k-1中保Wiener指數(shù)的樹(shù)[J].河北北方學(xué)院學(xué)報(bào)：自然科學(xué)版，2010， 26(4):1-3,7.