圖論及其應(yīng)用論文

1、圖論及其應(yīng)用論文姓名：xxx學(xué)號：xxx專業(yè)：xxx圖論在高校互聯(lián)校內(nèi)網(wǎng)建設(shè)的應(yīng)用摘要圖論和我們的生活其實是息息相關(guān)的，我們在生活中處處可見圖論的實際應(yīng)用。特別的，圖論對我們通信專業(yè)以后的工作也有著極大的幫助。在以后的工作中也會時時用到圖論的相關(guān)知識。本論文的主旨是利用相關(guān)的圖論知識來解決重慶幾所高校建立互聯(lián)校內(nèi)網(wǎng)的問題。主要是為了能使各重慶高校的學(xué)生能夠免費共享高校的學(xué)習(xí)資源。從而促進各高校學(xué)生的共同發(fā)展。本文中，解決重慶幾所高校建立互聯(lián)校內(nèi)網(wǎng)主要應(yīng)用的是求圖的最小生成樹的方法。而求圖的最小生成樹有兩種算法，一種是Prim（普里姆）算法，另一種是Kruskal（克魯斯卡爾）算法。本文通過將高

2、校轉(zhuǎn)換成連通圖，再將連通圖轉(zhuǎn)換成鄰接矩陣。在C+上，通過輸入結(jié)點和權(quán)值，用普里姆算法獲得權(quán)值最小邊來得到最小生成樹，從而在保證各個地點之間能連通的情況下節(jié)省所需費用。關(guān)鍵字：最小生成樹、PRIM算法、鄰接矩陣、高校互聯(lián)校內(nèi)網(wǎng)建設(shè)1. 連通圖（1）概述在圖論中，連通圖基于連通的概念。在一個無向圖 G 中，若從頂點vi到頂點vj有路徑相連(當(dāng)然從vj到vi也一定有路徑)，則稱vi和vj是連通的。如果 G 是有向圖，那么連接vi和vj的路徑中所有的邊都必須同向。如果圖中任意兩點都是連通的，那么圖被稱作連通圖。圖的連通性是圖的基本性質(zhì)。（2）嚴格定義對一個圖 G=(V,E) 中的兩點 x 和 y ，若

3、存在交替的頂點和邊的序列=(x=v0-e1-v1-e2-.-ek-(vk+1)=y) (在有向圖中要求有向邊vi( vi+1)屬于E )，則兩點 x 和 y 是連通的。是一條x到y(tǒng)的連通路徑，x和y分別是起點和終點。當(dāng) x = y 時， 被稱為回路。如果通路 中的邊兩兩不同，則 是一條簡單通路，否則為一條復(fù)雜通路。如果圖 G 中每兩點間皆連通，則 G 是連通圖。（3)相關(guān)概念連通分量：無向圖 G的一個極大連通子圖稱為 G的一個連通分量（或連通分支）。連通圖只有一個連通分量，即其自身；非連通的無向圖有多個連通分量。強連通圖：有向圖 G=(V,E) 中，若對于V中任意兩個不同的頂點 x和 y，都存

4、在從x到 y以及從 y到 x的路徑，則稱 G是強連通圖。相應(yīng)地有強連通分量的概念。強連通圖只有一個強連通分量，即是其自身；非強連通的有向圖有多個強連分量。弱連通圖：將有向圖的所有的有向邊替換為無向邊，所得到的圖稱為原圖的基圖。如果一個有向圖的基圖是連通圖，則有向圖是弱連通圖。初級通路：通路中所有的頂點互不相同。初級通路必為簡單通路，但反之不真。(4)性質(zhì)一個無向圖 G=(V,E) 是連通的，那么邊的數(shù)目大于等于頂點的數(shù)目減一：|E|>=|V|-1，而反之不成立。如果 G=(V,E) 是有向圖，那么它是強連通圖的必要條件是邊的數(shù)目大于等于頂點的數(shù)目：|E|>=|V|，而反之不成立。沒

5、有回路的無向圖是連通的當(dāng)且僅當(dāng)它是樹，即等價于：|E|=|V|-1。2. 最小生成樹（1）樹樹包含n（n>=0）個節(jié)點。當(dāng)n=0時表示為空樹。其定義如下：T=(D,R)其中，D為樹中節(jié)點的有限集合，關(guān)系R滿足一下條件：有且僅有一個節(jié)點k0屬于D，它對于關(guān)系R來說沒有前趨節(jié)點，結(jié)點k0稱作樹的根結(jié)點。除根結(jié)點k0之外，D中的每個結(jié)點僅有一個前趨結(jié)點，但可以有過個后繼結(jié)點。D中可以有多個終端結(jié)點。即除根結(jié)點無父結(jié)點，其余各結(jié)點都有一個父結(jié)點和n（n>=0）個子結(jié)點。（2）鄰接矩陣圖的矩陣表示，本文中只用到了鄰接矩陣，故在這只提出鄰接矩陣的定義，及其圖在鄰接矩陣中的表示。設(shè)圖 A = (

6、V, E)是一個有 n 個頂點的圖, 圖的鄰接矩陣是一個二維數(shù)組 A.edgenn，用來存放頂點的信息和邊或弧的信息。是表示頂點之間相鄰關(guān)系的矩陣。設(shè)G=(V,E)是一個圖，其中V=v1,v2,vn。G的鄰接矩陣是一個具有下列性質(zhì)的n階方陣：無向圖的鄰接矩陣是對稱的;有向圖的鄰接矩陣可能是不對稱的。無向圖的鄰接矩陣中第i行第j列表示i結(jié)點到j(luò)結(jié)點的度即權(quán)值，可以表示為某一具體應(yīng)用的數(shù)據(jù)。也表示i結(jié)點是否與j結(jié)點連通。（3）最小生成樹在一給定的無向圖G=(V, E)中(u,v) 代表連接頂點u與頂點v的邊(即),而 w(u,v)代表此邊的權(quán)重,若存在T為E的子集（即)且為無循環(huán)圖，使得的w(T)

7、最小則此T為G的最小生成樹。3.prim算法思想：首先，選擇帶最小的邊，把它放進生成樹里，相繼添加帶權(quán)最小的邊，這些邊與已在樹立的頂點相關(guān)聯(lián)，并且不與已在數(shù)理的邊形成圈，當(dāng)已經(jīng)添加了n-1條邊為止步驟：假設(shè)V是圖中頂點的集合，E是圖中邊的集合，TE為最小生成樹中的邊的集合，則prim算法通過以下步驟可以得到最小生成樹：（1）初始化：U=u 0,TE=f。此步驟設(shè)立一個只有結(jié)點u 0的結(jié)點集U和一個空的邊集TE作為最小生成樹的初始形態(tài)，在隨后的算法執(zhí)行中，這個形態(tài)會不斷的發(fā)生變化，直到得到最小生成樹為止。（2）在所有uU,vVU的邊（u,v）E中，找一條權(quán)最小的邊（u0,v0），將此邊加進集合T

8、E中，并將此邊的非U中頂點加入U中。此步驟的功能是在邊集E中找一條邊，要求這條邊滿足以下條件：首先邊的兩個頂點要分別在頂點集合U和VU中，其次邊的權(quán)要最小。找到這條邊以后，把這條邊放到邊集TE中，并把這條邊上不在U中的那個頂點加入到U中。這一步驟在算法中應(yīng)執(zhí)行多次，每執(zhí)行一次，集合TE和U都將發(fā)生變化，分別增加一條邊和一個頂點，因此，TE和U是兩個動態(tài)的集合，這一點在理解算法時要密切注意。（3）如果U=V，則算法結(jié)束；否則重復(fù)步驟2?？梢园驯静襟E看成循環(huán)終止條件。我們可以算出當(dāng)U=V時，步驟2共執(zhí)行了n1次（設(shè)n為圖中頂點的數(shù)目），TE中也增加了n1條邊，這n1條邊就是需要求出的最小生成樹的邊

9、。4.實際問題及其解決現(xiàn)有：重慶大學(xué)，西南大學(xué)，西南政法大學(xué)，重慶師范大學(xué)，重慶郵電大學(xué)5所高校，要求把他們的校內(nèi)網(wǎng)進行互聯(lián)，以組建一個更大的校園網(wǎng)絡(luò)。在發(fā)費最少的情況下進行光纜的鋪設(shè)。根據(jù)實際測量地圖的得到的各學(xué)校之間的直線距離圖：由于每公里光纜造價相同，故可以用實際距離代替造價作為權(quán)重。實際情況縮略圖：設(shè)：重慶郵電大學(xué)V1重慶大學(xué)V2重慶師范大學(xué)V3西南大學(xué)V4西南政法大學(xué)V5輸入程序運行得到結(jié)果：解決問題得到結(jié)果：5.總結(jié)通過對prim算法編寫的程序我們可以輕易地得到在發(fā)費最少的情況下進行光纜的鋪設(shè)的路徑。這大大的節(jié)約了成本和時間，是對實際問題的一次生動嘗試。同時這個程序也可以進行相應(yīng)的

10、改善和推廣，以利于我們的工作實踐。參考文獻【1】圖論及其算法，殷劍宏等，中國科學(xué)技術(shù)大學(xué)出版社。【2】C語言程序設(shè)計(第三版)，譚浩強，清華大學(xué)出版社?！?】數(shù)據(jù)結(jié)構(gòu)(C語言版)，嚴蔚敏 吳偉民，清華大學(xué)出版社。程序#include "stdio.h"#define maxnum 10#define maxvalue 88typedef struct /定義存放各節(jié)點間邊的權(quán)值的二位數(shù)組為新的數(shù)據(jù)類型可稱為圖int vmaxvaluemaxvalue; mgraph; /該數(shù)據(jù)類型用標(biāo)識符mgraph表示mgraph input(int n) /數(shù)據(jù)輸入函數(shù)用于輸入各節(jié)點間

11、邊的權(quán)值mgraph x; /定義x為mgraph類型while(n<=0|n>maxnum) /控制輸入出錯重新執(zhí)行printf("輸入有誤,請重新輸入:"); scanf("%d",&n);for(int i=1;i<=n;i+) /雙層循環(huán)控制每個節(jié)點到其他各節(jié)點的權(quán)值for(int j=0;j<=n;j+) int temp; /定義臨時變量用于存放輸入權(quán)值便于接下的過濾操作if(i=j) /各節(jié)點到自身的權(quán)重賦為0x.vij=0; else if(i<j) /賦值其他各點到比其大的下標(biāo)的節(jié)點printf(&

12、quot;請輸入節(jié)點%d到節(jié)點%d的權(quán):",i,j);scanf("%d",&temp); /將輸入臨時存放在tempwhile(temp=0|temp<-1) /過濾輸入數(shù)據(jù)printf("輸入有誤,請重新輸入:n");printf("請輸入%d到%d的權(quán):",i,j);scanf("%d",&temp);if(temp>0) /將符合要求數(shù)據(jù)賦值給tempx.vij=temp; else /temp=-1時將權(quán)重賦值最大值88 x.vij=maxvalue;else /i&

13、gt;j由于權(quán)重是對稱的即呈上三角或下三角分布故只需將i,j對換即可x.vij=x.vji;printf("n");return x; /返回圖xvoid print(mgraph g,int n) /打印函數(shù)int i,j; /定義整型i,jprintf(" "); /打印美觀需要for(i=1;i<=n;i+) printf("%2d ",i); printf("n");for(i=1;i<=n;i+) /雙層循環(huán)按矩陣方式打印輸出各節(jié)點間權(quán)值printf("%d ",i); f

14、or(j=1;j<=n;j+)printf("%2d ",g.vij); printf("n");void prim(mgraph g,int k,int n) /核心算法Prim算法實現(xiàn)函數(shù)int i,j,min,p; /定義整型變量i,j用于循環(huán) min和p分別用于臨時存放最小權(quán)值及其下標(biāo)struct /定義型類型數(shù)據(jù)closedge用于臨時存放下標(biāo)和最小邊int adjvex;int lowcost;closedgemaxnum; for(i=1;i<=n;i+) /初始化輔助數(shù)組if(i!=k) closedgei.adjvex=k;

15、closedgei.lowcost=g.vki;closedgek.lowcost=0; /將節(jié)點加入生成樹中for(i=1;i<n;i+) /循環(huán)比較最小權(quán)值且將最小權(quán)值的點加入生成樹中并打印輸出p=1; /初始化p min=maxvalue; /初始化最小權(quán)值for(j=1;j<=n;j+) /循環(huán)n次比較最小權(quán)值if(closedgej.lowcost!=0&&closedgej.lowcost<min) /當(dāng)前節(jié)點不在已生成樹中且權(quán)值最下min=closedgej.lowcost; /替換最小權(quán)值為當(dāng)前節(jié)點的權(quán)值p=j; /記錄該節(jié)點下標(biāo)printf("%d_ _%dn",closedgep.adjvex,p,min); /打印最小的權(quán)值的下標(biāo)和最小邊closedgep.lowcost=0; /將該節(jié)點加入生成樹中 for(j=1;j<=n;j+) /刷新臨時存放空間if(g.vpj) < (closedgej.lowcost)closedgej.lowcost=g.vpj; /賦值最小邊closedgej.adjvex=p; /賦值最小邊對應(yīng)下標(biāo)int main() /主函數(shù)int n,start; /定義整型n,start表示節(jié)點數(shù)和開始節(jié)點printf