含复合铰机构运动链的拓扑图表示与同构判别_罗贤海

第3期

2014年3月

机械设计与制造

Machinery Design ＆Manufacture

247

含复合铰机构运动链的拓扑图表示与同构判别

罗贤海，李亮臻，李涛

江西景德镇333403）（景德镇陶瓷学院机电学院，

摘

要：提出一种适用于含任意复合铰个数的机构运动链拓扑图表示新方法，该方法在对含复合铰运动链转化为拓扑

图时，在拓扑图顶点上标以顶点号和顶点对应的构件运动副数，与复合铰相连接的所有构件被看作是相互邻接的构件，该拓扑图完整表示了含复合铰机构运动链的信息，且不增加拓扑图顶点数规模。在拓扑图表示基础上，将邻接矩阵动态修改法应用到含复合铰运动链的同构判别，判别实例表明邻接矩阵动态修改法能有效对含复合铰机构运动链进行同构判别。

关键词：运动链；复合铰；拓扑图；同构判别中图分类号：TH16；TH112；TP391

文献标识码：A

文章编号：1001-3997（2014）03-0247-04

Topological Graph and Isomorphism Identification of Kinematic Chains

in a Mechanism with Compound Hinges

LUO Xian-hai ，LI Liang-zhen ，LI-tao

Jingdezhen Ceramic Institute ，Jiangxi Jingdezhen 333403，China ）（School of Mechanical &Electronic Engineering ，

Abstract ：A new available method is applied to represent a topological graph of a kinematic chain in a mechanism with compound hinges. In the topological graph ，a vertex is marked with a vertex number and a corresponding number of kinematic pair ，and mutually adjacent components equivalently substitute for all components connected to the compound hinge. This topological graph holds the same vertex number with traditional graph and contains the complete information of a kinematic chain in a mechanism with compound hinges. It turns out that the topological graph is applied to the dynamic modification of adjacency matrix so that it can effectively identify the isomorphism of the kinematic chains with compound hinges. Key Words ：Kinematic Chain ；Compound Hinge ；Topological Graph ；Isomorphism Identification

1引言

机构同构问题一直是机构类型综合、创新设计的核心问题之一。机构同构问题本质上属于图的同构，已有一系列同构判别方法，这些方法一般分为两大类。（1）特征恒量法，即当两个图的特征恒量对应相等时就判别为两图同构，否则判别为异构，例如全等环路法[1]，但是环路数随图的顶点数呈指数增长，对规模大的图搜索出全部环路则运算量难以接受。（2）判别方法则从图的同构定义出发，找到同构的两个图的顶点和边的双射关系，例如特征值和特征向量法[2]，规范邻接矩阵法[3]，同构判别的遗传算法[4]，利用邻接矩阵特征多项式系数的通过定义杆件度建立邻接矩阵，

判别法[5]。当出现较多相同特征值时同对于特征值和特征向量法，构判别计算量相当复杂。特征多项式系数法也存在类似情况。遗传算法则存在早熟、易陷入局部解的缺陷。针对含复合铰的机构运动链的拓扑图表示，已提出了一种新双色图描述机构运动链的拓扑图结构，引入pin 构件将复合铰链转化为多个并联单铰链

[6]

扑图顶点的新表示方法，在此基础上将邻接矩阵动态修改法应用到含任意复合铰的同构判别[8]。

2含复合铰的机构运动链的拓扑图表示

用通常的拓扑图及以（0，1）为元素的邻接矩阵难以表示含复合铰的机构运动链。例如构件的局部连接在通常的拓扑图描述中是相同的，如图1所示。邻接矩阵中的元素也相同，图1（a ）构件1与图1（b ）构件1的顶点度相同（即都有4条边与之连接），而这两个运动链的局部结构是不同的，图1（c ）的拓扑图并不能反映图1（a ）和图1（b ）的实际连接关系的差异。

5

51

43

2

3

2

1

4

5

4

1

2

3

的拓扑图表示方法，并用特征值和特征向量法判别复合铰运动链的同构[7]，当复合铰数量较多时新双色图和复合铰链转化法需增加较多的图顶点。针对含复合铰机构运动链提出一种不需增加拓

（b ）（c ）

图1构件局部邻接拓扑图示意

Fig.1Components and Their Local Topological Graph

（a ）

定义了一种新的含任意复合铰个数的机构运动链的拓扑图

2013-08-17来稿日期：

基金项目：江西省自然科学基金项目资助（2010GZC0087）；江西省教育厅科技项目资助（GJJ12491）作者简介：罗贤海，（1965-），男，江西广丰人，教授，博士，主要研究方向：机械设计及理论、计算机辅助工程

248罗贤海等：含复合铰机构运动链的拓扑图表示与同构判别

56

1

7

3

8

42

3

7

81

42

6

5

第3期

在拓扑图顶点上标上一个二元数（a ，b ），其中，a 表示构表示方法，

件运动副数，b 表示构件标号，与复合铰连接的所有构件均作为相互邻接的构件，以构件为图的顶点，以运动副为图的边形成拓扑图。根据上述方法表示的含复合铰机构运动链局部拓扑图示意，如图2所示。

563

4

1

2

（2，6）

（3，1）（3，3）

（2，5）

（2，4）（3，2）

（b ）（a ）

图4用新双色图表示复合铰拓扑图

Fig.4The Topological Graphs in New Black-and-White

图4中黑色顶点（1、2、3、4、5、6）表示构件，白色顶点（7、8）表示复合铰，新双色图将复合铰定义为图的一个顶点，只是该顶点用另外一种颜色（这里为白色）表示以区别用黑色顶点表示的构件。另外对图2（a ）、图2（b ）的局部运动链如果用引入pin 构件[7]方法表示复合铰拓扑图结构，表示结果与图4相同，只要将图4

（a ）

6

1

3

5

（2，6）

42

（3，3）

（2，5）

（2，4）

的白色顶点（7、8）改为黑色顶点且将顶点（7、8）作为3副杆（即pin 构件）即可。

如果将新双色图4的白色顶点也理解为构件，即将白色点改为黑色点，则新双色图与引入pin 构件的拓扑图没有本质的区别。新双色图与引入pin 构件的拓扑图表示需要增加新的顶点，当复合铰数量较多时显然就增加了图的规模，图2与图4均描述相同的运动链，相比之下这里提出的含复合铰运动链拓扑图表示方法不需增加图的顶点，这在判别运动链拓扑图的同构时特别是当复合铰数量较多时不会增加判别运算量。

（3，1）

（3，2）

（b ）

图2含复合铰运动链拓扑图表示

Fig.2The Topological Graph of Kinematic Chains

With Compound Hinges

而图1（a ）、图（b ）结构的拓扑图分别表示，如图3所示。

（2，2）

（2，5）

（2，5）

（2，4）

3含复合铰运动链的同构判别

含复合铰运动链的同构判别问题比一般运动链同构判别更复杂，相关的研究文献较少。在含复合铰运动链的同构判别中，ASHOK 等提出了通过构件度和运动副值进行运算来判别机构的虽然给出了部分判别实例，但该方法对某些一般图（该同构性[9]，

判别方法的反例，如图5所示。）并不适用，例如对图5用该方法判别时得到同构的结果，但实际上是异构的，容易看出图5（a ）中的一个环（4—9—2—5—12—15—4），在图5（b ）中却找不到与之全等的环，因此该方法不足以说明能适用于含任意复合铰运动链的同构判别问题。

1

1

（3，1）

（4，1）

（2，3）（2，4）

（2，2）

（3，3）

（b ）

图3构件局部拓扑图示意

Fig.3The Local Topological Graphs of Components

（a ）

显然图2、图3拓扑图能完整表示含任意复合铰的机构运动链信息，这种拓扑表示方法与已有的表示方法不同之处在于拓扑图除了对构件标号外，还用构件运动副数标识构件，另外与复合铰直接相连的构件均作为相互邻接的构件，在拓扑图上这些构件之间都用边连接，例如图1（a ）标号为1、3、4的构件连接到复合铰，则在拓扑图3（a ）中这3个顶点用边连接为一个三角形，这种标识非常适合邻接矩阵的形成并进行同构判别。从拓扑图中容易识别出连接到复合铰上的构件，识别方法是当顶点对应的构件运动副数小于顶点度数时，则表明该构件连接到复合铰上，例如图3（a ）中顶点（3，1）的运动副数等于3，但从图3（a ）中可以看出该顶点度数为4，表明标号为1的构件连接到了复合铰上，且复合铰的重数f 为f =4-3=1。如果顶点运动副数等于顶点度数，则表明该构件不含复合铰，显然这种拓扑图与实际运动链简图是一一对应的。

为了与这里提出的复合铰拓扑图表示方法进行比较，将图2（a ）、图2（b ）用新双色图方法[6]分别表示为含复合铰的局部拓扑如图4所示。图，

4

9

15

1213

11

81014

7

9

6

3

2

512

8

4151014

1311

7

5

2

6

3

（a ）（b ）

图5异构的两个图

Fig.5Two Non-Isomorphic Graphs

应用邻接矩阵动态修改法对含复合铰机构运动链进行同构判别[8]，首先依据构件运动副数赋予构件一个素数，例如将构件运动副数（2、3、4、5…）分别用素数（2、3、5、7…）进行标识，然后根据提出的含复合铰运动链拓扑图新表示方法形成机构基本邻接矩a ij " 阵A=! 如下：

No.3Ｍａｒ．２０１４

a ij =0，当i 与j 不邻接

p j ，当i 与j 邻接

n

机械设计与制造

（1）

軓

軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓

249

[***********][***********][***********][***********][***********]0023002202

軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓

軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓

i=jqp i ，

[***********][***********][***********][***********][***********]0000220022

p j —构件i 、式中：p i 、j 的素数；q 叟1—调整系数，通过调整q 可使行

列式|A |≠0。设n 为运动链构件总数，记：M =max

1燮i 燮n j =1，i ≠j

a ≠0，仪a ，

ij

ij

A =，B =

軍=軃軃ij 軃根据基本邻接矩阵A 形成同构判别矩阵A 如下：a

ap i ，i=j

0，当i 与j 不邻接p j +m ，当i 与j 邻接

軓+1M

（2）

軃ij =a

軓

軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓

軓=M，軍如下M 根据（2）式形成初始矩阵A （q =1，矩阵中元素仅保

軓叟M ，M p j 、q 的意义同式式中：p i 、（1），m —m =

k =1，k ≠j ，k ≠i

仪

n

a jk ，a jk ≠0。

軍、軍矩阵省略B C 留4位有效数字，）：

軓

軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓

53.097603.195102.04882.09760005.292732.1463000002.0488003.243923.4878000002.29275.292702.146332.048800002.19510003.487822.12200005.4390002.0732200005.4390000022.097602.[1**********].243922.07322.292703.2739000002.097620

002.21953.4878002.24392.097602

軍形軍与B 对于两个机构运动链G （A ）和G （B ），利用判别矩阵A 成如下线性方程组：

軍Y=b軍X=bB A

b i n ×1，其中，b=軃軃b i =100，i =1，2，…，n 。

对于同构的两个机构运动链其必要条件为：A 与B 的对角线元素对应相等，与的每行非零元素乘积对应相等。用邻接矩阵軍的行列軍与B 动态修改法判别机构运动链同构的主要过程：计算A

式A 解线性方程组（3），如果A 或X ≠Y 则两个軍，軍，軍B 軍≠B 軍軍与B 机构运动链异构，否则根据X 与Y 矢量内元素分类情况对A 进行动态修改并解线性方程组（3）直到X=Y，且X 与Y 矢量内元素互不相同，因此可以根据解矢量元素对应关系找到两个机构运动链构件标号映射关系，如果该映射也使得边保持映射，则两个机构同构，否则异构。

判别实例：

3个含复合铰的10杆机构与用这里方法表示的拓扑图，如图6所示。

932

4

810

5

6

67

2

81

1

3109

5

4

29

103

4

56

78

（3）

軍=A

軓

軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓軓

用邻接矩阵动态修改法图6（a ）与图6（b ）的行列式值相等，解向量也对应相等A 解向量X 、Y （保留4位軍=29550.4537，軍＝B 有效数字）分别为：

X =［7.2413，-2.9849，10.1204，9.0424，-20.7999，51.8682，-29.6146，29.5295，23.8713，25.2559］。Y =［7.2413，9.0424，-20.7999，51.8682，

-29.6146，25.2559，10.1204，-2.9849，23.8713，29.5295］根据解向量可建立图6（a ）与（b ）同构的构件标号映射关系，如表1所示。

表１机构同构的标号映射

Ｔａｂ．１ＭａｐｐｉｎｇｏｆＮｏｄｅＣｏｄｅｓｉｎｔｈｅＩｓｏｍｏｒｐｈｉｃＧｒａｐｈｓ

G （A ）12345

G （B ）18723

G （A ）678910

G （B ）451096

1

（a ）

（4，1）

（3，2）（2，10）（2，3）

（3，2）

（b ）（c ）

（4，1）

（4，1）（3，2）（2，10）（2，10）

（2，3）

（2，9）

（2，9）

（2，9）

（2，3）（2，8）（2，4）

（2，7）

（2，6）

（3，4）

（2，5）

（2，8）（3，8）

（3，4）

（2，7）（2，7）（2，5）

（2，5）（2，（2，6）6）

图6的（c ）行列式值C 因此軍≠C 軍，軍=-53088.8309A 軍=B 图6（c ）与图6（a ）、图6（b ）异构，也可以通过对矩阵A 、B 、C 的每行素数乘积序列判别图6（c ）与图6（a ）、图6（b ）异构。其中，A 、B 每行素数乘积序列均为：180，60，36，120，12，20，40，16，12，48，C 每行素数乘积序列为：180，60，36，120，12，20，20，16，24，48，两个序列不能完全对应相等，可得到图6（c ）与图6（a ）、图6（b ）异构的结论。

（a ）

（b ）（c ）

图6三个含复合铰运动链与拓扑图

Fig.6Kinematic Chains with Compound Hinges and

Their Topological Graphs

3、4的杆分别用素数2、3、5表示，根据式将运动副数为2、

（1）图6三个机构运动链邻接矩阵如下：

250机械设计与制造

Journal of Mechanical Engineering ，2004，40（7）：85-88.

No.3

Ｍａｒ．２０１４

（在该例中pin 对该判别实例如果用新双色图、引入pin 构件构件为3副杆）表示运动链拓扑图，只要将白色顶点用素数7表示或将pin 构件用素数3表示，根据式（1）、（2）形成邻接矩阵，用邻接矩阵动态修改法判别同样可以得到图6（a ）与图6（b ）同构，而图6（c ）与图6（a ）、图6（b ）异构。

［3］葛茂忠，项建云，徐人平. 一种判定运动链同构的新方法［J ］．机械设计

与制造，2007（3）：19-20.

（Ge Mao-zhong ，Xiang Jian-yun ，Xu Ren-ping.A new approach for disti-nguishing isomorphism of kinematic chains ［J ］．Machinery Design &Man-ufacture ，2007（3）：19-20. ）

［4］RAO A C.Pseudogenetic algorithm for evaluation of kinematic chains ［J ］.

Mechanism and Machine Theory ，2006（41）：473-485.

［5］Hasan Ali ，R.A Khan. ，Mohd Aas.A new method to detect isomorphism in

kinematic chain ［J ］.Kathmandu University Journal of Science ，Enginee-ring and Technology ，2007，1（3）：1-9

［6］丁华锋，黄真. 平面机构统一拓扑描述模型的建立及同构判别［J ］．机械

工程学报，2009，45（3）：99-103.

（Ding Hua-feng ，Huang Zhen.Uniform topological representation model of planar mechanisms and isomorphism identification ［J ］．Journal of Mec-hanical Engineering ，2009，45（3）：99-103. ）

［7］刘江南，于德介. 基于转化邻接矩阵的含复铰运动链描述与同构识别

［J ］．机械工程学报，2012，48（5）：15-21.

（LIU Jiang-nan ，YU De-jie.Representations &isomorphism identification of planar kinematic chains with multiple joints based on the converted adjacent matrix ［J ］．Journal of Mechanical Engineering ，2012，48（5）：15-21. ）

［8］罗贤海．机构运动链邻接矩阵的素数表示与同构判别［J ］．机械工程学

报，2013，49（5）：24-31.

（Luo Xian -hai ．Prime representation and isomorphism identification of mechanism kinematic chains via the adjacent matrix ［J ］．Journal of Mecha-nical Engineering ，2013，49（5）：24-31. ）

［9］ASHOK Dargar ，KHAN R A ，HASAN Ali. Application of link adjacency

values to detect somorphism among kinematic chains ［J ］.Int. J Mech. Mater. ，2010（6）：157-162.

4结论

（1）提出了一种适用于含任意复合铰链个数的拓扑图表示新方法，将拓扑图顶点定义为一个二元数，与复合铰相连的构件看作互相邻接的构件，该方法表示的拓扑图与新双色图表示以及引入pin 构件表示的运动链拓扑图相比，这里的拓扑图表示方法不增加图的顶点数规模，因而在对含较多复合铰运动链进行同构判别或其它分析时不会增加运算量。（2）在这里的含复合铰运动链的拓扑图表示基础上，将邻接矩阵动态修改法应用于含复合铰运动链的同构判别，判别实例表明邻接矩阵动态修改法能有效应用于含复合铰运动链的同构判别，并能给出同构机构的构件标号映射关系。此外邻接矩阵动态修改法也可用于运动链新双色图或引入pin 构件拓扑图的机构同构判别。

参考文献

聂松辉. 平面运动链同构识别的全等环路法［J ］．机械科学与［1］伍星华，

技术，2009，28（2）：205-209

（Wu Xing-hua ，Nie Song-hui. Congruent loop approach to isomorphism identification of planar kinematic chains ［J ］．Mechanical Science and Technology for Aerospace Engineering ，2009，28（2）：205-209. ）［2］万金保，董铸荣，沈守范. 用邻接矩阵识别机构运动链同构的研究［J ］．

机械工程学报，2004，40（7）：85-88.

Wan Jing-bao ，Dong Zhu-rong ，Shen.shou-fan.Research on mechanism kinematic chain isomorphism identification using adjacent matrices ［J ］．

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

（上接第246页）

［J ］. 工具技术，200428（9）:［2］谢华锟. 近年来齿轮测量技术与仪器的发展

27-33.

（Xie Hua -hun. The development of gear measuring technology and instrument in recent years ［J ］. Tool Engineering ，200428（9）:27-33.）［3］黄富贵，张认成. 在三坐标测量机上精确测量渐开线圆柱齿轮的齿形

误差［J ］. 工具技术，2005，39（7）：85-87.

（Huang Fu-gui ，Zhang Ren-cheng.Tooth profile error of involute cylinder gear were measured precisely on the CMM ［J ］.Tool Engineering ，2005，39（7）：85-87. ）

［4］苑惠娟，韩立美，孙永全. 大齿轮齿形偏差测量方法研究［J ］. 机械设计

与制造，2013（3）：169-171.

（Yuan Hui-juan ，Han Li-mei ，Sun Yong-quan.Research on measurement method for gear profile based on radial polar coordinate ［J ］.Machinery Design &Manufacture ，2013（3）：169-171. ）

［5］史恩秀，田晓虹，李永堂. 渐开线圆柱齿轮齿形误差的测量与计算［J ］.

太原重型机械学院学报，2000，21（1）:18-21.

（Shi En-xiu ，Tian Xiao-hong ，Li Yong-tang.The measurement and calcu-lating of the gear ’s profile ［J ］.Journal Of Taiyuan Heavy Machinery Insti-tute ，2000，21（1）:18-21.）

［6］GB/Z18620.1—2008渐开线圆柱齿轮精度检验细则［S ］.

（GB/Z18620.1—2008Inspection code for accuracy of involute cylindrical gears ［S ］）.

［7］GB/T10095.1—2008圆柱齿轮精度制. 第一部分：轮齿同侧齿面偏差

的定义和允许值［S ］.

（GB/T10095.1—2008Cylindrical gears -System of accuracy -Part 1：Definitions and allowable values of deviations relevant to corresponding flanks of gear teeth ［S ］）.

［8］石雪梅. 基于齿轮测量中心的渐开线圆柱齿轮的测量与评定［D ］. 天津：天

津大学，2009.

（Shi Xue-mei. Measurement and evaluation of involute cylindrical gear based on gear measurement center ［D ］.Tianjin:Tianjin University ，2009. ）［9］杨全超. 渐开线圆柱齿轮各项偏差计算及精度等级评定［D ］. 苏州：苏

州大学，2012：19-22.

（Yang Quanchao.Research on Calculation and Accuracy Assessment for Involute Spur Gear Deviation ［D ］.Suzhou ：Soochow University ，2012：19-22. ）

［10］张展. 渐开线圆柱齿轮传动［M ］. 北京：机械工业出版社，2012:8-20.

（Zhang Zhan.Transmission of Involute Cylindrical Gear ［M ］.Beijing:China Machine Press ，2012：8-20. ）