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

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

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

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