某些网络的距离控制数

发布时间：2017-10-13 03:31

  本文关键词：某些网络的距离控制数

  更多相关文章： 距离控制数 控制数 NPC NP-hard 笛卡尔乘积图

【摘要】：图论是离散数学的一个重要分支,它是现代电子计算机的理论基础,不论在理论上还是在现实中都扮演着重要的角色。图论的发展具有悠久的历史的,自欧拉首次给出柯尼斯堡七桥问题开始,图论吸引了一大批学者的关注与研究,不断的新的问题的提出与解决给图论发展带来了源源不断的动力与乐趣。本文主要研究一些具有简单结构的、常见的图类的距离控制数。在计算机网络中,控制数具有重要的应用,它表示控制整个网络的所需要的最少的点数,也就是所需要的最小费用。因而研究控制数具有重要的理论和现实意义。与控制数相关的一个重要概念就是束缚数,它是网络安全性能的一个重要指标。距离控制数和距离束缚数是经典的控制数和束缚数的自然推广,具有更加广阔的现实背景和意义。但确定一个图的距离控制数是一个NPC问题。因此,确定一些典型图类的距离控制数以及它们的界就显得尤为重要。这能为进一步确定其他复杂结构的图的距离控制数提供重要的界的依据。 本文第一章介绍了图论中必要的基本概念,以及控制数、束缚数的现实背景。 第二章确定了与路相关的几种笛卡尔乘积图Pn, Pn×P2,Pn×P3,Pn×Km的k-距离控制数。 第三章确定了与圈相关的图Cn, Cn×P2,Cn×P3,Cn×Km的k-距离控制数。
【关键词】：距离控制数 控制数 NPC NP-hard 笛卡尔乘积图
【学位授予单位】：中国科学技术大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要5-6
• Abstract6-7
• 目录7-9
• 第一章 绪论9-21
• 1.1 图论的历史背景9
• 1.2 图论的一些基本概念9-16
• 1.3 控制数16-18
• 1.4 束缚数18-19
• 1.5 本文工作19-21
• 第二章 与路相关的笛卡尔乘积图的距离控制数21-29
• 2.1 k-距离控制集的性质21-22
• 2.2 P_n×P_2的距离控制数22-24
• 2.3 P_n×K_m的距离控制数24-26
• 2.4 图P_n×P_3的距离控制数26-29
• 第三章 与圈相关的图的距离控制数29-37
• 3.1 关于C_n的距离控制数29
• 3.2 C_n×P_2的距离控制数29-33
• 3.3 关于P_n×K_m及P_n×P_3的距离控制数33-37
• 参考文献37-39
• 致谢39

【参考文献】

中国期刊全文数据库 前1条

1 管梅谷;中国投递员问题综述[J];数学研究与评论;1984年01期

中国博士学位论文全文数据库 前2条

1 李宁;图的控制问题研究[D];中国科学技术大学;2011年

2 胡夫涛;图的约束数研究[D];中国科学技术大学;2012年

，

本文编号：1022606