论文摘要
在设计计算机网络和通讯网络时,为了避免和最大限度减少因网络通讯中断而带来的损失,设计者必须考虑网络的稳定性。因此网络设计的基本思想之一便是使其在受到外部攻击时,不容易被破坏,更进一步,如果真的受到破坏,它们也比较容易被修复重建。一个计算机网络或者通讯网络,可以用一个连通图来表示,其中图的顶点表示通讯站,边表示两个通讯站之间可以直接通讯的通讯线路。对于一个网络,它的稳定性常用它所对应的图的脆弱性参数描述。 早期在脆弱性参数方面的研究,主要是围绕连通度和边连通度展开的。这两个参数被广泛的使用来描述图的脆弱性,而且已被证明,存在多项式时间算法计算一个图的连通度和边连通度。由于这两个参数在描述图的脆弱性方面具有局限性,近来人们陆续引入了一些其它的脆弱性参数,主要包括了坚韧度和边坚韧度,离散数,完整度和边完整度,粘连度和边粘连度,毁裂度,邻域连通度和边邻域连通度,邻域完整度和边邻域完整度,邻域离散数和边邻域离散数。与连通度和边邻域连通度不同,这些参数不仅考虑了破坏网络的难易程度,还考虑了网络遭受破坏的程度。 但已被证明的是计算一般图的这些参数是NP-困难问题。因此研究特殊图类的这些参数就十分有意义。在本文中,我们主要讨论了三类图:分割图,刺图和路和圈笛卡尔积的脆弱性参数。 本文第一章首先介绍了这些脆弱性参数,并总结了一些基本图类（路,圈,星状图,彗星图,完全k-部图等）关于这些参数的研究结果以及本文的研究成果。 第二章简要介绍了分割图的性质,讨论了分割图的脆弱性参数的计算问题。 第三章介绍了特殊图类刺图及其性质,讨论某些特殊的刺图的脆弱性参数,改正了Kirlangic的几个错误,并研究了单圈图的离散数计算问题。 第四章我们介绍了特殊图类:路和圈笛卡尔积,对其粘连度和毁裂度进行了一些讨论,介绍了我们的研究成果。 第五章介绍了关于图的脆弱性参数研究进一步可以做的研究工作。
论文目录
相关论文文献
标签：连通度论文; 边连通度论文; 坚韧度论文; 边坚韧度论文; 离散数论文; 完整度论文; 边完整度论文; 粘连度论文; 边粘连度论文; 毁裂度论文; 邻域连通度论文; 边邻域连通度论文; 邻域完整度论文; 边邻域完整度论文; 邻域离散数论文; 边邻域离散数论文; 分割图论文; 刺图论文; 路和圈的笛卡尔积论文;