3类特殊图完美匹配数的计算公式

发布时间：2019-03-25 10:42

【摘要】：图的完美对集计数问题已经被证实是NP—难问题,因此要得到一般图的完美对集的数目是非常困难的。该问题在蛋白质结构预测、晶体物理学、计算机科学和量子化学中都有重要的应用,对此问题的研究具有非常重要的理论价值和现实意义。用划分,求和,再递推的方法分别给出了图3-nT_4,5-nT_6和2-2nQ_(2×2)的完美匹配数目的计算公式,为图的完美匹配问题的应用提供了理论支持。
[Abstract]:The problem of counting perfect pairs of graphs has been proved to be NP- difficult, so it is very difficult to get the number of perfect pairs of general graphs. This problem has important applications in protein structure prediction, crystal physics, computer science and quantum chemistry. The research on this problem is of great theoretical value and practical significance. By the method of partition, summation and recursion, the formulas for calculating the number of perfect matches of graphs 3-nT_4,5-nT_6 and 2-2nQ2 脳 2 are given respectively, which provide theoretical support for the application of the perfect matching problem of graphs.
【作者单位】： 天水师范学院数学与统计学院;华东师范大学数学系;
【基金】：国家自然科学基金(11171114)
【分类号】：O157.5

【相似文献】

相关期刊论文 前10条

1 陈赐平;;关于图的完美对集的一点注记[J];北京农业工程大学学报;1990年01期

2 马英红;关于图的韧度与分数完美对集的若干结果[J];山东大学学报(自然科学版);2002年01期

3 陆芸婷;;哈林图中划分成完美对集问题的线性算法[J];科学技术与工程;2009年15期

4 管梅谷;;极大对集与最短投递路线问题(续)[J];曲阜师院学报(自然科学版);1978年03期

5 李为政;一个完美对集问题[J];华中师院学报(自然科学版);1980年04期

6 刘桂真;求最优权对集的一个对偶算法[J];数学研究与评论;1985年04期

7 徐武城;图中完美对集的一个充分必要条件及其计数[J];工科数学;1992年01期

8 王骋;关于图论中完美对集的一个充分条件[J];西安理工大学学报;2005年03期

9 王中兴;;完全图正常△+2全着色的构造[J];广西大学学报(自然科学版);1989年04期

10 姚兵 ,刘信生;Kotzig猜想的部分解决[J];西北师范大学学报(自然科学版);1984年02期

相关会议论文 前1条

1 师海忠;;关于Star-网络的一个猜想[A];中国几何设计与计算新进展2007——第三届中国几何设计与计算大会论文集[C];2007年

相关硕士学位论文 前2条

1 胡艳红;三类互连网络的Hamiltonian分解[D];西北师范大学;2016年

2 孙岩;关于图的分数（1；f）-因子的一些结果[D];山东大学;2010年

，

本文编号：2446897