|
N個(gè)城市間的最經(jīng)濟(jì)的網(wǎng)絡(luò)建設(shè)
陸軍航空兵學(xué)院 信息技術(shù)教研室 徐剛 魏琴 2014/4/1 10:31:48
摘 要：n個(gè)城市間有多種的網(wǎng)絡(luò)建設(shè)方案，本文使用最小支撐樹(shù)的原理，運(yùn)用算法中的普林算法進(jìn)行運(yùn)算。得到的最小生成樹(shù)使n個(gè)城市間的連接是連通的，而且是最經(jīng)濟(jì)的在各種網(wǎng)絡(luò)建設(shè)方案中。
關(guān)鍵字：最小支撐樹(shù)、普林算法
The most economical network construction in n cities
XuGang WeiQin
(Army Aviation Institute Infirmation Technology ,Beijing 101123, China)
Abstract: N cities have a variety of network construction plan, this article USES the principle of minimum support tree, spring algorithm operation in using the algorithm. The minimum spanning tree connection is connected between the n city, and it is the most economical in various network construction scheme.
Key words: the minimum spanning. Procedure prime.
引言
當(dāng)今時(shí)代發(fā)展迅速，各個(gè)城市之間需要有比較方便的通訊和聯(lián)系。這就需要在各個(gè)城市間建立通信，這就涉及到了網(wǎng)絡(luò)建設(shè)，網(wǎng)絡(luò)建設(shè)的方案很多而且差別較大，這就需要根據(jù)當(dāng)?shù)鼐W(wǎng)絡(luò)建設(shè)的實(shí)際要求進(jìn)行設(shè)計(jì)。本文就N個(gè)城市間的網(wǎng)絡(luò)建設(shè)以最經(jīng)濟(jì)的方法進(jìn)行了設(shè)計(jì)。N個(gè)城市間的最經(jīng)濟(jì)的網(wǎng)絡(luò)建設(shè)就要求他們之間是一個(gè)連通的關(guān)系，各個(gè)城市間就可以進(jìn)行通信，這避免了每?jī)蓚�(gè)城市間直接建立連接的各種建設(shè)費(fèi)用，而怎樣連接才能使經(jīng)濟(jì)成本最低呢？這就涉及到了最小支撐樹(shù)，以及實(shí)現(xiàn)最小支撐樹(shù)的兩個(gè)算法。本文就七個(gè)城市間的通信，來(lái)解決他們之間的網(wǎng)絡(luò)建設(shè)的最經(jīng)濟(jì)的連接方法。
正文
有七個(gè)城市，要實(shí)現(xiàn)他們之間的通信，圖1是這七個(gè)城市的具體關(guān)系：
如果要實(shí)現(xiàn)這七個(gè)城市間的通信，則按照兩兩之間建立聯(lián)系的方式可以建立一個(gè)通信網(wǎng)絡(luò)，可以保證通信的正常。但是這樣也同樣會(huì)帶來(lái)問(wèn)題，這樣在兩兩城市之間建立通信，需要的設(shè)備和線路比較多，會(huì)使建設(shè)費(fèi)用大幅度的增加，是一種不合理的建網(wǎng)方式。我們可以尋找一種最經(jīng)濟(jì)的建網(wǎng)的方式，既不影響網(wǎng)絡(luò)的通信，又是建設(shè)費(fèi)用大幅度的降低，這是我們所追求的。這就涉及到了最小支撐樹(shù)的問(wèn)題。我們可以利用最小生成樹(shù)原理進(jìn)行最經(jīng)濟(jì)的網(wǎng)絡(luò)建設(shè)。人們總想尋找最經(jīng)濟(jì)的方法將一個(gè)終端集合，通過(guò)某種方式將其連接起來(lái)。如“用通訊線路把若干城市聯(lián)結(jié)起來(lái)，要求設(shè)計(jì)最短通信線路”，“為了解決苦于居民點(diǎn)供水，要求設(shè)計(jì)最短的自來(lái)水管線路”等，總之，求最小生成樹(shù)是現(xiàn)實(shí)世界中解決實(shí)際問(wèn)題的需要參考 。我們可以用普林算法得到最小生成樹(shù)，也就得到了最經(jīng)濟(jì)的建網(wǎng)方案和連接方式 。
下面是用普林算法來(lái)求最小樹(shù)。
可以用普林算法來(lái)求出最小樹(shù)，首先選擇帶最小權(quán)的邊，吧它放進(jìn)支撐樹(shù)里，相繼向樹(shù)里添加帶最小權(quán)的邊，這些邊與已在書(shū)里的邊形成圈，當(dāng)已經(jīng)添加了n-1條邊為止 。根據(jù)普林算法我們可以進(jìn)行運(yùn)算：
選擇 1 2 3 4 5 6
邊 a.f a.e e.g a.b b.c c.d
權(quán) 1 2 2 3 1 4
我們最后可以得到它的最經(jīng)濟(jì)的連接方法如圖2
.......
N個(gè)城市間的最經(jīng)濟(jì)的網(wǎng)絡(luò)連接可以得到實(shí)現(xiàn)。
結(jié)論
通過(guò)使用最小生成樹(shù)原理，并且運(yùn)用普林算法我們可以得到七個(gè)城市之間的最小生成樹(shù)，通過(guò)最小生成樹(shù)，這七個(gè)城市自建可以形成一個(gè)互通的網(wǎng)絡(luò)，并且實(shí)現(xiàn)了最經(jīng)濟(jì)的組網(wǎng)方式，這體現(xiàn)了最小生成樹(shù)的用法。
參考文獻(xiàn)：
[1] 太原師院計(jì)算機(jī)教研室 求最小生成樹(shù)的一個(gè)算法[J] 太原師范專(zhuān)科學(xué)校學(xué)報(bào) 1999
[2] 徐俊明 圖論及其應(yīng)用[M]中國(guó)科技大學(xué)出版社 2000
[3] 吳文虎等 圖論的算法與程序設(shè)計(jì)[M] 清華大學(xué)出版社 2002
[4] 陳莉等 離散數(shù)學(xué)[M] 高等教育出版社 2002
附件下載：點(diǎn)擊下載全部文件
|