张昭[1]2003年在《网络可靠性研究：图的高阶连通性》文中研究说明随着信息网络的飞速发展，许多与之相关的理论性问题越来越引起人们的重视，其中之一即为网络可靠性，对称性在网络设计中也非常重要，因为对称网络具有许多我们所期望的性质。网络往往被模型化为图。衡量网络可靠性的经典参数为图的连通度和边连通度。为了进一步的研究，人们提出了各种各样的高阶连通性概念，如super-κ性，hyper-κ性，超边连通性，r-限制性边连通度等。本论文主要利用图的高阶连通性研究网络(特别是对称网络)的可靠性。 第一章中介绍了研究背景和一些基本结果。第二章中，我们研究高阶边连通度，得到了如下结果：(a)除了叁个特殊图外，所有具有有限跃阶的无限循环图都是超边连通的；(b)除了叁种特殊图类外，所有边传递图都是最优-λ~(3)图；(c)刻划了点传递图的最优-λ~(3)性，特别是给出了Cayley图和极小Cayley图为最优-λ~(3)图的充分必要条件；(d)给出了一个图(不一定是对称图)是最优-λ~(3)图的一种充分条件。在第叁章中，我们研究高阶点连通性，得到如下结果：(a)刻划了边传递图的super-κ性和hyper-κ性；(b)定义了一种新的网络可靠性度量标准：semi-hyper-κ性，并给出了边传递图为semi-hyper-κ图的充要条件。在最后一章中，我们使用高阶边连通度的结果研究对称图中树分解的一个问题，给出了森林数等于树数的一个充分条件。 在高阶连通性的研究中，能否得到(边)原子的无交性是关键，也是证明的难点。而成功地应用高阶边连通性证明树分解中的问题，使我们进一步寻找高阶连通性在其它图论问题中的应用。
李向军[2]2013年在《某些网络容错性研究》文中研究表明互连网络在并行计算和通信系统中发挥着重要作用.网络的容错性是评价互连网络性能的关键指标,它主要考虑在网络发生故障的时候网络中某些特有性质的保持能力.本文主要以图论作为工具研究故障出现时网络保持叁种性质的能力：多对多不交长路存在性,连通分支最小度,连通分支子网络结构.在研究中,本文利用高对称网络在不同维度上分解的等价性,探索出一套分析网络容错性的有效方法,解决了几个悬而未决的问题.本文第一章介绍所考虑问题的研究背景以及文章用到的图论主要概念.本文第二章主要考虑出现顶点故障超立方体Qn中的k条多对多不交路问题.在考虑条件容错的前提下,证明故障点数.f不超过2n-2k-3时,对于Qn中在不同部的两个k-点集合S与T,存在至少含有2n-2f顶点的k条顶点不交的无故障路连接S与T.这个结果改进了很多已知的结论.本文的第叁、四章主要分析类超立方体和星图的容错性能.理论上讲,类超立方体和星图具备成为互连网络拓扑结构的很好潜质,是超立方体的强有力的竞争网络.本文在第叁章中确定了类超立方的高阶限制边连通度和高阶嵌入限制边连通度,对于点的情形确定了超立方体、Mobius立方、交叉超立方体的高阶限制连通度和高阶嵌入限制连通度.本文在第四章确定了星图网络的高阶限制点(边)连通度和高阶嵌入限制点(边)连通度,其中对星图高阶限制点连通度的确定证实了同行学者提出的猜想.本文的第五、六章主要分析广义星图网络和交换超立方体的高阶限制连通性.广义星图网络是星图的网络的推广,它的变化更加灵活,受到了很多学者的关注.交换超立方体是超立方体的另外一种变形,它由超立方体系统的删去一些边得到,具有一些很好的性质,同时降低了连接复杂性.本文在第五、六章分别确定广义星图网络和交换超立方体的高阶限制点连通度和高阶限制边连通度.
陈淑苹[3]2012年在《混合Cayley图的连通性，哈密尔顿性和谱》文中研究说明最近几十年，信息浪潮席卷全球，信息化的高速发展给人类的生活带来了极大的方便，而计算机信息网络作为全球信息化的重要载体，它的研究显得非常重要，在图论这个领域涉及到信息网络的研究中，最重要的就是网络可靠性问题的研究，网络可靠性研究的核心问题是通信网络的可靠性分析和高可靠性能网络的设计。在我们的研究中，我们把网络拓扑结构模拟成一种图，而图作为网络拓扑结构的一种有效模型，图的各种性质首当其冲的被先后用来研究网络的可靠性问题。Cayley图是一种典型的网络结构模型，混合Cayley图是在Cayley图和二部Cayley图的基础上研究出来的更具有普遍性的一种模型，因此更具有研究意义。本论文的叁个性质都是衡量网络可靠性的经典参数。目前国内外同行还没有对此类图做过研究，因此具有较高的研究价值。在第一章中,简要的介绍本论文的研究背景。在第二章中,混合Cayley图是Cayley图和二部Cayley图的推广和延伸，基于Cayley图和二部Cayley图的连通性研究的方法,我们得到了当混合Cayley图连通时的充要条件：G_是有限的可交换群，G_0=S_0,G_1=S_1,G_=S_122S_2,则混合Cayley图X=MC (G, S_0, S_1, S_2)连通的充要条件是G_=G_0G_1G_2。在第叁章中,基于对称群上Cayley图的哈密尔顿性和有限交换群上二部Cayley图的哈密尔顿性的研究，我们研究了循环群上混合Cayley图的哈密尔顿性:设G是循环群，G_≥2, S_i G, i=(0,1,2)，1G_∈S_2,S_i~(-1)=S_i，当S_0=S_1,则连通的混合Cayley图MC (G_, S_0, S_1,S_2)是哈密尔顿性的。在第四章中，基于Cayley图的相邻矩阵，得到Cayley图的谱，根据Cayley图与二部Cayley图的联系，得到了二部Cayley图的谱，由此方法，我们在本章中推出了混合Cayley图的谱:设λ_1, λ_2, L,λ_n是Cayley图C (G,S_0)的特征值，设κ_1, κ_2, L,κ_n是二部Cayley图BC (G_,S_1)的特征值，如果C (G,S_0)和C (G,S_1)的邻接矩阵是正规的和可交换的，则混合Cayley图MC (G, S_0, S_1,S_2)的相邻矩阵的特征值是κ_1±λ_1，κ_2±λ_2, L,κ_n±λ_n。
刘娟[4]2009年在《图与有向图的高阶连通性》文中进行了进一步梳理随着信息网络的飞速发展,许多相关的理论问题开始引起人们的重视,其中之一是网络的可靠性,即网络在它的某些部件(节点或者连接)发生故障的条件下仍能正常工作的能力.网络拓扑结构通常被模型化为图或有向图,因此,图论中的一些经典概念,如连通度和边(弧)连通度,就被用来研究网络的可靠性.为了进一步研究相关内容,人们提出了各种各样的高阶连通性的概念,如super-κ性(super-λ性)、限制性边连通性、超限制性边连通性等.本文主要研究某些特殊图类的各种连通性问题.第一章,我们介绍了研究背景和一些基本概念,给出了有向图的线图、Cartesian积、Lexicographic积等的定义.对各类连通度问题研究的历史与现状进行了一定程度的综述.最后介绍了本文的研究内容和主要结果.第二章,我们根据图的局部边连通度定义了图的局部限制性边连通度以及图的最优局部限制性边连通性,证明了一些图类下已知图是最优限制性边连通的充分条件仍能保证图是最优局部限制性边连通的.第叁章首先研究了两个无向图的Cartesian积的超限制性边连通性、两个有向图的Cartesian积的super-λ及super-κ性.其次根据全变换图的概念给出了全变换有向图的概念,研究了其中两类全变换有向图以及中间有向图的super-λ及super-κ性.本章最后一节研究了完全二部有向图的迭代线图的一些性质.第四章主要定义了有向图的双超连通性,并且刻划了一些特殊图类,比如说, Abelian Cayley有向图、有向图的线图、Cartesian积及Lexicographic积的双超连通性.
谢茜[5]2011年在《双轨道图的边连通性》文中认为近年来,随着互联网络的飞速发展,网络性能自然引起人们的关注。互联网络的拓扑结构对网络的性能有着决定性的影响。在设计多处理器的网络拓扑时,人们最关心的问题是网络可靠性,即网络在它的某些部件(节点或者连接)发生故障的条件下仍然能够正常工作的能力。多处理器的互联网络拓扑通常被模型化为图。因此,图论中的一些经典概念,如连通度和边连通度,就被用来研究网络的可靠性。为了更精确地度量网络可靠性,人们提出了各种各样的高阶连通性的概念,如super-λ性(super-κ性)、hyper-λ性(hyper-κ性)、限制边连通性、超限制边连通性等等。本文主要研究正则双轨道有向图的弧连通性问题和正则双轨道图的超边连通性问题。第一章,我们介绍了研究背景和一些相关的基本概念,并对各类边连通问题的研究与现状进行了一定程度的回顾。第二章,我们研究了正则双轨道有向图的弧连通性问题,证明了对给定正整数m,k (1 < m k)存在正则度为k,弧连通度为m的双轨道有向图,进一步地,给出了一个连通的正则双轨道有向图是极大弧连通的充分条件。第叁章,研究了正则双轨道图的超边连通性问题,主要结果是证明了一个连通且围长g(G) 6的正则双轨道图是超边连通的。
靳艳军[6]2007年在《图的笛卡尔积及字典式积的连通性》文中研究表明随着信息网络的飞速发展，许多与之相关的理论性问题越来越引起人们的重视，其中之一即为网络可靠性。通信网络的可靠性分析与高可靠性能网络的设计问题是可靠性研究的核心。图作为网络拓扑结构最有效模型，图的各种连通性指标被先后用来研究网络可靠性问题。通常情况下，网络是连通的，从而代表它的图也是连通的，也就是说，图中任意两点间都存在一条路。但是，有时网络的某个元素被破坏，也就是其对应的图被去掉一些边和点时。这时我们希望被破坏的网络尽可能的连通。图的经典参数边连通度λ(G)是指要使得一个图不连通所需要去掉的最少的边数，点连通度κ(G)是指要使得一个图不连通所需要去掉的最少的点数。边连通度和点连通度是衡量网络可靠性的一个重要参数。作为经典连通度的推广，人们提出了高阶的连通度，例如极大(边)连通的，上(边)连通的，超连通的等。另一方面，笛卡尔积和字典式积是从一些较小的图来构造较大的图的一种有效的方法，从而在设计网络和分析网络方面有着重要的作用。在本文中，主要是研究图的笛卡尔积和字典式积的高阶连通性的问题。我们给出了两个图的笛卡儿积及字典式的积为max-λ，max-κ，super-λ，super-κ及hyper-κ的充分条件，同时证明了其中一些条件也是必要的。此外，对这两种积的局部割集和广义割集的性质也进行了考虑。对于两个图的笛卡尔积，我们有以下的主要结果：(1)如果G_1和G_2是极大边连通的，则G_1×G_2是极大边连通的。(2)假设λ_i≥2或λ_1=1，2≤λ_2＜n-1。如果G_1和G_2是极大边连通的，则G_1×G_2是上边连通的。(3)如果G_1和G_2是极大连通的，则G_1×G_2是极大连通的。(4)假设κ_i≥2或κ_1=1，2≤κ_2＜n-1。如果G和G是极大连通的，则G_1×G_2是上连通的。(5)假设κ_i≥2或κ_1=1，2≤κ_2＜n-1。如果G和G是极大连通的，则G_1×G_2是超连通的。(6)若G_1，G_2满足下列条件之一，则有G_1×G_2的每一个最小广义割集都是一个局部割集：(a) G和G是极大连通的，并且δ(G_1)≥2和δ(G_2)≥2，(b) G_1(?)K_2，2≤δ(G_2)＜n-1并且G_2(?)K_3。对于两个图的字典式积，我们有以下的主要结果：(1)如果X和Y是极大边连通的，则X[Y]是上边连通的。(2) X[Y]是极大连通的当且仅当X是完全图并且Y是极大连通的。(3) X[Y]是上连通的当且仅当X是完全图并且Y是上连通的。(4) X[Y]是超连通的当且仅当X是完全图并且Y是超连通的。(5)如果X是完全图，并且Y的每一个最小广义割集都是一个局部割集，则X[Y]的每一个最小广义割集都是一个局部割集。
韩龙美[7]2017年在《基于复杂网络理论的能源互联网通信可靠性分析》文中认为在全球能源消费需求持续增长的背景下,资源枯竭与环境污染的双重压力给经济社会发展带来了严峻的挑战。近年来,国内外对智能电网的建设趋于成熟,为电力能源的高效利用提供了技术基础。然而,随着可再生能源的广泛发展以及电气化交通网络的接入,电力网络面临着前所未有的发展瓶颈,主要表现在系统的稳定性与可靠性受到挑战。在此背景下,能源互联网(Energy Internet)的概念随之而出,在我国,能源互联网依托于传统骨干电网,接入大规模的可再生能源系统、即插即用电动汽车,并融合了交通网络与天然气网络等,是一个具有高度灵活性与实时性的复杂网络,其可靠性的要求也相对提高。近年来,复杂网络理论在复杂系统的研究中有了重大突破。基于复杂网络理论研究电力通信网络的可靠性也日渐兴起,对于传统的电网研究方法来说是一个重大的突破;相比较于传统的电力通信网络,能源互联网的通信网络是更复杂的网络,更适合运用复杂网络理论来研究,因此,本文拟将复杂网络理论运用在能源互联网通信网络的可靠性分析中。本文首先研究了复杂网络理论的基本概念及其特征参数,然后分析了未来能源互联网的基本特征及其通信网络所具有的小世界特性与无标度特性。接着,本文给出了一种对可靠性分层分析然后整体评估的可靠性研究方法,来分析能源互联网通信网络可靠性,其中,对于拓扑结构层可靠性采用了抗毁性、生存性相结合的方法分析。在此基础上,本文对所给出的能源互联网通信网络拓扑结构的模型进行了仿真模拟;并将此网络模型与互联网AS级拓扑和美国电力通信网络拓扑从复杂网络层面进行了各项参数比较,从而得出本文的网络模型与互联网有若干相似特性,比传统电力通信网络更符合网络通信的要求。最后,将本文的能源互联网通信模型与某省电力通信网在随机攻击与蓄意攻击两种形式下,从抗毁性和生存性方面进行了可靠性的分析比较,得出该能源互联网通信网络模型比该省电力通信网更可靠。
周小佳[8]1997年在《电力系统可靠性人工神经网络模型及实现研究》文中指出本文是作者论文工作结合“人工神经元网络在电网可靠性管理中的应用”等多个重大项目研究的成果总结。它主要研究了运用神经网络进行图最小割集搜索的方法及其实现技术,将该方法和技术运用于电网可靠性评估分析之中,缓和了电网可靠性分析中存在的“计算灾难”问题,为实现电网可靠性的实时、在线分析和计算提供了有力的工具和可靠的依据。本文的主要工作归纳如下: 1.首次提出了支路可行流、薄弱度和薄弱域的概念,证明了搜索网络K次薄弱割集及其薄弱度的DASWA算法的正确性,为分析网络薄弱程度和范围提供了科学的依据。 2.在研究人工神经元网络理论基础之上,提出了搜索图最小割集的神经网络模型——N-SearCut模型,证明了该模型的稳定性,分析了该模型的动态特性,导出了一系列的定理,为运用该模型进行优化问题的求解提供了理论依据。 3.通过对电网最小割集搜索原则的分析,提出了热量平衡法HBM,论证了利用该方法判断一个网络图连通性能的可行性和正确性。将其运用于N-SearCut模型对图的最小割集搜索之中,发展了N-SearCut模型的应用前景,提高了该模型的实际工程价值。 4.提出了N-SearCut神经网络模型软件实现的NNCS算法和NNSP算法,给出了具体的实现步骤,并通过利用NNSP算法对IEEE24节点可靠性试验系统的可靠性计算表明该算法在一定程度上缓和了电网可靠性分析中存在的“计算灾难”问题。 5.提出了运用N-SearCut神经网络模型搜索图最小割集的全硬件实现方法,为更理想地解决网络可靠性评估中出现的最小割集搜索这一瓶颈问题提出了新的思路,提供了理论和实践依据。 6.提出了通过商业化的神经计算系统来实现利用N-SearCut神经网络模型进行网络最小割集搜索的实现方案,使N-SearCut神经网络模型能真正运用于实际工程中,为网络可靠性分析中出现的瓶颈问题找出了一条较理想的解决途径,使电力系统可靠性评估技术得以充分地发展。 7.在软件设计的开放性、可靠性及面向对象叁大要素基础上,根据系统工作原理和可靠性计算要求开发研制出了电网可靠性综合管理系统——ESMIS系统,使其在运用N-SearCut神经网络模型实现方法基础之上,实现了电网的可靠性综合管理,为实际电网可靠性的计算和管理提供了科学的依据和可行的工具。
尚莉[9]2008年在《图的高阶限制边连通度》文中研究说明图的边连通度和超边连通性常用来度量网络的可靠性，但是当两个图具有相同的边连通度和超边连通性时，就无法对其可靠性进行比较．因此，为了更精确地度量网络可靠性，人们提出了m-限制边连通度的概念：设m是正整数，连通图G的边割S称为m-限制边割，如果G-S的每个连通分支都至少包含m个顶点：G中最小m-限制边割的基数称为图G的m-限制边连通度，记为λ_m(G)．当m=2时，λ_2(G)称为图G的限制边连通度，通常记为λ_'(G)．如果λ_m(G)存在，则称G是λ_m-连通图．目前，关于m-限制边连通度方面的研究，主要集中在讨论m-限制边连通度的存在性及上界，计算特殊图类或网络的m-限制边连通度，寻求分别具有极大m-限制边连通度和较少最小m-限制边割数的图类等方面．令ξ_m(G)：=min{|[X,X]|：X(?)V(G),|X|=m，且G[X]连通}．如果图G的m-限制边割S=[X，X]满足|X|=m或|X|=m，则称S是平凡的．设λ_m-连通图G满足λ_m(G)≤ξ_M(G)，如果λ_m(G)=ξ_M(G)，则称G是最优m-限制边连通图，简称λ_m-最优图；如果G的每个最小m-限制边割都是平凡的，则称G是超级m-限制边连通图，简称超-λ_m连通图．一般来说，λ_m-最优图和超-λ_m连通图具有较高的可靠性．本文共分五章，第一章综述m-限制边连通度的应用背景及研究进展，介绍本文用到的一些基本概念，术语和记号，并概述本文的研究内容及获得的主要结果．第二章主要研究满足λ_m(G)≤ξ_m(G)的一个一般充分条件．已经证明，当m≤3时，λ_m-连通图G具有λ_m(G)≤ξ_m(G)这一性质．当m≥4时，Bonsma等人指出不等式λ_m(G)≤ξ_m(G)一般不再成立．欧见平于2007年证明阶大于等于11的λ_4-连通图G满足λ_4(G)≤ξ_4(G)．本章我们通过研究满足λ_m(G)>ξ_m(G)的λ_m-连通图所具有的结构性质，不仅易得欧见平的以上结论，而且还得到了如下结论：当m≥5时，阶大于m(m-1)的λ_m-连通图G均满足λ_m(G)≤ξ_m(G)．最后，通过构造例子来说明我们给出的条件是最好的．第叁章主要研究图的最优限制边连通性．给出并证明一般图，二部图，以及直径为2的图分别是λ'-最优图的充分条件，同时通过构造例子来说明这些条件不能被减弱．本章得到的结论是对Hellwig与Volkmann 2004和2005年相应结论的改进，其中关于直径为2图的λ'-最优性结论是对王应前和李乔1999年结论的进一步推广．第四章主要研究图的超级限制边连通性．给出并证明一般图，二部图，无叁角形图，以及直径为2的图分别是超-λ'连通图的充分条件，并用例子说明这些条件是最好的．本章所得的结论推广了王应前和李乔2001年的结论．而关于直径为2图的超-λ'连通性，在不含叁角形的条件下，我们得到的推论与王世英和林上为2007年的结论类似，并且推广了范英梅2003年的结论．第五章主要研究图的λ_3-最优性和超-λ_3连通性．首先讨论λ_3-最优与λ'-最优和超-λ'连通之间的关系．然后给出并证明一般图，二部图，无叁角形图，以及直径为2的图分别是λ_3-最优图和超-λ_3连通图的充分条件，并通过构造例子来说明这些条件不能被减弱．最后证明最小度δ≥2m的超-λ_m连通非完全图所具有的一个结构性质：G的最小度顶点集M的导出子图G[M]不含完全子图K_(δ-m+1)．本章中，我们把欧见平2003年关于无叁角形正则图的λ_3-最优性结论推广到一般图．另外，关于直径为2图的λ_3-最优性和超-λ_3连通性，我们所获得的结论推广了王应前2006年的相应结论．
刘清海[10]2009年在《图的高阶连通性》文中进行了进一步梳理随着信息网络的飞速发展,许多相关的理论问题开始引起人们的重视,其中之一是网络的可靠性,即网络在它的某些部件(节点或者连接)发生故障的条件下仍能工作的能力.网络拓扑结构通常被模型化为图或有向图,因此,图论中的一些经典概念,如连通度和边连通度,就被用来研究网络的可靠性.为了进一步研究,人们提出了各种各样的高阶连通性的概念,如super-κ性、hyper-κ性和κ-限制性边连通度λ_κ等.本文主要研究各种连通性问题.本文共分四章.第一章,我们介绍了研究背景和一些基本概念.对各类连通度问题研究的历史与现状进行了一定程度的综述.第二章,我们用围长和直径给出了λ_κ-最优图的一个充分条件,并且这个条件是对前人结果的一个改进.第叁章,我们求出了Harary图的所有可能的λ_κ和ξ_κ,由此完全刻画了Harary图的λ_κ-最优性.第四章,我们研究限制性点连通度κ_κ和κ'_κ,其中κ'_κ为我们定义的一类新的图参数,可以做为hyper-κ性的一种度量,并给出了κ_κ和κ'_κ的存在性和上界的一些充分条件以及两种限制性点连通度的性质和关系.
参考文献：
[1]. 网络可靠性研究：图的高阶连通性[D]. 张昭. 新疆大学. 2003
[2]. 某些网络容错性研究[D]. 李向军. 中国科学技术大学. 2013
[3]. 混合Cayley图的连通性，哈密尔顿性和谱[D]. 陈淑苹. 湖北师范学院. 2012
[4]. 图与有向图的高阶连通性[D]. 刘娟. 新疆大学. 2009
[5]. 双轨道图的边连通性[D]. 谢茜. 新疆大学. 2011
[6]. 图的笛卡尔积及字典式积的连通性[D]. 靳艳军. 新疆大学. 2007
[7]. 基于复杂网络理论的能源互联网通信可靠性分析[D]. 韩龙美. 华北电力大学. 2017
[8]. 电力系统可靠性人工神经网络模型及实现研究[D]. 周小佳. 重庆大学. 1997
[9]. 图的高阶限制边连通度[D]. 尚莉. 兰州大学. 2008
[10]. 图的高阶连通性[D]. 刘清海. 新疆大学. 2009
标签：数学论文; 有向图论文; 超立方体论文; 网络模型论文; 可靠性分析论文; 连通图论文; 网络图论文; 通信论文; 可靠性论文; 充分条件论文;