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

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

1、論在多播生成樹快速算法的應(yīng)用摘要：為了有效地支持多播通信路由（路徑）選擇是一個關(guān)鍵問題。路由選擇負(fù)責(zé)對源與目的結(jié)點間的多條可行路徑根據(jù)某種目標(biāo)加以選擇、例如網(wǎng)絡(luò)資源消耗最低化就是路由選擇的重要目標(biāo)。解決多播路由的方法涉及到〃樹"的構(gòu)造，如果能構(gòu)造出合理的多播樹,就可以在滿足業(yè)務(wù)需要的前提下，盡量少占用網(wǎng)絡(luò)資源。本篇論文以圖論為基礎(chǔ)，主要探討和研究了多播生成樹問題。主要探討了單約束的單樹多播這種情況，介紹了經(jīng)典的Dijkstra算法，并在此基礎(chǔ)上提出了動態(tài)最短路徑樹算法。關(guān)鍵詞:圖論路由最短路徑多播樹Di

2、jkstra算法1?多播生成樹問題的提出隨著Internet的爆炸性發(fā)展，在Internet上產(chǎn)生了許多新的應(yīng)用，其中有很多是高帶寬的多媒體應(yīng)用,這就帶來了帶寬的急劇消耗和網(wǎng)絡(luò)擁擠問題。為了緩解這一問題，人們提岀了IP多播技術(shù)。多播技術(shù)是一種允許一個或多個發(fā)送者（多播源）發(fā)送單一的數(shù)據(jù)包到多個接收者的網(wǎng)絡(luò)技術(shù)。該技術(shù)有助于緩解當(dāng)前Internet的業(yè)務(wù)量而導(dǎo)致的擁塞問題。為了有效地支持多播通信，路由（或路徑）選擇是一個需要討論的關(guān)鍵問題。路由選擇負(fù)責(zé)對源與目的結(jié)點間的多條可行路徑根據(jù)某種目標(biāo)加以選擇。路

3、由選擇算法是計算機網(wǎng)絡(luò)中的一個重要硏究課題，它直接關(guān)系到網(wǎng)絡(luò)效率、傳輸延遲和吞吐量等通信網(wǎng)絡(luò)的主要技術(shù)性能指標(biāo)。路由選擇算法的設(shè)計一般包括以下內(nèi)容:首先對一個網(wǎng)絡(luò)的鏈路進(jìn)行準(zhǔn)確描述，定義鏈路代價函數(shù)（一般可由信道容量、信道利用率或報文延遲時間這幾種因素確定），計算最短路徑,建立路由選擇表或路由數(shù)據(jù)庫。根據(jù)網(wǎng)絡(luò)拓?fù)浜妥泳W(wǎng)款式選擇適當(dāng)算法，并設(shè)計出實現(xiàn)算法的過程，模擬測試和運行。其中計算最短路徑是整個設(shè)計過程中較為關(guān)鍵的一環(huán)。多播路由選擇要保證實現(xiàn)的目標(biāo)是，數(shù)據(jù)能夠到達(dá)所有的接收者。同時，在整個通信網(wǎng)絡(luò)的任

4、何一條鏈路上數(shù)據(jù)最多傳送一次。在一條鏈路上是否傳輸數(shù)據(jù)依賴于此鏈路上是否有該數(shù)據(jù)的接收者。多播之所以能節(jié)約帶寬,就是因為在網(wǎng)絡(luò)的任何一條鏈路上數(shù)據(jù)最多傳送一次。要實現(xiàn)這個目標(biāo)，多播的傳輸就不能像單播一樣點到點地傳輸，而要采用樹的傳輸方式。一般采用多播生成樹來描述多播數(shù)據(jù)包在網(wǎng)絡(luò)中經(jīng)過的路徑。將多播路徑基于樹結(jié)構(gòu)有兩點理由：(1)信息可以沿著樹枝并行地傳送至懷同的目的地；(2)僅在樹叉處復(fù)制信息，傳送信息的拷貝數(shù)最小，從而使網(wǎng)絡(luò)流量最｛氐，占用的網(wǎng)絡(luò)資源最少。多播樹的質(zhì)量評價一般有兩個尺度，最短路徑和最小

5、代價。最短路徑和最小代價可以被表述為不同的函數(shù)，如最小代價可以表述為使用緩沖區(qū)的數(shù)量、占用信道的所需交納的費用，包丟失率等;最短路徑可以表述為傳輸、處理、排隊時延的結(jié)合。多播生成樹算法沿著優(yōu)化這兩個尺度(最短路徑和最小代價)的方向,己經(jīng)有了很大的發(fā)展。2.多播生成樹問題的圖論基礎(chǔ)2?1?樹給定一個圖G=(V,E),如果它不含任何回路，我們就叫它是林，如果G又是連通的，即這個林只有一個連通支，就稱它是樹。樹是圖論中最重要的概念之一，在自然和社會科學(xué)中的許多領(lǐng)域都有廣泛的應(yīng)用。定義1?不含田可回路的連通圖稱

6、為樹，用T表示。T中的邊稱為樹枝，度為1的結(jié)點稱為樹葉。樹的每條邊都不會屬刊北可回路。這樣的邊叫割邊。定義2設(shè)e是圖G的一條邊,若G、=G-e比G的連通支數(shù)增加，則稱e是G的一條割邊。顯然圖G刪去割邊=0(u,v)之后結(jié)點u和v分屬于不同的連通支。定理1e=(u,v)是割邊，當(dāng)且僅當(dāng)e不屬于G的田可回路。定理2設(shè)T是結(jié)點數(shù)為n>2的樹，則下列性質(zhì)等價：1.T連通且無回路。2T連通且每條邊都是割邊。3.T連通且有條邊。4.T有n-1條邊且無回路。5.T的任意兩結(jié)點間有唯一道路。6.T無回路，但在任兩結(jié)點間

7、加上一條邊后恰有一個回路.定理3樹T中一定存在樹葉結(jié)點。定義3如果T是圖G的支撐子圖，而且又是一棵樹，則稱r是G的一棵支撐樹，或稱生成樹，又簡稱為G的樹。2?2?多播網(wǎng)絡(luò)模型為簡化對問題的討論，我們通常將一個通信網(wǎng)絡(luò)表示為一個帶權(quán)無向圖G=(V,E,C),其中V代表網(wǎng)絡(luò)中結(jié)點(Node)的集合;E是一組邊(edge)的集合,

8、V

9、和

10、E

11、分別代表結(jié)點和邊的數(shù)目。每條邊用對應(yīng)的兩個結(jié)點u,v來表示:(u,v)—對結(jié)點對應(yīng)的兩條邊口(")和(3)費用相等，即這兩條邊對稱;C是各邊對應(yīng)費用(cost)的集合。

12、圖G中結(jié)點v的度(degree)是指與v關(guān)聯(lián)的邊的條數(shù)。在多播網(wǎng)絡(luò)中數(shù)據(jù)包由源結(jié)點seV生成,并發(fā)送給所有的多播組成員，多播組成員結(jié)點他稱為端結(jié)點)的集合McV。由無向圖G=(V,E,C)中生成一棵有向樹T=(%,址)若滿足以下三個條件則稱其為多播生成樹：^)VtQVfEtQEo2)源結(jié)點S到每一個端結(jié)點都有通路，并且S的入度為0。，樹中其余結(jié)點的入度為1。3)端結(jié)點的出度大于或等于0,其余結(jié)點的出度均大于或等于1。一棵多播樹T的總費用是指