论文部分内容阅读
在计算机网络或通讯网络的设计与维护过程中,网络的抗毁性是一项重要的性能指标。网络设计的基本思想之一就是使其在受到外部攻击时不易被破坏,而且,在万一遭到破坏时也能够容易得到修复。我们通常用无向连通图来表示网络,其中图的顶点代表网络站点,边代表网络站点间的直通线路。在此数学模型之下,人们开始讨论抗毁性的有关测度,早期的研究主要是围绕图的连通度和边连通度展开的。伴随着研究的深入,人们发现用这两个参数刻画图的抗毁性存在明显不足之处。后来,人们引入了一些其它的参数,如坚韧度、离散数、完整度、粘连度。这些参数不仅考虑了网络被破坏的难易程度,而且还考虑到了网络遭受的毁坏程度,相比图的(边)连通度而言,是一些较为合理的刻画网络抗毁性的参数。 本论文在总结和比较以上连通性参数的基础上,引入了能比较客观、相对简单的刻画图的连通性的一个新参数——图的相对粘连度,并对这个参数进行了初步的研究。论文第一章分析了图的连通性参数的研究背景和实际意义,并介绍了论文所需的一些相关知识和本论文的主要结果。论文第二章介绍了图的连通度、边连通度、坚韧度、边坚韧度、离散数、完整度、边完整度、粘连度、边粘连度等图的连通性参数,对它们做了比较归纳和系统分析。论文在第三章详细研究了一些特殊图(完全图、圈、路、星、彗星、完全二部图、完全k-部图)的相对粘连度,讨论了图的相对粘连度的界,图的运算的相对粘连度,树的相对粘连度的算法,相对粘连度与其他参数的关系。第四章讨论了图的相对粘连度意义下的最值网络的构造以及关于图的相对粘连度的Nordhaus-Gaddum型问题的结果。第五章对图的边相对粘连度进行了定义并做了一些简单研究。第六章讨论了相对粘连度的计算问题,证明了图的相对粘连度的计算是NP完全问题。最后,在结束语里我们对图的连通参数的定义进行了归纳统一,并提出了进一步研究的问题。