最小生成樹在通信網(wǎng)建設(shè)中的應(yīng)用

1、 圖論課程論文設(shè)計(jì)（論文）題目：Prim算法在通信網(wǎng)絡(luò)架設(shè)中的應(yīng)用學(xué) 院 名 稱 ：通信與信息工程學(xué)院學(xué) 生 姓 名 ：專 業(yè) ：學(xué) 號(hào) ：填表時(shí)間： 2014年 12月摘要通信網(wǎng)絡(luò)系統(tǒng)架設(shè)屬于典型的圖論優(yōu)化問題，針對(duì)通信網(wǎng)絡(luò)系統(tǒng)的特點(diǎn)，抽象問題，簡(jiǎn)化模型，以通信網(wǎng)絡(luò)系統(tǒng)架設(shè)費(fèi)用那個(gè)最小為優(yōu)化目標(biāo)，應(yīng)用Prim算法進(jìn)行通信網(wǎng)絡(luò)系統(tǒng)架設(shè)模型研究。首先簡(jiǎn)述了五個(gè)城市之間架設(shè)通信網(wǎng)絡(luò)系統(tǒng)問題，然后應(yīng)用數(shù)學(xué)建模知識(shí)對(duì)隱含在該問題中的圖論模型進(jìn)行了抽象研究，進(jìn)而構(gòu)造問題的數(shù)學(xué)模型，最后應(yīng)用Prim算法設(shè)計(jì)了該通信網(wǎng)絡(luò)系統(tǒng)架設(shè)實(shí)現(xiàn)流程及相應(yīng)代碼的編寫。程序執(zhí)行結(jié)果表明:準(zhǔn)確構(gòu)建了問題的數(shù)學(xué)模型及應(yīng)用Pri

2、m算法正確求解了該數(shù)學(xué)模型；并且權(quán)值因子的可變性使得該程序具有較強(qiáng)的通用性，易于在實(shí)際中使用?！娟P(guān)鍵字】：數(shù)學(xué)建模 無向連通圖 最小生成樹 Prim算法引言隨著數(shù)學(xué)科學(xué)和計(jì)算機(jī)技術(shù)的發(fā)展，數(shù)學(xué)建模知識(shí)在各領(lǐng)域中發(fā)揮著重要作用，抽象實(shí)際問題、建立正確的數(shù)學(xué)模型已成為解決實(shí)際應(yīng)用問題的關(guān)鍵1。通過數(shù)學(xué)建模，就可以對(duì)實(shí)際問題進(jìn)行抽象、簡(jiǎn)化，確定變量和參數(shù)，并應(yīng)用某些“規(guī)律”建立起變量、參數(shù)間的確定的數(shù)學(xué)模型；一個(gè)理想的數(shù)學(xué)模型，它應(yīng)滿足兩個(gè)條件；一是模型的可靠性，即在允許的誤差范圍內(nèi)，能正確反映所考慮系統(tǒng)相關(guān)特性的內(nèi)在聯(lián)系，反映客觀實(shí)際；二是模型的可解性，即它易于數(shù)學(xué)處理和計(jì)算2。本文主要研究的是架

3、設(shè)通信網(wǎng)絡(luò)系統(tǒng)的費(fèi)用最小問題，應(yīng)用數(shù)學(xué)建模知識(shí)，建立相應(yīng)的數(shù)學(xué)模型，其中求最小生成樹可以通過Prim算法和Kruskal算法，根據(jù)本文所要解決問題的特點(diǎn)，主要采用Prim算法3。依據(jù)算法的基本思想加入了不同的權(quán)值，解決不同情況下網(wǎng)絡(luò)架設(shè)的費(fèi)用最小問題，并編寫了相關(guān)程序，該程序具有較強(qiáng)的通用性，易于在實(shí)際中使用。一、 相關(guān)知識(shí)介紹1.樹樹包含n（n=0）個(gè)節(jié)點(diǎn)。當(dāng)n=0時(shí)表示為空樹。其定義如下：T=(D,R)其中，D為樹中節(jié)點(diǎn)的有限集合，關(guān)系R滿足一下條件：有且僅有一個(gè)節(jié)點(diǎn)k0屬于D，它對(duì)于關(guān)系R來說沒有前趨節(jié)點(diǎn)，結(jié)點(diǎn)k0稱作樹的根結(jié)點(diǎn)。除根結(jié)點(diǎn)k0之外，D中的每個(gè)結(jié)點(diǎn)僅有一個(gè)前趨結(jié)點(diǎn)，但可以有

4、過個(gè)后繼結(jié)點(diǎn)。D中可以有多個(gè)終端結(jié)點(diǎn)。即除根結(jié)點(diǎn)無父結(jié)點(diǎn)，其余各結(jié)點(diǎn)都有一個(gè)父結(jié)點(diǎn)和n（n=0）個(gè)子結(jié)點(diǎn)。2.鄰接矩陣圖的矩陣表示，本文中只用到了鄰接矩陣，故在這只提出鄰接矩陣的定義，及其圖在鄰接矩陣中的表示。設(shè)圖 A = (V, E)是一個(gè)有 n 個(gè)頂點(diǎn)的圖, 圖的鄰接矩陣是一個(gè)二維數(shù)組 A.edgenn，用來存放頂點(diǎn)的信息和邊或弧的信息。是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。設(shè)G=(V,E)是一個(gè)圖，其中V=v1,v2,vn。G的鄰接矩陣是一個(gè)具有下列性質(zhì)的n階方陣：無向圖的鄰接矩陣是對(duì)稱的;有向圖的鄰接矩陣可能是不對(duì)稱的。無向圖的鄰接矩陣中第i行第j列表示i結(jié)點(diǎn)到j(luò)結(jié)點(diǎn)的度即權(quán)值，可以表示為某一

5、具體應(yīng)用的數(shù)據(jù)。也表示i結(jié)點(diǎn)是否與j結(jié)點(diǎn)連通。3.最小生成樹在一給定的無向圖G=(V, E)中(u,v) 代表連接頂點(diǎn)u與頂點(diǎn)v的邊(即),而 w(u,v)代表此邊的權(quán)重,若存在T為E的子集（即)且為無循環(huán)圖，使得的w(T)最小則此T為G的最小生成樹。二、提出問題與問題抽象1.提出問題假設(shè)在五個(gè)城市架設(shè)通信網(wǎng)絡(luò)系統(tǒng)，任意兩個(gè)城市之間都可直接架設(shè)通信網(wǎng)絡(luò)，最終目標(biāo)是以最小總費(fèi)用在五個(gè)城市架設(shè)通信網(wǎng)絡(luò)系統(tǒng)。表1為各城市之間的距離，單位為公里。各城市之間架設(shè)網(wǎng)絡(luò)每公里費(fèi)用為10000元。其中五個(gè)城市分別用A、B、C、D、E表示。表1：五城市之間距離關(guān)系A(chǔ)BCDEA010122122B0211513C

6、01214D017E02.問題的數(shù)學(xué)抽象因?yàn)槿我鈨蓚€(gè)城市之間都可直接架設(shè)通信網(wǎng)絡(luò)，并且網(wǎng)絡(luò)連接無方向性，所以五個(gè)城市之間的連接圖如圖1可以認(rèn)為是一個(gè)無向連通賦權(quán)圖G(V,E,W)，其中，V表示頂點(diǎn)集，E表示邊集,W表示各邊權(quán)值，本問題代表為公里數(shù)。這樣問題就轉(zhuǎn)化為一個(gè)圖論問題，變?yōu)榱艘粋€(gè)在無向連通賦權(quán)圖G中求解一棵最小代價(jià)生成樹問題，該樹滿足以下條件： 樹中任意兩點(diǎn)之間至多只有一條邊 樹中邊數(shù)等于樹的頂點(diǎn)數(shù)減一 樹中任意去掉一條邊，即得一個(gè)不連通圖 樹中各邊權(quán)值之和是該連通賦權(quán)圖中所有可能樹中各邊權(quán)值之和最小的。圖1：五城市之間連通圖3.建立問題求解模型對(duì)連通賦權(quán)圖G（V,E,W）,一般來說，

7、生成樹不止一個(gè)，因此，最小代價(jià)生成樹不一定是唯一的。我們的目的是找出一棵關(guān)于圖G的最小代價(jià)生成樹。設(shè)T(V,E)為G的一棵生成樹，其各邊加權(quán)之和：W(T)=W(ei)稱為樹T的權(quán)，找G中樹權(quán)值最小的生成樹T*,T*為G的最小代價(jià)生成樹。4.數(shù)學(xué)模型的算法設(shè)計(jì) 基于具有五個(gè)頂點(diǎn)的無向連通賦權(quán)圖G的每個(gè)生成樹剛好具有四條邊，所以問題是用某種方法選擇四條邊使它們形成G的最小生成樹。此處用到了Prim算法4。4.1構(gòu)造最小生成樹的Prim算法假設(shè)G（V,E,W）為問題中五城市的連通圖，頂點(diǎn)集V(A,B,C,D,E)，E為圖中所有帶權(quán)邊的集合。設(shè)置兩個(gè)新的集合U和EDGE,其中集合U用于存放G的最小生成

8、樹中的頂點(diǎn)，集合EDGE存放G的最小生成樹中的邊。假設(shè)構(gòu)造最小生成樹時(shí)，從頂點(diǎn)A出發(fā)，令集合U的初值為UA,集合EDGE的初值為空5。Prim算法的基本思想：從所有uU,vV-U的邊中，選取具有最小權(quán)值的邊（u,v）,將頂點(diǎn)v加入集合U中，將邊(u,v)加入集合EDGE中，如此不斷重復(fù)，直到U=V時(shí)，最小生成樹構(gòu)造完畢，這時(shí)集合EDGE中包含了最小生成樹的所有四條邊。三、算法具體實(shí)現(xiàn)1. Prim算法實(shí)現(xiàn)步驟假設(shè)V是圖中頂點(diǎn)的集合，E是圖中邊的集合，EDGE為最小生成樹的邊的集合，則Prim算法通過以下步驟可以得到最小生成樹：a：初始化：U=U0,EDGE=。此步驟設(shè)立一個(gè)只有頂點(diǎn)U0的結(jié)點(diǎn)集

9、U和一個(gè)空的邊集EDGE作為最小生成樹的初始形態(tài)。b：在所有uU,vV-U的邊(u,v)E中，找一條權(quán)最小的邊(u0,vi),將此邊加進(jìn)集合EDGE=(u0,vi)中，并將此邊的非U中的頂點(diǎn)vi加入U(xiǎn)中，U=u0，vi。c：如果U=V,則算法結(jié)束；否則重復(fù)步驟2?？梢运愠霎?dāng)U=V時(shí)，步驟2共執(zhí)行了四次，EDGE中也增加了四條邊，這四條邊就是所求出的最小生成樹的邊。2. 算法編碼實(shí)現(xiàn)代碼的編寫主要通過visual studio 2013編輯器來編寫，用到的編程語言為C+。具體細(xì)節(jié)如下：首先定義一個(gè)5*5的二維數(shù)組來存儲(chǔ)鄰接矩陣值，數(shù)組名為value55;定義一個(gè)結(jié)構(gòu)體來存儲(chǔ)最小生成樹中邊的信息，

10、結(jié)構(gòu)體定義如下：typedef struct TREEint from;int to;int weight;Tree;其中結(jié)構(gòu)體中有三個(gè)整形的成員變量，from代表最小生成樹中某條邊的起點(diǎn)，to代表最小生成樹中某條邊的終點(diǎn)，weight代表最小生成樹中某條邊的權(quán)重。首先初始化一個(gè)結(jié)構(gòu)體數(shù)組 Tree TE5，TE5用于存儲(chǔ)最小生成樹中邊的信息。首先假設(shè)A為起點(diǎn)，以A為起點(diǎn)，B、C、D、E為終點(diǎn)的邊假設(shè)為最小權(quán)邊，將其分別存儲(chǔ)在TE1,TE2,TE3,TE4。找出TE數(shù)組中權(quán)值最小的邊，然后將其與TE1交換數(shù)據(jù)。然后假設(shè)最小權(quán)邊的終點(diǎn)為起點(diǎn)，重新比較各邊的權(quán)重，跟新TE數(shù)組中的信息。重復(fù)步驟與，

11、直到找出四條最小權(quán)邊。具體代碼如下：void CGraphShow:MiniTree_prim()for (int i = 0; i MAX; i+)for (int j = 0; j m_pMainWnd)-valueij;int i, j, k, m, min, t, w;for (i = 1; i m_ctrldlg.m_editvalue; i+)TEi.from = 0;TEi.to = i;TEi.weight = value0i;for (j = 1; j m_ctrldlg.m_editvalue; j+)m = j;min = MAX_VALUE;for (k = j; k

12、m_ctrldlg.m_editvalue; k+)if (TEk.weight min)min = TEk.weight;m = k;Tree temp;temp = TEj;TEj = TEm;TEm = temp;k = TEj.to;for (i = j + 1; i m_ctrldlg.m_editvalue; i+)t = TEi.to;w = valuekt;if (w TEi.weight)TEi.weight = w;TEi.from = k;3. 運(yùn)行結(jié)果構(gòu)建鄰接矩陣見圖2圖2：鄰接矩陣圖畫出五個(gè)城市之間連接圖，見圖3圖3：連通圖生成最小生成樹，見圖4圖4：最小生成樹4結(jié)論通過程序求出的仿真圖形我們可以求出最小生成樹，所以在五座城市之間架設(shè)通信線路費(fèi)用最少為：Y=(10+12+13+12)*10000=470000元。四、結(jié)論本文綜合應(yīng)用數(shù)學(xué)建模和圖論知識(shí)，針對(duì)通信網(wǎng)絡(luò)系統(tǒng)架設(shè)的特點(diǎn)及優(yōu)化目標(biāo)，建立了問題的數(shù)學(xué)模型，并應(yīng)用Prim算法求解該數(shù)學(xué)模型，最后編寫相應(yīng)代碼。程序執(zhí)行結(jié)果表明了建立的數(shù)學(xué)模型的正確性和Prim算法解決架設(shè)通信網(wǎng)絡(luò)系統(tǒng)費(fèi)用最小問題的有效性；同時(shí)也證明了該應(yīng)用程序具有較強(qiáng)的通用性，可