圖論及其應用論文

《圖論及其應用論文》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。

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

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

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

4、=(V,E)中，若對于V中任意兩個不同的頂點x和y，都存在從x到y(tǒng)以及從y到x的路徑，則稱G是強連通圖。相應地有強連通分量的概念。強連通圖只有一個強連通分量，即是其自身；非強連通的有向圖有多個強連分量。弱連通圖：將有向圖的所有的有向邊替換為無向邊，所得到的圖稱為原圖的基圖。如果一個有向圖的基圖是連通圖，則有向圖是弱連通圖。初級通路：通路中所有的頂點互不相同。初級通路必為簡單通路，但反之不真。(4)性質(zhì)一個無向圖G=(V,E)是連通的，那么邊的數(shù)目大于等于頂點的數(shù)目減一：

5、E

6、>=

7、V

8、-1，而反之不成立。如果G=(V,E)是有向圖，那么它是強連通圖的必要條件

9、是邊的數(shù)目大于等于頂點的數(shù)目：

10、E

11、>=

12、V

13、，而反之不成立。沒有回路的無向圖是連通的當且僅當它是樹，即等價于：

14、E

15、=

16、V

17、-1。2.最小生成樹（1）樹樹包含n（n>=0）個節(jié)點。當n=0時表示為空樹。其定義如下：T=(D,R)其中，D為樹中節(jié)點的有限集合，關系R滿足一下條件：①有且僅有一個節(jié)點k0屬于D，它對于關系R來說沒有前趨節(jié)點，結(jié)點k0稱作樹的根結(jié)點。②除根結(jié)點k0之外，D中的每個結(jié)點僅有一個前趨結(jié)點，但可以有過個后繼結(jié)點。③D中可以有多個終端結(jié)點。即除根結(jié)點無父結(jié)點，其余各結(jié)點都有一個父結(jié)點和n（n>=0）個子結(jié)點。（2）鄰接矩陣圖的矩陣表示，本

18、文中只用到了鄰接矩陣，故在這只提出鄰接矩陣的定義，及其圖在鄰接矩陣中的表示。設圖A=(V,E)是一個有n個頂點的圖,圖的鄰接矩陣是一個二維數(shù)組A.edge[n][n]，　用來存放頂點的信息和邊或弧的信息。是表示頂點之間相鄰關系的矩陣。設G=(V,E)是一個圖，其中V={v1,v2,…,vn}。G的鄰接矩陣是一個具有下列性質(zhì)的n階方陣：①無向圖的鄰接矩陣是對稱的;有向圖的鄰接矩陣可能是不對稱的。②無向圖的鄰接矩陣中第i行第j列表示i結(jié)點到j結(jié)點的度即權(quán)值，可以表示為某一具體應用的數(shù)據(jù)。也表示i結(jié)點是否與j結(jié)點連通。（3）最小生成樹在一給定的無向圖G=(V,E)

19、中(u,v)代表連接頂點u與頂點v的邊(即),而w(u,v)代表此邊的權(quán)重,若存在T為E的子集（即)且為無循環(huán)圖，使得的w(T)最小則此T為G的最小生成樹。3.prim算法思想：首先，選擇帶最小的邊，把它放進生成樹里，相繼添加帶權(quán)最小的邊，這些邊與已在樹立的頂點相關聯(lián)，并且不與已在數(shù)理的邊形成圈，當已經(jīng)添加了n-1條邊為止步驟：假設V是圖中頂點的集合，E是圖中邊的集合，TE為最小生成樹中的邊的集合，則prim算法通過以下步驟可以得到最小生成樹：（1）初始化：U={u0},TE={f}。此步驟設立一個只有結(jié)點u0的結(jié)點集U和一個空的邊集TE作為最小生成樹的初始

20、形態(tài)，在隨后的算法執(zhí)行中，這個形態(tài)會不斷的發(fā)生變化，