【摘要】：圖論作為數(shù)學的一個重要分支,在計算機科學中也扮演著非常重要的角色。隨著大數(shù)據(jù)時代的到來,圖數(shù)據(jù)的規(guī)模也隨之增大,因此圖算法的效率對于解決圖論問題至關重要。由于現(xiàn)實問題中可能會遇到很多的意外情況,如機器故障,信號傳輸?shù)牟环�(wěn)定性等,最終導致實際數(shù)據(jù)存在不確定性。因此不確定圖已經(jīng)成為一個非常熱門的研究領域。本文對不確定圖中的生成樹算法進行了研究,主要獲得了如下成果:(1)由于不確定圖的邊存在不確定性,所以傳統(tǒng)的最小生成樹定義已經(jīng)不能完全適用于不確定圖。因此提出了最優(yōu)生成樹的概念,它主要是在最小生成樹定義的基礎上增加了對概率的最優(yōu)化定義。然后我們借助貪心的思想設計了不確定圖中最優(yōu)生成樹算法。(2)為了能夠找到不確定圖中的所有關鍵邊,我們設計了Top-K最小生成樹算法,并提出了基于并查集的優(yōu)化算法和基于啟發(fā)式搜索的優(yōu)化算法。當值較小時,基于啟發(fā)式搜索的優(yōu)化算法具有明顯的優(yōu)勢。(3)對最小生成樹在不確定圖中的可靠性進行了分析。將可靠性定義為所有包含最小生成樹的蘊含圖的存在概率之和,主要使用了邊集劃分的方法將所有蘊含圖進行歸類,在同一類中的蘊含圖具有相同的最小生成樹,通過求同一類中所有蘊含圖存在的概率來獲得不確定圖的可靠性。(4)針對不確定有向圖,給出了最優(yōu)樹形圖的定義,設計了最優(yōu)樹形圖算法。最后將TOP-K最小生成樹算法的思想和最優(yōu)樹形圖的性質相結合設計了TOP-K最小樹形圖查詢算法。最后,我們對不確定圖中生成樹的研究進行了相關的實驗驗證,實驗結果表明,設計的算法的運行效率與理論分析基本一致,且能夠完全正確的得到問題的解。
[Abstract]:As an important branch of mathematics, graph theory also plays a very important role in computer science. With the arrival of big data era, the scale of graph data increases, so the efficiency of graph algorithm is very important to solve graph theory problem. Many unexpected situations may be encountered in practical problems, such as machine failure, instability of signal transmission and so on, resulting in uncertainty of actual data. Therefore, uncertainty graph has become a very popular research field. In this paper, the spanning tree algorithm in uncertain graphs is studied. The main results are as follows: (1) because of the uncertainty in the edges of uncertain graphs, the traditional definition of minimum spanning tree can no longer be fully applied to uncertain graphs. Therefore, the concept of optimal spanning tree is proposed, which mainly adds the optimal definition of probability on the basis of the definition of minimum spanning tree. Then we design the optimal spanning tree algorithm in uncertain graph with greedy idea. (2) in order to find all the key edges of uncertain graph, we design the Top-K minimum spanning tree algorithm. An optimization algorithm based on parallel search set and an optimization algorithm based on heuristic search are proposed. When the value is small, the heuristic search based optimization algorithm has obvious advantages. (3) the reliability of the minimum spanning tree in uncertain graphs is analyzed. The reliability is defined as the sum of the existential probability of all the implied graphs containing the minimum spanning tree. The edge set partition method is mainly used to classify all the implied graphs, and the implied graphs in the same class have the same minimum spanning tree. The reliability of uncertain graphs is obtained by finding the probability of the existence of all implicit graphs in the same class. (4) for uncertain digraphs, the definition of optimal tree graphs is given, and an optimal tree graph algorithm is designed. Finally, the idea of TOP-K minimum spanning tree algorithm and the properties of the optimal tree graph are combined to design the TOP-K minimum tree graph query algorithm. Finally, the experimental results show that the efficiency of the proposed algorithm is consistent with the theoretical analysis, and the solution of the problem can be obtained correctly.
【學位授予單位】：湘潭大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：O157.5

【相似文獻】

相關期刊論文 前3條

1 胡楓,于福溪;最小生成樹算法在多元連接中的應用及算法分析[J];青海師范大學學報(自然科學版);2004年02期

2 程媛媛;;基于Prim最小生成樹算法的時間成本研究[J];河北北方學院學報(自然科學版);2013年06期

3 ;[J];;年期

相關會議論文 前1條

1 周惠巍;黃德根;高潔;楊元生;;最大生成樹算法和Nivre算法相結合的中文依存關系解析[A];中國計算語言學研究前沿進展（2009-2011）[C];2011年

相關重要報紙文章 前1條

1 ;最偉大的網(wǎng)絡技術發(fā)明者[N];網(wǎng)絡世界;2007年

相關碩士學位論文 前2條

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

2 楊寅;社會網(wǎng)絡分析工具中的分布式最小生成樹算法[D];北京郵電大學;2011年

，

本文編號：2273938