几类网络抗毁性和邻域抗毁性参数研究

摘要

网络抗毁性是计算机、信息、运筹学等学科的一个重要研究课题．人类已经进入网络化时代,这使得网络抗毁性研究受到更多的关注。在设计计算机网络和通信网络时,为了避免和最大限度地减少因网络通信中断所带来的损失,设计者必须考虑网络的抗毁性．因此网络设计的基本思想之一是当其在受到外部攻击时,不容易被破坏；当受到破坏时,能比较容易修复。一个计算机网络或者通信网络,可以用一个连通图表示,其中图的顶点表示通信站,边表示两个通信站之间的通信线路。对于一般的网络,其抗毁性即所对应的图的抗毁性,通过引入适当的参数定量刻画。早期的抗毁性参数研究,主要是围绕连通度和边连通度展开的．它们被广泛地用来刻画图的抗毁性,而且已被证明,它们存在多项式时间算法．然而这两个参数在刻画图的抗毁性方面具有一定的局限性,所以近几十年来,人们不断地研究并引进新的抗毁性参数。
　　本研究前分为五个部分：第一章简要介绍了网络抗毁性的概念、研究背景及其研究现状；第二章引入平均（边）坚韧度和平均（边）粘连度两个新参数,给出了几类基本图的上述参数计算公式；第三章主要研究了平均（边）邻域坚韧度和平均（边）邻域粘连度,给出了几类基本图的上述参数计算公式；第四章基于赋权图的抗毁性参数提出诚实赋权图的概念并研究了相关的问题；第五章总结全文,提出了若干值得继续研究的问题。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪论

1.1 引言

1.2 本文的主要工作

1.3 网络及其抗毁性的概念

1.4 网络抗毁性的研究现状

1.5 本章小结

2 图的平均坚韧度和平均粘连度

2.1 图的平均坚韧度和平均边坚韧度

2.2 几种特殊图的平均坚韧度

2.3 图的平均粘连度和平均边粘连度

2.4 几种特殊图的平均粘连度

2.5 一类极图问题

2.6 本章小结

3 图的平均邻域坚韧度和平均邻域粘连度

3.1 图的邻域抗毁性

3.2 图的平均邻域抗毁性参数

3.3 几种特殊图的平均邻域坚韧度和平均邻域粘连度

3.4 本章小结

4 一类特殊赋权图的抗毁性

4.1 赋权图的抗毁性简介

4.2 一类特殊赋权图及其抗毁性

4.3 本章小结

5 总结与展望

5.1 本文的创新与不足

5.2 进一步研究的问题

参考文献

致谢