基于电路模拟的大规模图同构判定算法研究

项目名称： 基于电路模拟的大规模图同构判定算法研究

项目编号： No.61301028

项目类型： 青年科学基金项目

立项/批准年度： 2014

项目学科： 无线电电子学、电信技术

项目作者： 商慧亮

作者单位： 复旦大学

项目金额： 20万元

中文摘要： 图的同构判定是图论学科中的基本问题之一，对模式识别、有机化学、机械学及电路分析等领域的系统建模具有重要作用。本项目拟在本课题组提出的电路模拟法基础上，依据电路理论，针对图同构判定问题中较难的对称图同构判定问题展开研究，分析对称图的分支特征，拟建立基于分支搜索的改进电路模拟法模型，设计对称图和非对称图都能适用的具有较好普适性的图同构判定算法；拟采用稀疏矩阵技术对电路模拟法判定程序加以优化，进一步提高算法的判定效率和所能判定的图的规模。针对一些特殊类型的图，例如非连通图，拟建立基于子图划分的改进电路模拟法模型，设计相应的优化算法。期望通过该项目的研究，得到一种普适的面向一般图的同构判定算法，为相关领域的应用研究提供更为高效的方法和科学的依据。

中文关键词： 同构；电路模拟；电路理论；；

英文摘要： The graph isomorphism determination is one of the basic problems in graph theory and plays an important role in modeling of the system in pattern recognition, organic chemistry, mechanism, circuit analysis and other related fields.On the basis of the circuit simulation method proposed by our group, we plan to use the method based on circuit theory to research the isomorphism determination of symmetric graphs which has been a difficult isomorphism determination problem. We will analyze the branching characteristics of symmetric graphs in order to establish an optimized circuit simulation model based on branching search and design a relatively pervasive graph isomorphism algorithm which is suitable for both symmetric and non-symmetric graphs. We plan to optimize the determination procedure of circuit simulation method with the sparse matrix technology to further enhance the efficiency of the procedure and expand the size of graphs to be determined. We will further build optimized circuit simulation method on the basis of subgraph partitioning and design optimized algorithms for some special graphs such as disconnected graphs. Through this project, we expect to get a pervasive graph isomorphism determination algorithm for general graphs and provide more effective method and scientific theory for the application and

英文关键词： isomorphism；circuit simulation；circuit theory；；