具有相同路径层矩阵的图、应用及算法研究-东篱科研大数据发现系统（DRDS）

位置：立项数据库 > 立项详情页

具有相同路径层矩阵的图、应用及算法研究

项目名称：具有相同路径层矩阵的图、应用及算法研究
项目类别：面上项目
批准号：60373096
申请代码：F020104
项目来源：国家自然科学基金
研究期限：2004-01-01-2006-12-31

项目负责人：杨元生
负责人职称：教授
依托单位：大连理工大学
批准年度：2003

中文摘要：

本课题研究具有相同路径层矩阵的不同构的图，同时，研制较好的构造这些图的算法与较好的计算图的路径层距阵的算法, 并以此研究这些图的特征，从中探讨出图同构的更多、更好的必要条件，并为这些图的实际应用提供更坚实的理论基础。本课题是在医药品分析与设计的实际应用领域中提出来的。路径层矩阵也称分子的原子路径代码，该不变量及其各种变种在化学中描述分子分枝、确立分子图的相似性、设计医药品等领域都有令人感兴趣的应用。本课题属于NP困难问题，研究它对解决一般NP困难问题也很有意义。在图的同构问题研究领域，申请者已取得了部分国际领先成果，本项目的研究，将有助于我们在该领域继续保持国际领先水平。

中文主题词：同构;路径;路径层矩阵;NP困难问题

英文摘要：

isomorphism; path; path layer

英文主题词： isomorphism; path; path layer

结论摘要：

图的路径层矩阵问题是在药品分析的实际应用领域中提出来的，该不变量及其各种变种在化学中描述分子分枝、确立分子图的相似性、设计医药品等领域都有令人感兴趣的应用。本课题属于NP困难问题，研究它对解决一般NP困难问题也很有意义。本项目组设计出全新的研究方法与路线，研制出时间复杂度较低的新算法，对具有相同路径层矩阵的正则图进行了深入的研究，取得了部分国际领先的成果。该领域的最新成果中，f1的上界与下界分别由Mckay与Dobrynin取得,f2的上界与f(r)(r≥3)的上界均由本课题组取得。研究期间，在国内外重要刊物上发表论文15篇，已被SCI索引10篇次，EI索引5篇次。另外还有13篇论文已被国外SCI刊源刊物录用。自然科学基金的资助促进了人才培养。项目组成员被晋升教授3名,副教授3名。9名博士生与24名硕士生的毕业论文都是本项目的论文。应用本研究成果进一步改进了部队水路运输决策支持系统,目前该系统已在全军推广使用。对路径幂图的交叉数进行了研究，并取得一项新的国家自然科学基金资助(No.60573022)。

成果综合统计