不确定图中的最短路径树算法研究

发布时间：2020-08-28 04:42

【摘要】：在通信网络中,组播是一种重要的通信方式,是一种一对多的连接类型的通信方式。随着网络技术的发展,组播在分布式系统、视频点等多媒体业务中得到广泛的应用。实现组播的关键是选择合理的组播算法构造一颗组播树。我们使用一个带权的无向图来表示通信网络,图中边的权值表示两个结点之间通信时的消耗,组播树其实就是带权无向图中的最短路径树。然而,在通信网络中,由于某些原因会导致结点间的物理链路断开或数据丢失,这时我们不仅需要选择新的组播树来保证信号源点到每个结点间的链路通畅和数据完整,而且还要保证整个的通信费用最小,因此最短路径树在不确定图中的研究具有十分重要的意义。本文主要对不确定图中的最短路径树算法进行深入研究,并获得如下进展:(1)因为不确定图中的边存在不确定性,所以在研究不确定图中最短路径树问题时已经不能使用确定图中的方法,我们提出了不确定图中的最短路径树概念,并在此基础上给出了最优最短路径树概念。最优最短路径树是指权值最小的最短路径树。我们借助边变换思想设计了不确定图中最优最短路径树算法,算法主要通过不断换入权值小的边来共享路径,进而降低最短路径树的权值,最终得到最优最短路径树,然后通过减少边变换判断次数可以有效的提高该算法的运行效率。(2)对最短路径树在不确定图中的可靠性进行了分析。所有可靠蕴含图的可靠性的和就是最短路径树的可靠性,并提出了一种新的计算方法来计算最短路径树的可靠性,在此基础上我们给出了最可靠最短路径树的概念。最可靠最短路径树是指不确定图中可靠性最高的最短路径树。我们借助边变换思想设计了不确定图中最可靠最短路径树算法。算法主要通过不断换入存在概率高的边来提高最短路径树的可靠性,进而得到最可靠最短路径树,然后通过减少边变换判断次数可以有效的提高该算法的运行效率。最后,通过对实例进行分析和相关的实验验证,证明了最优最短路径树算法和最可靠最短路径树算法的可行性,我们能够完全正确的得到问题的解。
【学位授予单位】：湘潭大学
【学位级别】：硕士
【学位授予年份】：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图,图G,不确定,蕴含图

∧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条边；每条边都有一个正整数的权值和边的存在概率值。不确定图G存在 23个蕴含图

不确定,图G,确定图,蕴含图

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。例如

【参考文献】