圖的兩類距離指標(biāo)的研究.pdf

1、圖論不變量，是從圖到實(shí)數(shù)集合的一個(gè)特殊映射，其需要滿足在圖同構(gòu)意義下的取值相等。其中基于頂點(diǎn)間距離的圖論不變量在生物、化學(xué)、物理領(lǐng)域都有著廣泛的實(shí)際應(yīng)用，同時(shí)作為一種拓?fù)渲笜?biāo)，這些圖論不變量的相關(guān)數(shù)學(xué)性質(zhì)也已經(jīng)得到學(xué)者們的廣泛關(guān)注。
　　圖論不變量的種類有很多，本文著重研究了其中兩類:離心距離指標(biāo)和度Kirchhoff指標(biāo)。離心距離指標(biāo)是Gupta、Singh和Madan在2002年為了更好地對(duì)化合物的化學(xué)物理性質(zhì)進(jìn)行合理預(yù)測(cè)而構(gòu)

2、造的一種基于頂點(diǎn)間距離的全新圖論不變量。對(duì)于任意簡(jiǎn)單連通圖G，定義圖G的離心距離指標(biāo)為:ξd(G)=∑u，v∈V(G）(εG(u)+εG(v))dG(u，v)，其中εG(u)和εG(v)表示頂點(diǎn)u和v在圖G中到其他頂點(diǎn)的最大距離，dG(u，v)表示在圖G中頂點(diǎn)u和v之間最短路的長(zhǎng)度。度Kirchhoff指標(biāo)是Chen和Zhang于2007年在對(duì)圖的阻尼距離進(jìn)行深入研究時(shí)所構(gòu)造的一種基于頂點(diǎn)間阻尼距離的圖論不變量。對(duì)于任意簡(jiǎn)單連通圖G，定

3、義圖G的度Kirchhoff指標(biāo)為:S'(G)=∑u，v∈V(G)dG(u)dG(v)RG(u，v),其中dG（u）和dG(v)分別表示頂點(diǎn)u和v在圖G中的度數(shù)，RG(u，v)表示在圖G中頂點(diǎn)u和v之間的阻尼距離。
　　本文主要是對(duì)這兩種圖論不變量在特殊圖下的極值進(jìn)行研究。對(duì)于任意簡(jiǎn)單連通圖G，令n:=|V(G)|，m:=|E(G)|。圖G為雙圈圖，當(dāng)且僅當(dāng)圖G滿足m=n+1;圖G為三圈圖，當(dāng)且僅當(dāng)圖G滿足m=n+2;圖G為仙人掌

4、圖，當(dāng)且僅當(dāng)圖G中的任意兩個(gè)圈之間至多存在一個(gè)公共頂點(diǎn)。這三類結(jié)構(gòu)特殊的圖在圖論中普遍存在，對(duì)其圖論不變量的研究具有非常重要的意義。
　　前人已經(jīng)對(duì)離心距離指標(biāo)和度Kirchhoff指標(biāo)在特殊圖下的數(shù)學(xué)性質(zhì)進(jìn)行了廣泛研究，并得到了大量相關(guān)結(jié)論。本文在前人的研究基礎(chǔ)上，結(jié)合雙圈圖、三圈圖和仙人掌圖的特殊圖型結(jié)構(gòu)，充分利用移邊變換，最終求解出具有最小離心距離指標(biāo)的雙圈圖、三圈圖和仙人掌圖;并對(duì)雙圈圖的最大和第二大度Kirchhoff指