图的邻域孤立断裂度研究

论文摘要

现实中的网络,往往会遭受到来自内（外）部破坏性事件的打击.这些破坏的后果不仅在于其本身,而且在于连锁反应或次生灾害.如间谍的叛变,高危病毒在人群中的传播,计算机病毒对信息网络的威胁等.这些特殊网络的抗毁性必须在邻域场合下考虑.因此,网络邻域抗毁性研究具有重要的理论与现实意义.本文研究了一个刻画网络邻域抗毁性的重要参数--邻域孤立断裂度的相关问题.首先,修改了 Ersin Aslan于2015年提出的邻域孤立断裂度的定义.因为该参数没有计算去掉邻域点割集后剩余的所有分支,也没有使得所有分支均为孤立点或团,因此它是不合理的.对于连通图G,其邻域孤立断裂度应定义为NIS（G）=max{i（G/S）-|S|:i（G/S）>1},其中S为G的邻域点割集,且G/S的每个分支均为孤立点或团,i（G/S）为G/S的连通分支数.其次,研究了若干重要图类的邻域孤立断裂度计算问题,给出一些基本图类和广义Petersen图,路、圈的线图、幂图、补图,顺次联图的邻域孤立断裂度计算公式.通过研究一般图的邻域孤立断裂度的界以及与其它重要参数,如邻域离散数,邻域连通度,邻域完整度等的关系,初步探索了邻域孤立断裂度与网络结构的关系.最后,用构造性的方法,通过将二部分图的控制数问题的一个实例在多项式时间内转化为二部分图的邻域孤立断裂度问题的一个实例,证明了二部分图的邻域孤立断裂度问题是NP完备的.通过在完全图,路和圈上添加边,分别给出点数和邻域孤立断裂度给定条件下的最大与最小网络及其构造方法.本文解决了图的邻域孤立断裂度的若干基本问题,对于后续的深入研究具有重要的基础性作用.

论文目录

摘要

abstract

1 绪论

1.1 引言

1.2 国内外研究现状

1.2.1 国外抗毁性参数的研究现状

1.2.2 国内抗毁性参数的研究现状

1.3 本文的主要工作

2 网络抗毁性参数

2.1 图的抗毁性参数

2.2 图的邻域抗毁性参数

2.3 小结

3 几个重要图类的邻域孤立断裂度

3.1 特殊图的邻域孤立断裂度

3.2 线图的邻域孤立断裂度

3.3 幂图的邻域孤立断裂度

3.4 顺次联图的邻域孤立断裂度

3.5 补图的邻域孤立断裂度

3.6 小结

4 邻域孤立断裂度与图的结构

4.1 图的邻域孤立断裂度与其它参数的关系

4.2 邻域孤立断裂度问题的NP完备性

4.3 邻域孤立断裂度意义下的极值图

4.3.1 具有最多边数的图

4.3.2 具有最少边数的图

4.4 小结

5 总结与展望

5.1 总结

5.2 展望

致谢

参考文献

攻读硕士学位期间的研究成果

文章来源

类型: 硕士论文

作者: 付维杰

导师: 魏宗田

关键词: 网络,抗毁性,邻域孤立断裂度,邻域离散数,极值图

来源: 西安建筑科技大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 西安建筑科技大学

分类号: O157.5

DOI: 10.27393/d.cnki.gxazu.2019.000410

总页数: 59

文件大小: 3215K

下载量: 23

图的邻域孤立断裂度研究

论文摘要

论文目录

文章来源

相关论文文献

猜你喜欢