顶点划分映射算法判定运动链同构

An algorithm identifying kinematic chain isomorphism based on vertex split and mapping

研究机构创新设计中运动链同构判定问题.依据图论和机构拓扑学原理,提出子块、平方和度、子块关联度等概念;利用拓扑图顶点间连接关系,构造顶点分类集合;提出一种将所有顶点一一划分并两两映射的算法,实现同构识别.实验结果证明该算法比现有算法效率高.将算法设计基础理论应用于机构拓扑学,为该领域研究提供新思路.

Kinematic chain isomorphism identification,which is a problem in mechanism innovative design,is studied.Based on graph theory and mechanical topology,the sub-block,the square sum degree and the association degree between sub-blocks were proposed.Based on the connection relations between vertices of topological graph,the vertex sets were built.An algorithm,making each vertex a set,then mapping them,finally realizing isomorphism identification,was proposed.The experiments presented show the proposed algorithm is more effective and efficient than existing algorithms.The basic theory of algorithm design is applied in mechanisms,which provides a new method in this field.