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

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

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

3、， 即它易于數(shù)學處理 和計算 2 。本文主要研究的是架設通信網(wǎng)絡系統(tǒng)的費用最小問題，應用數(shù)學建模知識， 建立相應的數(shù)學模型，其中求最小生成樹可以通過 Prim 算法和 Kruskal 算法， 根據(jù)本文所要解決問題的特點，主要采用 Prim 算法3 。依據(jù)算法的基本思想加 入了不同的權值，解決不同情況下網(wǎng)絡架設的費用最小問題， 并編寫了相關程序， 該程序具有較強的通用性，易于在實際中使用。一、相關知識介紹1. 樹樹包含n (n>=0)個節(jié)點。當n=0時表示為空樹。其定義如下：T=(D,R)其中，D為樹中節(jié)點的有限集合，關系 R滿足一下條件： 有且僅有一個節(jié)點k0屬于D,它對于關系R來說沒有

4、前趨節(jié)點，結點k0稱作 樹的根結點。 除根結點 k0 之外， D 中的每個結點僅有一個前趨結點，但可以有過個后繼結 點。 D中可以有多個終端結點。即除根結點無父結點，其余各結點都有一個父結點和n( n>=0)個子結點。2. 鄰接矩陣 圖的矩陣表示，本文中只用到了鄰接矩陣，故在這只提出鄰接矩陣的定義， 及其圖在鄰接矩陣中的表示。設圖 A = (V, E) 是一個有 n 個頂點的圖 , 圖的鄰接矩陣是一個二維數(shù)組 nn， 用來存放頂點的信息和邊或弧的信息。 是表示頂點之間相鄰關系的矩陣。設G=(V,E)是一個圖，其中V=v1,v2,vn。G的鄰接矩陣是一個具有下 列性質的 n 階方陣： 無向

5、圖的鄰接矩陣是對稱的；有向圖的鄰接矩陣可能是不對稱的。 無向圖的鄰接矩陣中第i行第j列表示i結點到j結點的度即權值，可以表示 為某一具體應用的數(shù)據(jù)。也表示i結點是否與j結點連通。3. 最小生成樹在一給定的無向圖G=(V, E)中(u,v)代表連接頂點u與頂點v的邊(即),而 w(u,v)代表此邊的權重,若存在T為E的子集(即)且為無循環(huán)圖，使得的 w(T) 最小則此T為G的最小生成樹。二、提出問題與問題抽象1. 提出問題假設在五個城市架設通信網(wǎng)絡系統(tǒng)，任意兩個城市之間都可直接架設通信網(wǎng) 絡，最終目標是以最小總費用在五個城市架設通信網(wǎng)絡系統(tǒng)。表1為各城市之間的距離，單位為公里。各城市之間架設網(wǎng)絡

6、每公里費用為 10000元。其中五個城 市分別用A B C D E表示。表1：五城市之間距離關系ABCDEA010122122B0211513C01214D017E02問題的數(shù)學抽象因為任意兩個城市之間都可直接架設通信網(wǎng)絡，并且網(wǎng)絡連接無方向性，所 以五個城市之間的連接圖如圖1可以認為是一個無向連通賦權圖 G(V,E,W)，其 中，V表示頂點集，E表示邊集,W表示各邊權值，本問題代表為公里數(shù)。這樣問 題就轉化為一個圖論問題，變?yōu)榱艘粋€在無向連通賦權圖 G中求解一棵最小代價 生成樹問題，該樹滿足以下條件： 樹中任意兩點之間至多只有一條邊 樹中邊數(shù)等于樹的頂點數(shù)減一 樹中任意去掉一條邊，即得一個不

7、連通圖 樹中各邊權值之和是該連通賦權圖中所有可能樹中各邊權值之和最小的。圖1:五城市之間連通圖3. 建立問題求解模型對連通賦權圖G( V,E,W), 一般來說，生成樹不止一個，因此，最小代價生 成樹不一定是唯一的。我們的目的是找出一棵關于圖G的最小代價生成樹。設T(V,E)為G的一棵生成樹，其各邊加權之和：W(T)=E W(e)稱為樹T的權，找G中樹權值最小的生成樹T*,T*為G的最小代價生成樹。4. 數(shù)學模型的算法設計基于具有五個頂點的無向連通賦權圖G的每個生成樹剛好具有四條邊，所以問題是用某種方法選擇四條邊使它們形成G的最小生成樹。此處用到了Prim算法4。構造最小生成樹的Prim算法假設

8、G (V,E,W)為問題中五城市的連通圖，頂點集 V(A,B,C,D,E)，E為圖 中所有帶權邊的集合。設置兩個新的集合U和EDGE其中集合U用于存放G的最 小生成樹中的頂點，集合 EDGE?放G的最小生成樹中的邊。假設構造最小生成樹時，從頂點A出發(fā)，令集合U的初值為U A,集合EDGE勺初值為空。Prim算法的基本思想：從所有u U,v V-U的邊中，選取具有最小權值的邊(u,v ),將頂點v加入集合U中，將邊(u,v)加入集合EDG沖，如此不斷重復， 直到U=V時，最小生成樹構造完畢，這時集合 EDG沖包含了最小生成樹的所有 四條邊。三、算法具體實現(xiàn)1. Prim 算法實現(xiàn)步驟假設V是圖中

9、頂點的集合，E是圖中邊的集合，EDGE最小生成樹的邊的集 合，則 Prim 算法通過以下步驟可以得到最小生成樹：a：初始化：U=U0 ,EDGE=。此步驟設立一個只有頂點 U0的結點集U和 一個空的邊集EDG作為最小生成樹的初始形態(tài)。b:在所有u U,v V-U的邊(u,v) E中，找一條權最小的邊(u0,vi),將此 邊加進集合EDGE (u0,vi) 中，并將此邊的非U中的頂點vi加入U中， U= u0， vi 。c:如果U=V,則算法結束；否則重復步驟2。可以算出當U=V時，步驟2共執(zhí) 行了四次，EDG中也增加了四條邊，這四條邊就是所求出的最小生成樹的邊。2. 算法編碼實現(xiàn)代碼的編寫主要

10、通過 visual studio 2013編輯器來編寫，用到的編程語言為 C+。 具體細節(jié)如下： 首先定義一個 5*5 的二維數(shù)組來存儲鄰接矩陣值，數(shù)組名為 value55; 定 義一個結構體來存儲最小生成樹中邊的信息，結構體定義如下：typedef struct TREEint from;int to;int weight;Tree;其中結構體中有三個整形的成員變量， from 代表最小生成樹中某條邊的起 點， to 代表最小生成樹中某條邊的終點， weight 代表最小生成樹中某條邊的權 重。首先初始化一個結構體數(shù)組 Tree TE5， TE5 用于存儲最小生成樹中邊的信息。 首先假設A為

11、起點，以A為起點，B C、D E為終點的邊假設為最小權邊，將其分別存儲在 TE1,TE2,TE3,TE4 。 找出 TE 數(shù)組中權值最小的邊，然后將其與 TE1 交換數(shù)據(jù)TE 數(shù)組中的 然后假設最小權邊的終點為起點，重新比較各邊的權重，跟新 信息。 重復步驟與，直到找出四條最小權邊。具體代碼如下：void CGraphShow:MiniTree_prim()for (int i = 0; i < MAX; i+)for (int j = 0; j < MAX; j+)valueij(CCTRLDlg*)AfxGetApp()->m_pMainWnd)->valueij;

12、int i, j, k, m, min, t, w;for (i = 1; i < ; i+)TEi.from = 0;TEi.to = i;TEi.weight = value0i;for (j = 1; j < ; j+)m = j;min = MAX_VALUE; for (k = j; k < ; 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 < ; i+)t =

13、TEi.to;w = valuekt;if (w < TEi.weight)TEi.weight = w; TEi.from = k;3.運行結果構建鄰接矩陣見圖2圖2 :鄰接矩陣圖畫出五個城市之間連接圖，見圖 3圖3:連通圖生成最小生成樹，見圖4圖4 :最小生成樹4. 結論通過程序求出的仿真圖形我們可以求出最小生成樹，所以在五座城市之間架設通信線路費用最少為：丫=(10+12+13+12)*10000=470000 元。四、結論本文綜合應用數(shù)學建模和圖論知識，針對通信網(wǎng)絡系統(tǒng)架設的特點及優(yōu)化 目標，建立了問題的數(shù)學模型，并應用 Prim算法求解該數(shù)學模型，最后編寫相 應代碼。程序執(zhí)行結果表明了建立的數(shù)學模型的正確性和Prim算法解決架設通信網(wǎng)絡系統(tǒng)費用最小問題的有效性；同時也證明了該應用程序具有較強的通用 性，可以調整輸入的權值以匹配不同的網(wǎng)絡架設情況，從而使程序易于在實際中使用參考文獻