机构运动链邻接矩阵的素数表示与同构判别

Prime Representation and Isomorphism Identification of M echanismKinematic Chains via the Adj acent MatrixLUO Xianhai(School of Mechanical＆Electronic Engineering，Jingdezhen Ceramic Institute，Jingdezhen 333403)Abstract：The adjacent relation ofmechanism kinematic chain is represented by a primary adjacency matrix by using primes to markits components.An isomorphism identifcation marx results from the primary adjacency matrix and prime products representingsecondary adjacent relation，and uses its determinant and solution vector of linear equation system to identify mechanismisomorphism.Dynamically，the identification matrix is modified by new primes on the basis of the classifcation of solution vectorelements.The result generates a solution vector with independent elements，which determines the positions of al nodes in thetopological graph of a kinematic chain.Furtherm ore，a mapping relation，which results in a necessary and suficient condition forisomorphism，iS established between componential codes of tw o isomorphic mechanisms.As a result.this new identification methodutilizes varying primes to virtually destruct the symmetry of the topological graph and change local and secondary adjacencyrelations among nodes under unchanged topological structure.Then，this method is also available for isomorphism identifcation ofgeneral un directed graphs.Applied examples show that it is very efective an d reliable for automatic identification with codemapping of isomorphism mechanisms and polynomial algorithm for computation time。

Key words：Kinematic chain Prime Adjacency matrix Linear equation system Solution vector Isomorphism identification0 前言机构同构问题-直是机构学领域的研究热点问题之-，引起国内外相关学者的重视，机构同构问题是机构类型综合、机构创新设计的主要问题。

机构同构判别已有许多方法，给出图节点与边的双江西省 自然科学基金(2010GZC0087)和江西侍育厅科技计划(GJJ12491)资助项目。20120517收到初稿，20130108收到修改稿射的方法有：基于邻接矩阵或关联矩阵的特征值和特征矢量计算方法l J，基于构件连接度矩阵的特征值法LjJ，该方法当出现较多相同特征值时同构判别计算量急剧增大，甚至失效。基于遗传算法的机构同构判别 ，但遗传算法本质上属于概率型搜索方法，存在早熟、易陷入局部解的缺陷，且用遗传算法进行同构判别其计算量尚未能从理论上给出较为精确的预测。根据关联矩阵及其转置矩阵的逐次乘积矩阵，通过乘积矩阵的行和数组的对应关系建立机 械 工 程 学 报 第 49卷第 5期②是异构的充分条件而非必要条件。

定义 2 用素数定义机构基本邻接矩阵A[口f，]如下fqPi J口f0 f 不邻接 (2)l P， f 邻接式中，p 、p，分别为构件f、 的素数，运动副数相同的构件其素数相同。q≥1为调整系数，如果IAI0，则通过调整g可使得 为严格对角优势矩阵，这时lAI≠0。这里 -般为非对称矩阵。

计算 的每行除对角元外的素数乘积，记该乘积最大值为 。

定义 3 描述构件次级邻接关系的邻接矩阵A[aiy]aijqP iJ0 不邻接 (3) m 邻接式中， 、p，、g的意义同定义2，m为 的第行除aⅣ、af夕 的所有素数乘积。-M≥M 为-个适当大的正数。显然a (当i≠ 时)为实数，当标号为f的构件与标号为 的构件邻接时，则a 小数部分表示了与构件 邻接的(除构件f外)其他构件信息。 可以很方便由 构造形成。定义 2、定义 3定义的邻接矩阵也适用于含任意复合铰个数的运动链。

如果将 的第 列元素用矢量b(这里b的全部分量为 1)替换后的矩阵用 (6)表示。设n阶矩阵 包含的素数为P，，Pz，， ，按列分为k土 组，第f组共有niYU， ，z ，设 A 的第 列素i1数属于第尼，组，对应的素数为 ，，将 的第 列所有素数 用新的 ，素数替换(对角元替换为)，替换后记矩阵为A ，用b替换 的第J列后记为A (6)。对矩阵A、A 有如下性质。

性质 1 如果行列式IAl≠0，线性方程组AXb，A b，解矢量元素有如下关系性质知 Pkj · Pkj≠根据克莱姆法则知性质 1成立。该性质显示了这样的-个信息，如果Xj≠0，则容易通过选择 使得Xt 不同于 中其他元素，进-步如果方程组式(4)第-个方程 AXb共有 ( ≥2)个与xj相同的元素，则对应该组元素，方程组式(4)第二个方程 b的相同元素个数为 ，-1，即 ：为中新出现的元素。另外如果l (6)I0，有Xj 0，共有七，个，则容易通过以下修改方法做-次 修改就 可 以使得 Ji，个 0元 素成 为- ，≠0，将矢量b全部分量 l修改为-个较pki大的正数 C，同时调整 A 中的系数g，使得矩阵(6)对角元素满足qPi> ∑ c i1，2，，j-1， 1，，kl， ≠f，kjc>∑ . l，式中，p 为 的对角元素数，显然经过修改后(6)成为严格对角优势矩阵，即I (6)l≠0，因而就有X ÷ ，≠0。

pki性质 2 由矩阵 A、A 构造的 、 ，线性方程组A(X8X)b A ( 8X )b (5)式中，x、 为方程组式(4)的解。当l l≠0、l I≠0时，并满足下面条件，线性方程组式(5)的解矢量 8X 至少出现-个新的元素。由定义 3知 ：A ， ：A， ，，其中 、跗 的元素为 0或为小数，跗 、跗 可以看成是对A、A的小扰动。当lIA Ilal<1、Ila ·I nA，lI<1时，其中 为矩阵的范数。则解的相对误差有 61≤A-1 IAI ≤A，-1 IA'I因此当 的第 列素数用新的素数替换为 时，因为方程组式(4)的解有 f≠Xtf，Xj≠0， ：≠0，这时如果A、A 为非病态矩阵(即矩阵的条件数较小)，且Il Il、ISA 8充分小，因而 ，、8x'，就、 舶歹 -丁 干由 .，o≠ 0.N ≠X。 ， 。

果女 2013年3月 罗贤海：机构运动链邻接矩阵的素数表示与同构判别 27充 分 小 ，则 可 知 方 程 组 式 (5)的解 ， ，≠： ：，因此 的第 列素数用新的素数替换后，由 形成的线性方程的解元素 ：必不同于中其他元素，如果替换前 中的 ，有Jj，个相同，则在 中对应该组变量的相 同解元素至少减少1个 。

定义 4 对于，l维实矢量 与 l， 定义其 相等”、 严格相等”、 不等”关系如下。

(1)VX∈X，3y∈Y使得 Y，且Vy∈Y，Sx∈X ，使得 x Y，则称 与 l，相等 ，记作X 兰l，。

(2)若X兰Y，且 或 y内的元素互不相等，则称 与 ，严格相等，记作 yo(3)至少存在-个 ∈X ，在 lr中找不到Y∈Y使得 ：Y，或至少存在-个Y∈J，，在 中找不到∈X使得xY，则称 与 l，不相等，记作X ≠y 。

在矢量相等关系中，矢量内可 以有相同的元素。对于两个机构运动链 G )和 G )，利用次级邻接矩阵(以下称为判别矩阵) 与 形成如下线性方程组AXb BYb (6)式中， c，f1，2，，z，c>0。

线性方程组式(6)的解矢量中的第f个元素与运动链中标号为f的构件的局部及次级邻接关系相对应。对于同构的两个机构运动链，矩阵 与 具有相同的行列式值和相等的解矢量。于是给出以下机构同构判别定理。

定理 2 对于构件数为，z的机构运动链 G )和G( )，则机构同构的必要条件如下。

(2)若 ≠0， ≠0，方程组式(6)具有相等关系的解矢量，即X兰，。

定理 2的证明是显然的，因为对于同构的两个机构运动链，存在初等变换矩阵，即同时交换矩阵中的行和列使 ： ，初等变换不改变行列式值，且初等变换只改变解矢量中的元素位置。

定理 3 对于构件数为 的机构运动链 G )和G )，如果：① G )和 G )的构件素数及构件素数度序列对应相等；② 与 的行列式值相等，即 ： ；③ ： ≠0。方程组式(6)具有严格相等关系的解矢量，即 l，。按解矢量建立顶点映射关系，如果该映射关系同时保持了边的映射，则两个机构同构，否则异构。

定理 3中的条件①、②为必要条件，而条件③构成充分条件，因为对具有严格相等关系的解矢量，容易通过解矢量建立两个机构构件标号的映射，如果同时保持了边的映射，则通过该映射关系同时交换 与 的行和列使得 ： ，因而也有 ， 因此两个机构同构。定理 3给出了找到同构机构标号映射的可行方法。

在按定理 3判别过程中，如果 ： ，X Y，根据性质 l、2，可通过逐步修改 、， 从 而修 改 、 使得解 矢量 X≠Y ，或≠ 或解矢量内互不相等的元素个数增加，最终使得 l，。矩阵每步修改方法如下：将解矢量X 、y中按相同的元素进行分组，设怪为e组，每组的元素个数为 ，f1，2，，P，取相同元素个数最小(不小于2)的-组(不妨设该组元素个数为 )。

该组元素对应机构运动链 G )和 G )的构件标号分别为(fl，f2，， )、( ， ，， )，这些标号的构件都具有-个相同素数 。图2为本步矩阵修改流程图，在 (fl，f2，， )中依次从-组新的素数( ，P2，，P.1)(该组素数必须与矩阵中原有的素数不相同)取出-个素数，替换A的对应列号的素数，并计算该列号对应构件的素数度 ，例如先将矩阵 的列素数用新的素数 替换，形成新的矩阵、 ， 然后在矩阵 标号中( ， ，，厶)按次序将未替换的标号用素数 Pl先计算构件新素数度， 如果 与 相等则将对应列的素数用 替换，形成新的矩阵 、ji，在替换的同时解方程组式(6)并计算行列式的值，得到新的解矢量，如果满足l l：l l和X兰Y则结束本次矩阵修改，取(，f2，， )中下个标号对应的矩阵列(例如取f2标号)继续修改，如果 l，，输出顶点映射关系，如果同时保持了边的映射，则可得到同构的结论，否则为异构，判别过程结束。否则恢复 G )中当前被替换列的原有素数，在( ， ，， ，)中取下-个标号对应的列进行素数替换，如果所有的替换都有X≠Y或l ≠I l，则两个机构异构。

下面给出依据定理 1、2和定理3的机构 G(A)和G )同构判别的算法步骤。

(1)对构件赋予初始素数，按定理 1进行初步判别，如果满足定理 1条件，则判别结束，否则转(2)。

28 机 械 工 程 学 报 第 49卷第 5期图2 矩阵修改流程图(2)根据定义2、定义3分别形成两个机构的初始矩阵 、 ， 、ji。

(3)计算 与 的行列式值，解线性方程组式(6)。如果：① ≠ ，或X≠l，则两个机构异构，判别结束；② XY，则比较 x与 y元素，输出标号映射关系，如果同时保持了边的映射，则两个机构同构，否则异构，判别结束；③ X兰Y，即 与 y内具有相同的元素，将 与 y的元素分组，转(4)。

该算法能在有限步内终止，并正确给出同构或异构的结论，根据性质 1、2，每修改-次矩阵，必能使得解矢量 与y至少增加-个新的不同元素，直至不同元素个数为n，因此算法具有很高的可靠性。

3 同构判别算法复杂性分析定理 l给出了基于素数度序列的机构同构判别方法，该方法简单，可以先用定理 1进行机构同构判别，只需要进行乘法运算和-维序列的排序运算，乘法运算次数N≤nl。由 形成 的乘法运算次数N≤nl(1-1)。

定理 2只需要解线性方程组和计算行列式，其运算量均为D( )。但定理 1实际上给出的是必要条件和-个严格的充分条件，定理 2给出的仍是必要条件，因此对-些机构的判别可能失效。利用定理3进行判别时计算量：① 最坏的情况是解矢量 、y 中相同元素只有-组，，l1，l，这种情况-般为完全对称的图，例如 n个孤立点、度数为 2的环、正则图等，此时存在n!同构映射关系，G )中任意的-个标号排列均能与 G )建立同构映射，计算表明只有 n个孤立点的矩阵修改次数为Ln，其余情况均有 L

表 2 机构同构的标号映射G ) G ) C-(A) G )1 16 15 222 l7 16 53 4 l7 64 3 18 75 12 19 86 l1 20 17 28 2l 28 27 22 259 26 23 2410 l9 24 151l 18 25 1412 9 26 1313 10 27 2O14 23 28 2l表 3 机构同构的标号映射G ) 研 6 ) G(司l l 12 92 3 13 123 I1 14 1O4 16 l5 135 I5 l6 66 4 17 57 8 18 148 18 19 2O9 19 20 21l0 2 2l 17n 75 结论(1)本文给出了两个机构运动链同构的充分必要条件。判别方法的核心创新点是巧妙地利用素数动态赋予相应的构件，在同构判别过程中动态修改邻接矩阵以模拟破坏图结构的对称性并模拟改变图节点的局部邻接、次级邻接关系，通过线性方程组解矢量将图节点位置进行唯-定位，从而找到两个同构机构的标号映射关系。

(2)本文方法计算时间的复杂度为多项式，计算量通常为O(Ln )，l≤L

(3)本文方法理论明确，判别方法简单，只要输入初始邻接矩阵就可以实现机构同构的自动判别，并开发了相应的同构自动判别软件。

(4)对于具有完全对称的图结构，本文的方法仍然非常有效。另外对于节点含有自圈或重边的无向图，只要将该节点赋予-个特定的素数，判别方法没有区别，因此可以推广到-般无向图的同构判别中。