论文摘要
在设计计算机网络和通讯网络时，为了避免和最大限度减少因网络通讯中断而带来的损失，设计者必须考虑网络的稳定性．因此，网络设计的基本思想之一便是使其在受到外部攻击时，不容易被破坏；更进一步，如果真的受到破坏，它们也比较容易被修复重建．一个计算机网络或者通讯网络，可以用一个连通图来表示，其中图的顶点表示通讯站，边表示两个通讯站之间可以直接通讯的通讯线路．对于一个网络，它的稳定性常用它所对应的图的脆弱性参数描述． 早期在脆弱性参数方面的研究，主要是围绕连通度和边连通度展开的．这两个参数被广泛用来描述图的脆弱性，而且已被证明，它们的计算存在多项式时间算法．由于这两个参数在描述图的脆弱性方面具有局限性，近年来人们陆续引入了一些其它脆弱性参数，主要包括了坚韧度和边坚韧度，离散数，完整度和边完整度，粘连度和边粘连度，毁裂度，邻域连通度和边邻域连通度，邻域完整度和边邻域完整度，邻域离散数和边邻域离散数．与连通度和边连通度不同，这些参数不仅考虑了破坏网络的难易程度，还考虑了网络遭受破坏的程度． 本文主要研究了图的（边）邻域离散数、毁裂度、完整度和弱完整度等几个脆弱性参数，分五章讨论了以下几个问题： 第一章主要介绍了这些脆弱性参数的定义以及它们的研究背景、研究现状和本文的一些研究成果． 第二章主要讨论了一般图及连通二部图的邻域离散数的上下界，并证明了二部图邻域离散数的计算是一个NP-完全问题． 第三章主要讨论了一般图的边邻域离散数的界并给出了计算公式，构造了边邻域离散数意义下的最大网络，还证明了二部图边邻域离散数的计算是一个NP-困难问题． 第四章主要讨论了其它一些脆弱性参数如完整度、边完整度、弱完整度和毁裂度，给出了一些特殊图的脆弱性参数的计算公式及相互之间的关系，给出了顶点数和边数一定时毁裂度的最大值并构造了此时对应的网络图． 第五章主要介绍了关于图的脆弱性参数研究进一步可以做的研究工作．
论文目录
相关论文文献
标签：连通度论文; 边连通度论文; 完整度论文; 边完整度论文; 弱完整度论文; 毁裂度论文; 邻域连通度论文; 边邻域连通度论文; 邻域完整度论文; 边邻域完整度论文; 邻域离散数论文; 边邻域离散数论文; 二项式树论文; 二部图论文; 困难问题论文; 完全问题论文;