【摘要】：在通信網絡中,組播是一種重要的通信方式,是一種一對多的連接類型的通信方式。隨著網絡技術的發(fā)展,組播在分布式系統(tǒng)、視頻點等多媒體業(yè)務中得到廣泛的應用。實現(xiàn)組播的關鍵是選擇合理的組播算法構造一顆組播樹。我們使用一個帶權的無向圖來表示通信網絡,圖中邊的權值表示兩個結點之間通信時的消耗,組播樹其實就是帶權無向圖中的最短路徑樹。然而,在通信網絡中,由于某些原因會導致結點間的物理鏈路斷開或數(shù)據丟失,這時我們不僅需要選擇新的組播樹來保證信號源點到每個結點間的鏈路通暢和數(shù)據完整,而且還要保證整個的通信費用最小,因此最短路徑樹在不確定圖中的研究具有十分重要的意義。本文主要對不確定圖中的最短路徑樹算法進行深入研究,并獲得如下進展:(1)因為不確定圖中的邊存在不確定性,所以在研究不確定圖中最短路徑樹問題時已經不能使用確定圖中的方法,我們提出了不確定圖中的最短路徑樹概念,并在此基礎上給出了最優(yōu)最短路徑樹概念。最優(yōu)最短路徑樹是指權值最小的最短路徑樹。我們借助邊變換思想設計了不確定圖中最優(yōu)最短路徑樹算法,算法主要通過不斷換入權值小的邊來共享路徑,進而降低最短路徑樹的權值,最終得到最優(yōu)最短路徑樹,然后通過減少邊變換判斷次數(shù)可以有效的提高該算法的運行效率。(2)對最短路徑樹在不確定圖中的可靠性進行了分析。所有可靠蘊含圖的可靠性的和就是最短路徑樹的可靠性,并提出了一種新的計算方法來計算最短路徑樹的可靠性,在此基礎上我們給出了最可靠最短路徑樹的概念。最可靠最短路徑樹是指不確定圖中可靠性最高的最短路徑樹。我們借助邊變換思想設計了不確定圖中最可靠最短路徑樹算法。算法主要通過不斷換入存在概率高的邊來提高最短路徑樹的可靠性,進而得到最可靠最短路徑樹,然后通過減少邊變換判斷次數(shù)可以有效的提高該算法的運行效率。最后,通過對實例進行分析和相關的實驗驗證,證明了最優(yōu)最短路徑樹算法和最可靠最短路徑樹算法的可行性,我們能夠完全正確的得到問題的解。
【學位授予單位】：湘潭大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：TN915.0;O157.5
【圖文】：

如果圖中有 n 個頂點，則生成樹有 n-1 條邊。一個無向連通圖可能有多個生成樹。例如，在圖 2.4中，其中圖(b)和圖(c)都是圖(a)生成樹。圖2.4 無向連通圖以及它的生成樹2.2 不確定圖定義 2.9[48]（不確定圖）不確定圖是一個四元組G=(V , E , W , P)其中：（1） V 是頂點集；（2） E 是邊集；（3） W {w ( e )| e E , w( e ) N}+= ∈ ∈ 是邊的權重集；（4） P = { p ( e )| e ∈ E , p ( e) ∈ (0,1]}是邊存在可能性的集合。

∧G圖2.5 不確定圖G圖 2.6 圖 2.5 中不確定圖G的主確定圖定義 2.11 不確定圖 G =(V , E , W , P)的主確定圖 G = (V, E,W)的任意子圖G = (V ′, E ′, W ′), 其 中 V ′ V, E ′ E , W ′ W 稱 為 G 的 蘊 含 圖 （ implicatedgraph）。我們用 G G表示 G 是 G的蘊含圖，或 G蘊含 G 。蘊含圖的直觀意義是不確定圖在實際中的可能存在形式。注意，由于頂點之間的邊可能不存在，因此蘊含圖可能是不連通的。設Imp(G ) 表示不確定圖 G =(V , E , W , P)的全部蘊含圖的集合，由于邊的存才與否都是相互獨立的，則有|E||Imp(G ) | = |2 |。例如，在圖 2.5中的不確定圖G，有 3個頂點和 3條邊；每條邊都有一個正整數(shù)的權值和邊的存在概率值。不確定圖G存在 23個蘊含圖

9例如，圖 2.5 給稱一個不確定圖G，其中頂點為 v1,v2,v3邊 v1v2,v1v3,v2v3的權值為 5，4，6，實際存在的概率值為 0.4，0.9，0.7。定義 2.10[48]確定圖 G = (V,E,W)稱為不確定圖 G =(V , E , W , P)的主確定圖或主蘊含圖，記作∧G。例如

【參考文獻】

相關期刊論文 前10條

1 朱摂;鄒兆年;李建中;;不確定圖上的Top-k稠密子圖挖掘算法[J];計算機學報;2016年08期

2 張柏禮;楊娟;呂建華;田偉;;基于不確定圖的最可靠最大流的改進算法[J];東南大學學報(自然科學版);2015年02期

3 張柏禮;呂建華;生衍;田偉;;一種不確定圖中最可靠最大流問題的解決方案[J];計算機學報;2014年10期

4 鄒兆年;朱摂;;大規(guī)模不確定圖上的Top-k極大團挖掘算法[J];計算機學報;2013年10期

5 蔡偉;張柏禮;呂建華;;不確定圖最可靠最大流算法研究[J];計算機學報;2012年11期

6 李鳴鵬;鄒兆年;高宏;趙正理;;不確定圖上期望最短距離的計算[J];計算機研究與發(fā)展;2012年10期

7 張應龍;李翠平;陳紅;杜凌霞;;不確定圖上的kNN查詢處理[J];計算機研究與發(fā)展;2011年10期

8 張旭;何向南;金澈清;周傲英;;面向不確定圖的k最近鄰查詢[J];計算機研究與發(fā)展;2011年10期

9 韓蒙;張煒;李建中;;RAKING:一種高效的不確定圖K-極大頻繁模式挖掘算法[J];計算機學報;2010年08期

10 鄒兆年;李建中;高宏;張碩;;從不確定圖中挖掘頻繁子圖模式[J];軟件學報;2009年11期

相關碩士學位論文 前2條

1 唐杰;不確定圖中的生成樹算法研究[D];湘潭大學;2015年

2 魏真真;大規(guī)模不確定圖緊密子圖挖掘算法研究[D];燕山大學;2015年

本文編號：2807120