赋权无向图的顶点素数分类与同构判别_罗贤海

《赋权无向图的顶点素数分类与同构判别_罗贤海》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第30卷第4期机械设计与研究Vol．30No．42014年8月MachineDesignandＲesearchAUG．，2014文章编号:1006-2343(2014)04-017-04赋权无向图的顶点素数分类与同构判别罗贤海，王佳宁，李涛(景德镇陶瓷学院机电学院，江西景德镇333403，E-mail:Lxh9031@163．com)摘要:运动链拓扑胚图一般是含自环和赋权的无向图，拓扑胚图的同构判别是类型综合的关键。提出了一种适用于赋权无向图顶点分类方法，将顶点度、赋权、自环分别用不同的素数区分，然后利用三者素数乘积形成顶点素

2、数度，将素数度序列按相同元素分组，将每组元素与素数重新建立映射，该映射关系下的素数可作为赋权无向图顶点的唯一标识，最后对邻接矩阵动态修改法进行改进，并用于运动链拓扑胚图和一般赋权无向图的同构判别，判别实例表明该方法的有效性。关键词:赋权无向图;顶点素数度;顶点分类;运动链;拓扑胚图;同构判别中图分类号:TH112文献标识码:ADOI:10.13952/j.cnki.jofmdr.2014.0086VertexPrimeClassificationandIsomorphismIdentificationofWeightedUnd

3、irectedGraphLuoXianhai，WangJianing，LiTao(SchoolofMechanical＆ElectronicEngineering，JingdezhenCeramicInstitute，Jingdezhen333403，China)Abstract:Atopologicalembryonicgraphofakinematicchainisgenerallyoneundirectedgraphwithself-loopsandweightsanditsisomorphismidentificati

4、onisakeytostructuralsynthesis．Anewclassificationmethodisgivenforvertexofweightedundirectedgraphbyusingprimes．Theprimedegreeofvertexisdefinedastheproductofthreedifferentprimesforvertexdegree，weight，andself-loop．Thesequenceofprimedegreeisgroupedwithsameelement，andeach

5、elementgroupismappedintoaprime．Theprimeisthereforeuniquetoavertexofweightedundirectedgraph．Themethodofdynamicmodificationtoadjacentmatrix，furthermore，isimprovedfortheisomorphismidentificationsofbothweightedundirectedgraphandtopologicalembryonicgraphofkinematicchain．

6、Appliedexamplesshowthatthevertexprimeclassificationandthemethodofdynamicmodificationiseffectiveandreliabletoisomorphismidentification．Keywords:weightedundirectedgraph;vertexprimedegree;vertexclassification;kinematicchain;topologyembryonicgraphs;isomorphismidentifica

7、tion［9］机构运动链同构问题是机构类型综合的核心问题之一，问题作为二次分配问题的同构判别法，通过增加和删除图在机构类型综合中利用运动链拓扑胚图进行综合是一种重［10］的边从而改变邻接矩阵的同构判别，利用顶点间最小色要的方法。运动链拓扑胚图往往是赋权和含自环的一般无差和最短路径的同构判别方法［11］，通过标号矩阵及标号之向图。同构问题也是图论中的重要理论问题，在许多领域有间的距离同构判方法［12］，将图转化为区间图的同构判别重要的应用。但图的同构问题至今未归到NPC(NP完备问［13］法。在已有的基于顶点分类的同构判别方法往

8、往需要进题)问题或P问题。在运动链和一般无向图的同构判别中，行回溯，因此判别复杂，计算量大。机构运动链作为一种特国内外学者开展了广泛的研究，提出了一系列有价值的判别殊的图，利用素数表示机构运动链中的构件，并形成可以描方法，例如利用一阶路径数组和二阶路径数组进行拓扑胚图述局部邻