發(fā)布時(shí)間：2020-08-28 04:42

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

如果圖中有 n 個(gè)頂點(diǎn)，則生成樹有 n-1 條邊。一個(gè)無(wú)向連通圖可能有多個(gè)生成樹。例如，在圖 2.4中，其中圖(b)和圖(c)都是圖(a)生成樹。圖2.4 無(wú)向連通圖以及它的生成樹2.2 不確定圖定義 2.9[48]（不確定圖）不確定圖是一個(gè)四元組G=(V , E , W , P)其中：（1） V 是頂點(diǎn)集；（2） E 是邊集；（3） W {w ( e )| e E , w( e ) N}+= ∈ ∈ 是邊的權(quá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 的 蘊(yùn) 含 圖 （ implicatedgraph）。我們用 G G表示 G 是 G的蘊(yùn)含圖，或 G蘊(yùn)含 G 。蘊(yùn)含圖的直觀意義是不確定圖在實(shí)際中的可能存在形式。注意，由于頂點(diǎn)之間的邊可能不存在，因此蘊(yùn)含圖可能是不連通的。設(shè)Imp(G ) 表示不確定圖 G =(V , E , W , P)的全部蘊(yùn)含圖的集合，由于邊的存才與否都是相互獨(dú)立的，則有|E||Imp(G ) | = |2 |。例如，在圖 2.5中的不確定圖G，有 3個(gè)頂點(diǎn)和 3條邊；每條邊都有一個(gè)正整數(shù)的權(quán)值和邊的存在概率值。不確定圖G存在 23個(gè)蘊(yùn)含圖

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

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 朱摂;鄒兆年;李建中;;不確定圖上的Top-k稠密子圖挖掘算法[J];計(jì)算機(jī)學(xué)報(bào);2016年08期

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

3 張柏禮;呂建華;生衍;田偉;;一種不確定圖中最可靠最大流問(wèn)題的解決方案[J];計(jì)算機(jī)學(xué)報(bào);2014年10期

4 鄒兆年;朱摂;;大規(guī)模不確定圖上的Top-k極大團(tuán)挖掘算法[J];計(jì)算機(jī)學(xué)報(bào);2013年10期

5 蔡偉;張柏禮;呂建華;;不確定圖最可靠最大流算法研究[J];計(jì)算機(jī)學(xué)報(bào);2012年11期

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

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

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

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

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

相關(guān)碩士學(xué)位論文 前2條

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

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

本文編號(hào)：2807120