摘 要：本文對(duì)水路運(yùn)輸、交通運(yùn)輸中的賦權(quán)圖定義了對(duì)應(yīng)的拓?fù)淇臻g，并討論了相關(guān)的拓?fù)湫再|(zhì)，證明了此類空間具有的強(qiáng)分離性質(zhì)及緊性. 對(duì)傳統(tǒng)的Dijkstra方法進(jìn)行改進(jìn)，為最優(yōu)化運(yùn)輸方案提出了一種算法，使得這種算法更容易理解和計(jì)算.

關(guān)鍵詞：賦權(quán)圖；拓?fù)淇臻g；拓?fù)洳蛔冃?；最短通?/p>

Abstract：A topology space for evaluation graph is defined in the paper， some properties with respect to the space is given such as compact， Hausdorff， regular， normality. Dijsktra method to calculate the shortest route of evaluation has been improved.

Key words：evaluation graph； topology space； invariant； shortest route

在水路運(yùn)輸、公路交通網(wǎng)絡(luò)、物流調(diào)配中，經(jīng)常要研究賦權(quán)圖，以確定最優(yōu)運(yùn)輸方案。本文假定所討論的賦權(quán)圖均是連通的。

設(shè)G=為賦權(quán)圖，其中V={v1，v2，…，vn}為頂點(diǎn)集，E={e1，e2，…，em}是關(guān)聯(lián)于各對(duì)頂點(diǎn)的邊的集合，W（ei）>0表示邊ei的權(quán). 兩頂點(diǎn)vi與vj之間的距離d（vi，vj）是指從vi到vj的最短通路的長(zhǎng)度.

定理1 設(shè)G=是賦權(quán)圖，V={v1，v2，…，vn}是頂點(diǎn)集，則V關(guān)于兩點(diǎn)間的距離d是一個(gè)度量空間.

證 容易驗(yàn)證在V中，度量的三公理成立。

事實(shí)上，首先由距離的定義可知，對(duì)任意的vi，vj∈V，有d（vi，vj）≥0，并且由每個(gè)頂點(diǎn)到自身的最短通路的長(zhǎng)度顯然為0，即d（vk，vk）=0. 反之，若有兩個(gè)頂點(diǎn)vi，vj∈V，使得d（vi，vj）=0， 則因?yàn)槊織l邊的權(quán)為正數(shù)，因此若vi≠vj， 必有 d（vi，vj）>0，于是由d（vi，vj）=0可得vi=vj.

其次根據(jù)距離的定義自然有d（vi，vj）=d（vj，vi）.

最后，假定有vi，vj，vk∈V，使得

d（vi，vj）>d（vi，vk）+d（vk，vj）

則說(shuō)明在賦權(quán)圖中存在一條經(jīng)過(guò)頂點(diǎn)vk的從vi到vj的通路，其距離小于d（vi，vj），這顯然與d（vi，vj）的定義矛盾. 所以在V中關(guān)于度量的三角不等式d（vi，vj）≤d（vi，vk）+d（vk，vj）恒成立.

盡管G作為賦權(quán)圖是連通的，但V作為拓?fù)淇臻g卻不連通，并且空間V還具有其它的一些拓?fù)湫再|(zhì).

定理2 （V，d）是緊的、不連通的、Hausdorff的、正則、正規(guī)拓?fù)淇臻g.

證 有限拓?fù)淇臻g當(dāng)然是緊空間.

為證明它是不連通空間，令ρ=mini≠j{d（vi，vj）}，并記B（v，ε）為V中以點(diǎn)v為心、ε為半徑的開(kāi)球，則

V=B（v1，ρ）∪∪nk=2B（vk，ρ）

于是V可表為不交開(kāi)集之并，從而V不連通.

根據(jù)距離的定義可知上面給出的ρ>0，且對(duì)任意的v∈V，B（v，ρ）是僅含一個(gè)點(diǎn)v的開(kāi)集，故當(dāng)vi≠vj時(shí)，B（vi，ρ）與B（vj，ρ）就是分別包含vi和vj的不交開(kāi)集，這就證明了V是Hausdorff空間.

現(xiàn)在證明V是正則空間. 為此，任取v∈V和v的任一開(kāi)鄰域U，顯然B（v，ρ）U.如果w∈V，w≠v， 則B（w，ρ）∩B（v，ρ）=Φ，從而wB′（v，ρ），即B（v，ρ）也是閉集，于是B（v，ρ）U，所以V是正則的.

容易證明V是正規(guī)空間. 任取V的兩個(gè)不交非空閉集A和B，由于上面已證V的單點(diǎn)集是既開(kāi)又閉的，故∪v∈AB（v，ρ）與∪v∈BB（v，ρ）就是分別包含集A和B的不交開(kāi)集，所以V是正規(guī)空間.

在實(shí)際應(yīng)用中，常常要考慮與一個(gè)運(yùn)輸網(wǎng)絡(luò)相關(guān)的賦權(quán)圖的最短通路的計(jì)算問(wèn)題. 這一問(wèn)題的一般提法是，從一頂點(diǎn)出發(fā)到指定的另一頂點(diǎn)的通路有多條時(shí)，如何求出具有最小費(fèi)用的運(yùn)輸方案？

1959年，由Dijkstra 提出了一種算法，其主要的依據(jù)是以下兩個(gè)結(jié)果：

定理3 設(shè)G=是賦權(quán)圖，SV，u∈S，T=V-S，對(duì)任何x∈T， 令lS（x）表示從u到x的不含T中除x外的其他通路中最短通路的長(zhǎng)，則

lS（t）=min{lS（x）|x∈T}=d（u，t）.

定理4 若定理3的條件滿足，且對(duì)任何x∈S，lS（x）≤lS（t），S′=S∪{t}，T′=T-{t}，

則對(duì)任意x∈T′，有

lS′（x）=min{lS（x），lS（t）+W（t，x）}.

此結(jié)果所提供的方法不太直觀. 現(xiàn)提出一個(gè)類似的算法，證明上要容易得多.

定理5 取定v1∈V，則存在度量空間V的一個(gè)子空間鏈V1V2…VkV，使得對(duì)每個(gè)v∈V，必有v∈Vi+1但vVi，且從v1到v的距離可在子空間Vi+1中求出.

證 第一步. 令r=min{W（v1，v）v是與v1關(guān)聯(lián)的點(diǎn)}，不妨設(shè)有r=W（v1，v2）=r2，于是從v1到v2的距離就是r2.

第二步. 令V2={v1，v2}為V的度量子空間，令r=min{W（v1，v），r2+W（v2，v）v與v1或v2關(guān)聯(lián)}，設(shè)這樣找到的點(diǎn)為v3，并記r=r3，則從v1到v3的距離就是r3. 這是因?yàn)閞3要么是關(guān)聯(lián)邊的長(zhǎng)W（v1，v3），要么從v1到v3的最短通路是經(jīng)過(guò)點(diǎn)v2的，此時(shí)r3=r2+W（v2，v3）.其它不與v1或v2關(guān)聯(lián)的點(diǎn)要作連接到v1的通路時(shí)，必須經(jīng)過(guò)v2或v3，因而從v1到此點(diǎn)的任一通路的長(zhǎng)必大于r3. 此時(shí)，容易知道r3≥r2，V2={v∈V|d（v1，v）≤r3}是一個(gè)閉圓盤(pán).

第三步. V3={v1，v2，v3}為V的度量子空間，令

r=min{W（v1，v），r2+W（v2，v），r3+W（v3，v）v與V3中的某點(diǎn)關(guān)聯(lián)}

不妨設(shè)r在點(diǎn)v4處取到，并記r=r4. 因?yàn)閺膙1到v4的最短通路或是它們的關(guān)聯(lián)邊，或是經(jīng)過(guò)頂點(diǎn)v2或v3再到v4. 此時(shí)，r4≥r3≥r2.

第四步. V4={v1，v2，v3，v4}為V的度量子空間，令

r=min{W（v1，v），r2+W（v2，v），r3+W（v3，v），r4+W（v4，v）v與V4中的某點(diǎn)關(guān)聯(lián)}

同樣，設(shè)上述的r在點(diǎn)v5處取到，并記r=r5，那么，從v1到v5的距離就是r5.

如此繼續(xù)下去，經(jīng)過(guò)有限次計(jì)算，就可求出從點(diǎn)v1到其它頂點(diǎn)的距離，同時(shí)也求出了相應(yīng)的子空間鏈. （作者單位：武漢理工大學(xué)華夏學(xué)院）

參考文獻(xiàn)

[1] 劉玉珍，劉詠梅.離散數(shù)學(xué)[M]2003年8月修訂版.武漢：武漢大學(xué)出版社，2003.

[2] 熊金城.點(diǎn)集拓?fù)渲v義[M]第二版.北京：高等教育出版社，1998.