学位论文 > 优秀研究生学位论文题录展示

图的脆弱性参数研究

作　者: 齐楠楠
导　师: 张胜贵
学　校: 西北工业大学
专　业: 系统分析与集成
关键词: 连通度边连通度完整度边完整度弱完整度毁裂度邻域连通度边邻域连通度邻域完整度边邻域完整度邻域离散数边邻域离散数二项式树二部图 NP-困难问题 NP-完全问题
分类号: O157.5
类　型: 硕士论文
年　份: 2007年
下　载: 69次
引　用: 0次
阅　读: 论文下载

内容摘要

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

全文目录

摘要  5-7
Abstract  7-9
第一章绪论  9-19
  §1.1 引言  9-10
  §1.2 图的脆弱性参数研究现状  10-18
    §1.2.1 图的连通度与边连通度  10-11
    §1.2.2 图的完整度、边完整度、纯边完整度及弱完整度  11-14
    §1.2.3 图的离散数  14
    §1.2.4 图的毁裂度  14-15
    §1.2.5 图的邻域连通度和边邻域连通度  15-16
    §1.2.6 图的邻域完整度和边邻域完整度  16-17
    §1.2.7 图的邻域离散数和边邻域离散数  17-18
  §1.3 本文的主要结果  18-19
第二章图的邻域离散数  19-36
  §2.1 基本概念  19-20
  §2.2 求解二部图的邻域离散数是NP-完备的  20-23
  §2.3 二部图的邻域离散数的上下界  23-27
  §2.4 图的邻域离散数的上下界  27-36
第三章图的边邻域离散数  36-51
  §3.1 引言  36
  §3.2 求解二部图的边邻域离散数是NP-困难的  36-39
  §3.3 图的边邻域离散数的上下界及计算公式  39-45
  §3.4 边邻域离散数意义下的最大网络  45-51
第四章其它几个脆弱性参数的研究  51-61
  §4.1 引言  51-52
  §4.2 二项式树的完整度和边完整度  52-54
  §4.3 若干图的弱完整度及其与完整度之间的关系  54-58
  §4.4 给定顶点数和边数的图的最大毁裂度  58-61
第五章一些进一步研究的问题  61-63
参考文献  63-67
致谢  67-68
附录一作者攻读硕士学位期间完成和发表的论文  68-69
附录二作者攻读硕士学位期间参加的科研项目  69-70

图的脆弱性参数研究

内容摘要

全文目录

相似论文