两类有向图的匹配数研究

发布时间：2017-08-04 05:15

  本文关键词：两类有向图的匹配数研究

  更多相关文章： 复杂网络 有向树 有向三角形树 匹配 Hosoya指标

【摘要】：随着计算设备的日益强大和迅猛发展的Internet,人们能够收集和处理种类不同且规模巨大的实际网络数据.并且希望可以通过一些措施对复杂网络进行有效的控制,使其朝着对人们的生产、生活有利的方向发展.刘和Barabasi等人提出:有向网络的可控节点数等于有向网络的顶点数减去最大匹配包含的边数.说明有向网络的可控性与有向网络的匹配数有着密切的联系.因此,研究有向网络的所有匹配数目具有一定的应用意义.本文主要研究有向树及一类有向三角形树的所有匹配数的计数问题和极值问题.首先,介绍复杂网络的研究背景、复杂网络可控性的研究背景、匹配数的发展背景.第二章介绍了一些无向图、有向图及有向树的基本知识.第三章给出了含n个节点有向树的匹配数的计算方法、表达式及其相关性质,确定了具有n个节点的有向树匹配数的上下界和达到上下界的有向树.第四章研究了一类有向三角形树匹配数的计数问题,给出含n个三角形的有向三角形树的匹配数的计算方法,给出有向三角形树匹配数的上下界和相应的结构.最后一章对本文进行了总结,给出了一些有待解决的问题.
【关键词】：复杂网络 有向树 有向三角形树 匹配 Hosoya指标
【学位授予单位】：青海师范大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5
【目录】：

• 中文摘要3-4
• 英文摘要4-7
• 第一 章引言7-15
• 1.1 复杂网络的研究背景7-10
• 1.2 复杂网络可控性的研究背景10-13
• 1.3 匹配数的研究背景13-14
• 1.4 本文的主要研究工作14-15
• 第二 章基本知识15-18
• 2.1 无向图的基本概念15
• 2.2 有向图的基本概念15-18
• 第三 章有向树的匹配数18-25
• 3.1 有向树的基本定义18-19
• 3.2 有向树匹配数的计算方法19-23
• 3.3 有向树匹配数的算法23-24
• 3.4 小结24-25
• 第四 章一类有向三角形树的匹配数25-34
• 4.1 有向三角形树的基本定义25-26
• 4.2 一类有向三角形树匹配数的计算方法26-32
• 4.3 有向三角形树匹配数的算法32-33
• 4.4 小结33-34
• 第五 章总结与展望34-36
• 5.1 总结34
• 5.2 有待研究的问题34-36
• 参考文献36-39
• 致谢39-40
• 个人简介40
• 学习经历40
• 研究成果40-41
• 研究生期间参与的项目和获得的科研成果41

，

本文编号：617871