论文部分内容阅读
随着信息技术的飞速发展、交互型模式及城市数字信息化应用水平的不断提升,智慧城市应运而生,同时对网络安全的要求也更高.网络可靠性是衡量网络安全的重要参数之一,其在许多领域扮演着越来越重要的角色,如国防、经济、教育等.因此,网络可靠性的研究具有重要的理论意义和应用价值.本文主要讨论边失效下二终端网络模型的可靠性.定义一个二终端图G为具有两个目标顶点s和t的无向简单图,并假设其每条边都以统计概率p ∈[0,1]独立存活,而二终端可靠度R2(G,p)即为计算这两个目标顶点之间连通的概率.研究结果显示,具有n个顶点m条边的所有二终端图构成的集合Ω(n,m)中并不总是存在一致最优图,即对于所有p∈[0,1],Ω(n,m)中不存在满足R2(G,p)≥R2(H,p)的图G,其中H为Ω(n,m)中的任意一个图,故对于这类图考虑其他的衡量全局可靠性的指标是必要的,如极优图和平均可靠度.对于给定的点数n和边数m,若存在a个图G1,G2,…,Ga,对任意的G∈Ω(n,m)总有一个图Gi(1≤i≤a)满足R(G,p)≥R(G,p),则这a个图就构成了图簇Q(n,m)的极优图集.而平均可靠度则为可靠度在区间[0,1]上的均值.首先,本文应用极优图的概念并结合集合论的知识确定了二终端图簇Q(n,n(n-1)/2-2)和Q(n,n(n-1)/2-3)中的最小极优图集,其集合基数分别为2和5.引入极优图的概念其主要目的是在网络设计过程中,选择极优图集中的某一结构将其作为网络设计的拓扑结构,较其他结构,该结构具有最优的含义,其为构造最优网络结构提供了理论依据.其次,本文首次研究了二终端平均可靠度,证明了其计算是#P-Hard问题,并给出了二终端平均可靠度的一个上界.另外,定义平均可靠度最优图为图簇Ω(n,m)中平均可靠度最大的图,作为应用,本文确定了图簇Ω(n,n(n-1)/2-2)和Q(n,n(n-1)/2-3)中的平均可靠度最优结构.