乘積圖生成樹的Wiener數(shù)問題.pdf

1、美國物理化學(xué)家HaroldWiener在[1]中最早提出Wiener數(shù)(在他的文獻(xiàn)中稱為pathnumber)。Wiener構(gòu)造Wiener數(shù)的初衷是用于處理無環(huán)的有機(jī)分子結(jié)構(gòu)(用圖論的語言，這種無環(huán)的有機(jī)分子結(jié)構(gòu)圖就是樹)問題，其原始的定義為W=∑ef(e)，其中和式取遍圖中的每一條邊e,f(e)表示將無環(huán)分子圖的邊e刪除后的兩個(gè)連通分支的頂點(diǎn)數(shù)之積。對(duì)于一棵樹T而言，其Wiener數(shù)也可等價(jià)的定義為任意兩點(diǎn)的距離之和，即W(T)=∑

2、{u,v}()V(T)dT(u，v)。這一定義后來被數(shù)學(xué)家及化學(xué)家推廣到一般的連通圖。 本文研究如下問題：給定一個(gè)連通圖，如何確定其Wiener數(shù)最小的生成樹?這是Wiener數(shù)研究中的主要問題之一。這一問題不僅對(duì)于Wiener數(shù)的研究有著重要的理論和實(shí)際意義，同時(shí)也具有其它的一些實(shí)際背景(如經(jīng)濟(jì)網(wǎng)絡(luò)的設(shè)計(jì)等[9])。一般而言，這一問題具有相當(dāng)?shù)碾y度，即使是對(duì)于一些很特殊的圖類如超立方體，也還是一個(gè)尚未解決的問題。事實(shí)上，Dob

3、rynin在[9]中構(gòu)造了超立方體的兩類Wiener數(shù)“很小”的生成樹，并進(jìn)一步猜想這兩類樹都是Wiener數(shù)最小的生成樹。利用歸納推理及遞歸關(guān)系，本文對(duì)更一般的且具有良好拓?fù)湫再|(zhì)和較高的網(wǎng)絡(luò)模型應(yīng)用價(jià)值的乘積圖，如G1×G2、Kmn、Cmn等，構(gòu)造了相應(yīng)的生成樹并計(jì)算了它們的Wiener數(shù)的值，以期獲得這些乘積圖Wiener數(shù)最小的生成樹。這些結(jié)果推廣了Dobrynin關(guān)于超立方體的結(jié)果。文章的最后，我們分析了Kmn、Cmn的漸進(jìn)性質(zhì)