基于全息下三角矩陣變換對(duì)比的運(yùn)動(dòng)鏈同構(gòu)判定方法

中圖分類號(hào)：TH112

DOI：10.3969/j.issn.1004-132X.2025.06.005 開(kāi)放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

Isomorphism Identification Method for Kinematic Chain Based on Exchange and Comparison of Lower Triangular Matrix with Whole Information

ZHANG Guangshuai SUN Liangbo*LIU Xiaocui ZHANG Deping ZHOU Huaxi School of Mechanical Engineering，Wuhan Polytechnic University，Wuhan，430023

Abstract： Isomorphism identification was recognized as a critical step in the synthesis processes of kinematic chains（KC）. A new MWI was proposed to describe the structural information of KCs. The principles for determining multiple-joint and polygonal links were introduced. Based on the principle that the lower triangular matrix with whole information（LTMWI）may uniquely express the structure of KCs，a new isomorphism identification method was proposed with the comparison and exchange of LTMWI. This method relied on the transformation law of links and key point numbers. Two KCs were expressed by LTMWI，with one LTMWI was selected as the datum matrix. After grouping the key points and moving the non-zero elements of key points in the same group forward，the determined key points and the key points to be determined were obtained. Under the assumption that all key points in the exchange matrix correspond one-to-one with the key point positions in the datum matrix， a finite number of exchange matrices were compared. The method has advantages such as a simple principle，ease of programming，and an identification process requiring only retrieval/comparison operations. It could quickly provide isomorphism identification results，and the mapping of links and even revolute pairs could be obtained. Isomorphism analyses of several KCs demonstrate the aforementioned characteristics of the method.

Key words： isomorphism identification；matrix with whole information（MWI）；datum matrix; multiple-joint；polygonal link

0 引言

機(jī)構(gòu)運(yùn)動(dòng)鏈構(gòu)型綜合是機(jī)構(gòu)學(xué)領(lǐng)域的一個(gè)難題，也是機(jī)構(gòu)創(chuàng)新設(shè)計(jì)的核心研究?jī)?nèi)容[1]。在運(yùn)動(dòng)鏈型綜合過(guò)程中，運(yùn)動(dòng)鏈的生成方法[2]、剛性子鏈判定[3]、同構(gòu)判定4]、拓?fù)鋱D和結(jié)構(gòu)圖自動(dòng)繪制[5]等關(guān)鍵技術(shù)問(wèn)題都是必須解決的。

運(yùn)動(dòng)鏈的生成過(guò)程幾乎都伴隨著大量同構(gòu)的運(yùn)動(dòng)鏈產(chǎn)生。同構(gòu)判定過(guò)程需要將后續(xù)所有構(gòu)型與前面不重復(fù)的構(gòu)型進(jìn)行逐一對(duì)比，需要 C_n² 次計(jì)算分析，占據(jù)了構(gòu)型綜合過(guò)程的大部分計(jì)算分析量。研究人員將圖的同構(gòu)判定引入機(jī)構(gòu)學(xué)研究中，提出同構(gòu)判定方法必須滿足以下要求，即提出并且能證明運(yùn)動(dòng)鏈結(jié)構(gòu)唯一性判定依據(jù)、準(zhǔn)確可靠、分析計(jì)算量小且便于程序化設(shè)計(jì)。

運(yùn)動(dòng)鏈同構(gòu)識(shí)別研究已取得顯著進(jìn)展，研究人員從不同角度提出了多種判定方法。特征多項(xiàng)式法通過(guò)構(gòu)建包含特定結(jié)構(gòu)信息的矩陣（如度矩陣、參數(shù)矩陣、結(jié)構(gòu)矩陣和距離矩陣）并求解其特征多項(xiàng)式來(lái)實(shí)現(xiàn)同構(gòu)判定[6-8]?；诰幋a比較的方法中，最大碼法通過(guò)構(gòu)件重新編號(hào)生成新的鄰接矩陣，并利用二進(jìn)制編碼進(jìn)行判定[9]，而最小碼法則通過(guò)優(yōu)化鄰接矩陣上的三角結(jié)構(gòu)來(lái)簡(jiǎn)化判定過(guò)程[10-11]。最大（?。┐a法均是對(duì)運(yùn)動(dòng)鏈進(jìn)行新標(biāo)記的算法，當(dāng)構(gòu)件數(shù)增加時(shí)，二進(jìn)制序列的大小也增加，其結(jié)果是計(jì)算復(fù)雜性增大，其實(shí)質(zhì)也是一種增加約束距離的最大最小的鄰接矩陣關(guān)系比較。哈明數(shù)法是先建立鄰接矩陣，通過(guò)對(duì)哈明數(shù)公式進(jìn)行 n（n-1）/2 次 Φ_n 為構(gòu)件總數(shù)）計(jì)算獲得哈明數(shù)矩陣，由哈明數(shù)矩陣獲得一系列的哈明數(shù)串，通過(guò)判定所獲得的哈明數(shù)串是否相等來(lái)實(shí)現(xiàn)同構(gòu)判定[12-13]。距離法則通過(guò)提取構(gòu)件間的距離信息生成路徑碼或距離序列串，通過(guò)比較所獲得的路徑碼或距離序列串是否相同來(lái)獲取同構(gòu)判定的結(jié)果[14-15]。該方法將計(jì)算復(fù)雜度從 n² 降低到n（n-1）/2 。最大周長(zhǎng)環(huán)表示法通過(guò)對(duì)基本環(huán)路集中的環(huán)路進(jìn)行 2^L-1 （ ?L 為獨(dú)立環(huán)路數(shù)）次合并操作獲得最大周長(zhǎng)環(huán)，進(jìn)一步獲得規(guī)范鄰接矩陣，通過(guò)對(duì)比有限幾個(gè)可能的規(guī)范鄰接矩陣獲得同構(gòu)判定結(jié)果[16]。

上述已有的代表性同構(gòu)判定方法通?；谶\(yùn)動(dòng)鏈的鄰接矩陣，提取某些結(jié)構(gòu)特性（如構(gòu)件連接距離、多元構(gòu)件類型、最大周長(zhǎng)環(huán)等）作為判定依據(jù)。然而，這些方法無(wú)法實(shí)現(xiàn)反向推導(dǎo)出運(yùn)動(dòng)鏈的所有結(jié)構(gòu)信息，即信息提取的非全面性，而用運(yùn)動(dòng)鏈的部分結(jié)構(gòu)特性作為運(yùn)動(dòng)鏈?zhǔn)欠裢瑯?gòu)的判定依據(jù)會(huì)導(dǎo)致同構(gòu)判定理論正確性存疑。如哈明數(shù)方法[14]存在反例的根本原因在于，這種方法提取的信息只有構(gòu)件之間的連接關(guān)系，而沒(méi)有構(gòu)件類型、復(fù)鉸類型以及復(fù)鉸連接了哪些構(gòu)件等信息。此外在這些方法中，有的方法提取信息過(guò)程非常繁瑣復(fù)雜。

矩陣便于存儲(chǔ)數(shù)據(jù)信息和進(jìn)行計(jì)算操作，被廣泛應(yīng)用于分析和解決機(jī)構(gòu)運(yùn)動(dòng)鏈型綜合[17]、同構(gòu)判定[18]、拓?fù)洵h(huán)路圖自動(dòng)生成[19]、變胞機(jī)構(gòu)的構(gòu)態(tài)描述[20]等研究領(lǐng)域。找到合適的方法表述機(jī)構(gòu)信息是研究和分析機(jī)構(gòu)的重要前提。在描述機(jī)構(gòu)運(yùn)動(dòng)鏈時(shí)，代表性的有鄰接矩陣和關(guān)聯(lián)矩陣，以及基于此的改進(jìn)矩陣等[21]。表達(dá)運(yùn)動(dòng)鏈時(shí)，無(wú)論是鄰接矩陣還是關(guān)聯(lián)矩陣，該構(gòu)件是否為多元構(gòu)件、是否含復(fù)鉸，以及多元構(gòu)件結(jié)構(gòu)幾何尺寸等信息都沒(méi)有包含在內(nèi)。即便是后續(xù)增加了多元構(gòu)件信息的度矩陣，以及前述鄰接矩陣、關(guān)聯(lián)矩陣及其改進(jìn)矩陣，均無(wú)法反向推導(dǎo)出結(jié)構(gòu)信息完整的運(yùn)動(dòng)鏈。以上述矩陣信息作為運(yùn)動(dòng)鏈的同構(gòu)判定原理，在理論分析上無(wú)法提供充分必要證明。

本文提出了一種新的表達(dá)運(yùn)動(dòng)鏈的全息矩陣，分析了矩陣的一些特性，如多元構(gòu)件判定定理、多元復(fù)鉸判定定理等，提出了一種新的同構(gòu)判定方法一—全息下三角矩陣變換對(duì)比法。

1描述運(yùn)動(dòng)鏈的全息矩陣

1.1 全息矩陣的定義

在使用計(jì)算機(jī)對(duì)全鉸鏈機(jī)構(gòu)進(jìn)行運(yùn)動(dòng)學(xué)仿真時(shí)，只需要知道機(jī)構(gòu)中關(guān)鍵點(diǎn)（兩構(gòu)件的連接點(diǎn)，該點(diǎn)可能對(duì)應(yīng)多個(gè)運(yùn)動(dòng)副鉸接）坐標(biāo)，以及該關(guān)鍵點(diǎn)處構(gòu)件的連接運(yùn)動(dòng)副元素，即可知曉機(jī)構(gòu)的全部結(jié)構(gòu)信息，并繪制出機(jī)構(gòu)?；谶@種思想，本文提出了一種新的運(yùn)動(dòng)鏈全息矩陣表達(dá)方法，運(yùn)動(dòng)鏈的結(jié)構(gòu)信息用全息矩陣（matrixwithwholeinformation， MWI）M 描述如下：

該矩陣為一個(gè) n_p×n_p 矩陣， n_p 為運(yùn)動(dòng)鏈的關(guān)鍵點(diǎn)數(shù)。關(guān)鍵點(diǎn)即構(gòu)件之間的連接點(diǎn)。若無(wú)復(fù)鉸，則關(guān)鍵點(diǎn)數(shù)對(duì)應(yīng)運(yùn)動(dòng)副數(shù)；若有復(fù)鉸，則多個(gè)構(gòu)件間的連接點(diǎn)為同一個(gè)關(guān)鍵點(diǎn)，此時(shí)關(guān)鍵點(diǎn)數(shù)少于運(yùn)動(dòng)副數(shù)。

矩陣對(duì)角線元素 a_i，i 為運(yùn)動(dòng)鏈中兩相鄰構(gòu)件的連接關(guān)鍵點(diǎn)對(duì)應(yīng)的運(yùn)動(dòng)副元素，如運(yùn)動(dòng)副元素有移動(dòng)副P、轉(zhuǎn)動(dòng)副R、球面副S等。本文只研究全轉(zhuǎn)副的運(yùn)動(dòng)鏈，所以 a_i，i=R 。

下三角矩陣元素 a_i，j（igt;j） 為兩關(guān)鍵點(diǎn) i 和j 所在的構(gòu)件對(duì)應(yīng)的編號(hào) k ，構(gòu)件編號(hào)從1開(kāi)始賦值，因此機(jī)構(gòu)中的構(gòu)件數(shù)就是下三角矩陣中最大的構(gòu)件編號(hào)值。由于運(yùn)動(dòng)鏈中可能有多元構(gòu)件，對(duì)應(yīng)有多個(gè)關(guān)鍵點(diǎn)，因此在下三角矩陣元素中可能出現(xiàn)多個(gè)元素具有相同值。若兩關(guān)鍵點(diǎn) i 和 j 之間無(wú)實(shí)際構(gòu)件，則 a_i，j=0 。

上三角矩陣 l_i，j（ii，j 表示構(gòu)件中編號(hào)為 i，j 的兩關(guān)鍵點(diǎn)之間的實(shí)際長(zhǎng)度值。若兩關(guān)鍵點(diǎn) i 和 j 之間無(wú)實(shí)際構(gòu)件，即兩關(guān)鍵點(diǎn)不在同一構(gòu)件上，則 l_i，j=0 。

圖1a所示的全鉸鏈運(yùn)動(dòng)鏈結(jié)構(gòu)含1個(gè)四元構(gòu)件、2個(gè)三元構(gòu)件、1個(gè)四元復(fù)鉸、2個(gè)三元復(fù)鉸，總計(jì)由12個(gè)桿件、16個(gè)鉸鏈和5個(gè)環(huán)組成，且其自由度為1，構(gòu)件編號(hào)和關(guān)鍵點(diǎn)（構(gòu)件之間的鉸接點(diǎn)）編號(hào)標(biāo)注如圖所示。根據(jù)運(yùn)動(dòng)鏈的雙色拓?fù)鋱D定義[22]，黑色實(shí)心圓代表構(gòu)件，引出的線條代表運(yùn)動(dòng)副，此處為關(guān)鍵點(diǎn)，空心圓代表復(fù)鉸，空心圓引出的線條都是同一個(gè)關(guān)鍵點(diǎn)，圖1b為其雙色拓?fù)鋱D。

該運(yùn)動(dòng)鏈對(duì)應(yīng)的鄰接矩陣（adjacencymatrix，AM）A為

對(duì)比鄰接矩陣 A 和全息矩陣 M ，同樣是 12× 12矩陣，如果一個(gè)構(gòu)件同時(shí)與多個(gè)構(gòu)件連接，則判斷該構(gòu)件是否為多元構(gòu)件的總時(shí)間復(fù)雜度為O（n²） ，近似來(lái)說(shuō)，時(shí)間復(fù)雜度與構(gòu)件節(jié)點(diǎn)個(gè)數(shù)的平方成正比。

全息矩陣相較于鄰接矩陣，可以清晰完整地表達(dá)運(yùn)動(dòng)鏈結(jié)構(gòu)信息，如構(gòu)件數(shù) Ω_n 、運(yùn)動(dòng)副數(shù) p ！兩構(gòu)件間是否有連接、連接兩構(gòu)件的運(yùn)動(dòng)副（此處只討論全鉸鏈情況）、某處連接是否為復(fù)鉸、某構(gòu)件是否為多元構(gòu)件、構(gòu)件上兩關(guān)鍵點(diǎn)間的長(zhǎng)度l_i，j （包括多元構(gòu)件的各邊長(zhǎng)度）等。一個(gè)全息矩陣可以對(duì)應(yīng)結(jié)構(gòu)信息唯一確定的運(yùn)動(dòng)鏈，也就是給定一個(gè)描述正確的下三角矩陣，可以簡(jiǎn)單分析和推導(dǎo)出對(duì)應(yīng)的運(yùn)動(dòng)鏈結(jié)構(gòu)。如根據(jù)全息矩陣M 可以反向推導(dǎo)出唯一確定的圖1a所示的運(yùn)動(dòng)鏈結(jié)構(gòu)圖。該特點(diǎn)是已有描述機(jī)構(gòu)和運(yùn)動(dòng)鏈的鄰接、關(guān)聯(lián)、環(huán)路等矩陣所不具備的。

1.2 全息矩陣相關(guān)特征參數(shù)的判定定理

本文只研究全鉸鏈運(yùn)動(dòng)鏈，對(duì)表達(dá)運(yùn)動(dòng)鏈的全息矩陣只研究下三角矩陣。

定理1（多元連桿判定）運(yùn)動(dòng)鏈對(duì)應(yīng)的全息下三角矩陣中的元素為構(gòu)件編號(hào) i 和0，某個(gè) n 元構(gòu)件有 n 個(gè)關(guān)鍵點(diǎn)，對(duì)應(yīng)其相同的構(gòu)件編號(hào) i 出現(xiàn)在下三角矩陣的數(shù)量應(yīng)為 C_n² ，且該全息矩陣中C_n² 個(gè)元素對(duì)應(yīng)的矩陣行和列的不同數(shù)字（也是關(guān)鍵點(diǎn)數(shù)）為 n 個(gè)。進(jìn)一步，當(dāng)某個(gè)關(guān)鍵點(diǎn)對(duì)應(yīng)的下三角矩陣的所有行與列元素中出現(xiàn)了 k 個(gè)相同的數(shù)值 j ，則多元構(gòu)件 j 為 （k+1） 元構(gòu)件。

例如：在全息矩陣中，某個(gè)三元構(gòu)件編號(hào)為2，數(shù)值2在全息矩陣中出現(xiàn)3次，分別對(duì)應(yīng)全息矩陣的元素 ，有3個(gè)關(guān)鍵點(diǎn)7、8、9。

對(duì)應(yīng)的全息矩陣 M 為

推論1當(dāng)知道 n 元構(gòu)件上某個(gè)關(guān)鍵點(diǎn)對(duì)應(yīng)的行和列元素位置之后，其中包含的構(gòu)件 i 其余關(guān)鍵點(diǎn)和編號(hào) i 出現(xiàn)的位置都可以確定。

如四元構(gòu)件編號(hào)為1，在關(guān)鍵點(diǎn)4處對(duì)應(yīng)的行和列元素轉(zhuǎn)變?yōu)橐痪S數(shù)組 {1，1，1，4，0，0，0，0，0 0，0}，其中編號(hào)為1的元素為 a_?4，1…a_?4，2…a_?4，3 ，則可判定構(gòu)件1為四元構(gòu)件，其余關(guān)鍵點(diǎn)為1、2、3，且構(gòu)件編號(hào)1對(duì)應(yīng)的其他位置也可以確定為 。如編號(hào)為4的元素為 a_5，4 ，則可判定構(gòu)件4為二元構(gòu)件，其他位置不再出現(xiàn)構(gòu)件4。

如提取關(guān)鍵點(diǎn)9上對(duì)應(yīng)的行與列元素為一維數(shù)組 {0，0，0，0，0，0，2，2，3，3，0} ，則可判斷構(gòu)件2和3都是三元構(gòu)件。構(gòu)件編號(hào)2對(duì)應(yīng)的其他位置可確定為 a_8，7 ，構(gòu)件編號(hào)3對(duì)應(yīng)的其他位置也可確定為a11，10 。

從推論1和案例分析可知，當(dāng)將下三角矩陣的某個(gè)關(guān)鍵點(diǎn)單獨(dú)提取出對(duì)應(yīng)的行和列元素時(shí)，同一個(gè)構(gòu)件上的不同關(guān)鍵點(diǎn)之間還是存在耦合關(guān)系的。例如關(guān)鍵點(diǎn)7、8、9均為構(gòu)件2上的三個(gè)關(guān)鍵點(diǎn)，提取其下三角元素分別為 {0，0，0，0，5，0，2 2，0，0，0} 、 {0，0，0，0，0，0，8，2，2，0，0，0} 和 {0，0，0 ，0，0，0，2，2，3，3，0} 。

定理2（多元復(fù)鉸判定）運(yùn)動(dòng)鏈對(duì)應(yīng)的全息下三角矩陣中，若關(guān)鍵點(diǎn) i 對(duì)應(yīng)的行元素 a_i，j 和列元素 a_k，i（0p） 中有 n 個(gè)非0且不相等的值，表明該處復(fù)鉸連接了 n 個(gè)不同構(gòu)件，則關(guān)鍵點(diǎn) i 處的鉸鏈為 n 元復(fù)鉸。

如圖1所示，提取下三角矩陣中關(guān)鍵點(diǎn)6對(duì)應(yīng)的行和列元素為一維數(shù)組 {0，0，7，0，6，0，8，0 .9，0，0} ，其中有4個(gè)不相同且不為0的數(shù)字6、7、8、9，則可判定該處為四元復(fù)鉸，分別對(duì)應(yīng)相互鉸接的4個(gè)構(gòu)件。

定理3（桿件編號(hào)變換規(guī)律）改變運(yùn)動(dòng)鏈中的桿件編號(hào)相當(dāng)于給構(gòu)件取了一個(gè)不同的序列號(hào)而已，不影響運(yùn)動(dòng)鏈的連接關(guān)系和結(jié)構(gòu)，只是重新對(duì)運(yùn)動(dòng)鏈的構(gòu)件進(jìn)行了編號(hào)。對(duì)應(yīng)全息下三角矩陣中元素值為0的位置不變，非0的對(duì)應(yīng)的桿件編號(hào)數(shù)值相應(yīng)改變。

定理4（關(guān)鍵點(diǎn)編號(hào)變換規(guī)律）改變運(yùn)動(dòng)鏈中的關(guān)鍵點(diǎn)編號(hào)不影響運(yùn)動(dòng)鏈的連接關(guān)系和結(jié)構(gòu)，對(duì)應(yīng)全息下三角矩陣中構(gòu)件的性質(zhì)（是否多元連桿、兩構(gòu)件間連接關(guān)系等）不變，其結(jié)果是各關(guān)鍵點(diǎn)（如 i 和 j ）對(duì)應(yīng)的行和列的位置互換。

例如：將式（3）的關(guān)鍵點(diǎn)3和4、構(gòu)件編號(hào)7和8互換后得到新的全息矩陣為

2基于全息下三角矩陣的同構(gòu)判定

基于上述分析，全息下三角矩陣可以確定結(jié)構(gòu)信息唯一的運(yùn)動(dòng)鏈，本文提出了一種基于全息下三角矩陣變換對(duì)比的同構(gòu)判定新方法。以圖2所示兩個(gè)12構(gòu)件運(yùn)動(dòng)鏈[23]的拓?fù)鋱D同構(gòu)判定為例，說(shuō)明基于全息下三角矩陣對(duì)比變換的同構(gòu)判定方法的具體步驟和分析思路。

1）首先檢索并獲得兩個(gè)運(yùn)動(dòng)鏈的結(jié)構(gòu)參數(shù)，如構(gòu)件類型和構(gòu)件數(shù)、多元復(fù)鉸類型和數(shù)量，獨(dú)立環(huán)路數(shù)等，再進(jìn)行比較。以運(yùn)動(dòng)鏈總構(gòu)件數(shù) n 、低副數(shù) p 、自由度數(shù) F 、獨(dú)立環(huán)路數(shù) L 、關(guān)鍵點(diǎn)數(shù) n_p 、多元構(gòu)件數(shù)和多元復(fù)鉸數(shù) 的組合 {n，p，F(xiàn)，L，n_p，n₂，n₃，J₃，…，n_L+1，J_L+1} 作為運(yùn)動(dòng)鏈結(jié)構(gòu)參數(shù)。上述運(yùn)動(dòng)鏈的基本結(jié)構(gòu)參數(shù)如不相同，則可以直接判定不同構(gòu)。圖2中，運(yùn)動(dòng)鏈1和2的結(jié)構(gòu)參數(shù)都是{12，16，1，5，16，5，6，0，1，0，0，0，0，0} 。

2）對(duì)運(yùn)動(dòng)鏈1和2的構(gòu)件和關(guān)鍵點(diǎn)進(jìn)行隨機(jī)編號(hào)，如圖2所示，用全息下三角矩陣表示，獲得初始的下三角矩陣 M₁ 和 M₂ ，將下三角矩陣 M₁ 作為基準(zhǔn)矩陣，下三角矩陣 M₂ 作為變換矩陣。

3）獲得初始矩陣 M₁ 和 M₂ 各個(gè)關(guān)鍵點(diǎn)對(duì)應(yīng)的下三角矩陣元素的信息，對(duì)于 n_p 個(gè)關(guān)鍵點(diǎn)，每個(gè)關(guān)鍵點(diǎn) i 對(duì)應(yīng)的下三角行和列均有 個(gè)元素 （a_i，j（jk，i（kgt;i）） 。對(duì)于每一個(gè)關(guān)鍵點(diǎn) i ，獲得其非0元素的總個(gè)數(shù)，以及相同非0元素出現(xiàn)次數(shù)，按數(shù)字從大到小排列，相同的數(shù)字不區(qū)分排序先后。獲得所有關(guān)鍵點(diǎn)對(duì)應(yīng)的元素信息從大到小排列的一維數(shù)組，并將這些數(shù)組按照相同值進(jìn)行分類?；鶞?zhǔn)矩陣 M₁ 為

變換矩陣 M₂ 為

如初始的基準(zhǔn)矩陣 M₁ 中，關(guān)鍵點(diǎn)1對(duì)應(yīng)元素的一維數(shù)組為 {1，1，1，0，0，3，3，0，0，0，0，0，0，0，0，0} ，非0元素的總個(gè)數(shù)為5，不同的非0元素有2個(gè)，其中元素“1”出現(xiàn)3次，即構(gòu)件1為四元構(gòu)件，元素“3”出現(xiàn)2次，即構(gòu)件3為三元構(gòu)件，則關(guān)鍵點(diǎn)1對(duì)應(yīng)的數(shù)組可表示為 {5，3，2} ，從該數(shù)組信息中可以得到前述多元構(gòu)件特性，構(gòu)件1為四元構(gòu)件，構(gòu)件3為三元構(gòu)件。表1所示為2個(gè)運(yùn)動(dòng)鏈的初始矩陣所對(duì)應(yīng)的關(guān)鍵點(diǎn)數(shù)字特征值，表2給出了數(shù)值相同的分組，16個(gè)關(guān)鍵點(diǎn)共分為了4組。關(guān)鍵點(diǎn)數(shù)組信息是運(yùn)動(dòng)鏈同構(gòu)的必要條件之一，當(dāng)基準(zhǔn)矩

表1兩個(gè)12桿運(yùn)動(dòng)鏈關(guān)鍵點(diǎn)數(shù)字特征值

陣 M₁ 中的某個(gè)關(guān)鍵點(diǎn)的數(shù)組與變換矩陣 M₂ 對(duì)應(yīng)組別中的關(guān)鍵點(diǎn)數(shù)組均無(wú)法匹配時(shí)則可判斷兩個(gè)運(yùn)動(dòng)鏈不同構(gòu)。

4）獲得兩個(gè)矩陣的關(guān)鍵點(diǎn)對(duì)應(yīng)數(shù)字特征值后，按照其中不同組關(guān)鍵點(diǎn)的數(shù)值大小進(jìn)行排序，相同值的同組關(guān)鍵點(diǎn)排列次序隨機(jī)。根據(jù)數(shù)字特征值是否唯一或多組相同，將關(guān)鍵點(diǎn)區(qū)分為確定的關(guān)鍵點(diǎn)和待確定的關(guān)鍵點(diǎn)。表2中沒(méi)有一組關(guān)鍵點(diǎn)的數(shù)字特征值是唯一的，根據(jù)數(shù)字特征值相同劃分為4組待確定關(guān)鍵點(diǎn)。矩陣 M₁ 中，同組中存在多個(gè)特征數(shù)字相同的情況，4組關(guān)鍵點(diǎn)內(nèi)的排序先隨機(jī)排列，對(duì)應(yīng)運(yùn)動(dòng)鏈1所有關(guān)鍵點(diǎn)的初始排序如下：

經(jīng)過(guò)上述變化后，基準(zhǔn)矩陣中只有上述8個(gè)關(guān)鍵點(diǎn)的位置待確定。存在對(duì)應(yīng) P₂²×P₂²×P₂²× P₂²=16 種變換矩陣 M₂ 。限于篇幅，這里不一一列舉。

上述16個(gè)變換矩陣 M₂ 對(duì)應(yīng)的運(yùn)動(dòng)鏈2與基準(zhǔn)矩陣 M_i 對(duì)應(yīng)的運(yùn)動(dòng)鏈1若同構(gòu)，則其關(guān)鍵點(diǎn)的位置與基準(zhǔn)矩陣 M₁ 中關(guān)鍵點(diǎn)具有一一映射關(guān)系。

6）根據(jù)構(gòu)件編號(hào)變換原則，將所有衍生出來(lái)的變換矩陣 M₂ 逐一與基準(zhǔn)矩陣 M₁ 進(jìn)行匹配對(duì)比和同構(gòu)判定。

同構(gòu)判定原則：根據(jù)關(guān)鍵點(diǎn)互換定理和構(gòu)件編號(hào)互換定理，在假定運(yùn)動(dòng)鏈2和運(yùn)動(dòng)鏈1的關(guān)鍵點(diǎn)具有逐一映射關(guān)系的前提下，對(duì)應(yīng)的下三角矩陣 M₁ 和 M₂ 中，0元素的位置相同，非0元素的位置對(duì)應(yīng)的構(gòu)件編號(hào)可以不同（對(duì)應(yīng)著構(gòu)件編號(hào)的逐一映射關(guān)系），但是多元構(gòu)件類型必須相同，同一多元構(gòu)件對(duì)應(yīng)的同一構(gòu)件編號(hào)在兩個(gè)矩陣中多個(gè)位置是相同的。

對(duì)角線標(biāo)記了隨機(jī)排序后的初始關(guān)鍵點(diǎn)編號(hào)。同理，如果對(duì)變換矩陣 M₂ 按照上述規(guī)則進(jìn)行關(guān)鍵點(diǎn)排序時(shí)，理論上一共有 P₂²×P₂²×P₄⁴×P₈⁸= 3870720種匹配的可能。

5）對(duì)于同一組的關(guān)鍵點(diǎn)，通過(guò)關(guān)鍵點(diǎn)互換，將非0元素放置到該組的前幾行位置。對(duì)式（7）中每組進(jìn)行分析和前移，本案例中只需要對(duì)第四組中12、15進(jìn)行互換，獲得的新基準(zhǔn)矩陣 M₁ 如下：

檢索判定的操作為： ① 基準(zhǔn)矩陣 M₁ 中某個(gè)位置出現(xiàn)0，對(duì)應(yīng)變換矩陣 M₂ 中相同位置必須是0； ② 某個(gè)位置出現(xiàn)非0元素 i ，檢索 i 出現(xiàn)在基準(zhǔn)矩陣 M₁ 的位置，對(duì)應(yīng)變換矩陣 M₂ 中相同的位置必須是同一個(gè)非0元素 j 。

將得到的變換矩陣 M₂ 依據(jù)同構(gòu)判定原則和上述操作進(jìn)行對(duì)比分析，若其中某個(gè)變換矩陣符合，則運(yùn)動(dòng)鏈1和2同構(gòu)，剩余的變換矩陣 M₂ 不用繼續(xù)判別；若所有的變換矩陣 M₂ 都不符合，則運(yùn)動(dòng)鏈1和2不同構(gòu)。上述16個(gè)變換矩陣中的一個(gè)如下：

將式（9）與式（8）基準(zhǔn)矩陣 M₁ 進(jìn)行對(duì)比分析，式（8）中 M_6，1 是非0元素3，式（9）中為0元素，因此該情況不同構(gòu)。本方法是在下三角矩陣可唯一確定運(yùn)動(dòng)鏈結(jié)構(gòu)的理論分析基礎(chǔ)上，基于2個(gè)重要的定理（構(gòu)件編號(hào)變換定理和關(guān)鍵點(diǎn)編號(hào)變換定理），將運(yùn)動(dòng)鏈用全息下三角矩陣表達(dá)，選擇其中矩陣 M₁ 作為基準(zhǔn)矩陣，經(jīng)過(guò)分組排列和同組非0元素前移后，分兩步將關(guān)鍵點(diǎn)進(jìn)行細(xì)分，得到確定的關(guān)鍵點(diǎn)和待確定的關(guān)鍵點(diǎn)。在假定變換矩陣 M₂ 中所有關(guān)鍵點(diǎn)與基準(zhǔn)矩陣 M₁ 中所有關(guān)鍵點(diǎn)位置逐一對(duì)應(yīng)的情況下，將有限個(gè)變換矩陣 M₂ 與基準(zhǔn)矩陣 M₁ 進(jìn)行數(shù)字對(duì)比，可快速獲得同構(gòu)判定結(jié)果。

上述基于全息下三角矩陣進(jìn)行運(yùn)動(dòng)鏈同構(gòu)判定方法的思路具體如圖3所示。

3 同構(gòu)判定舉例

應(yīng)用本方法完成文獻(xiàn)［24]中的28桿運(yùn)動(dòng)鏈的判定，構(gòu)件與關(guān)鍵點(diǎn)編號(hào)如圖4所示，主要判定步驟如下。

1）獲取兩個(gè)運(yùn)動(dòng)鏈的結(jié)構(gòu)參數(shù) {n，?，F(xiàn)，L n ₂，n₃，J₃，…，n₁₄，J₁₄}={28，40，1，13，40，4，24 ，0，0，…，0，0} 。

2）對(duì)圖4中運(yùn)動(dòng)鏈1和2的構(gòu)件和關(guān)鍵點(diǎn)隨機(jī)編號(hào)，獲得初始的下三角矩陣 M₁ 和 M₂ （具體矩陣表達(dá)式掃描本文首頁(yè)OSID碼獲?。?。

3）記錄初始矩陣 M₁ 和 M₂ 的關(guān)鍵點(diǎn)特征信息，如表3所示。

4）對(duì)初始矩陣 M₁ 和 M₂ 的關(guān)鍵點(diǎn)信息按確定和待確定區(qū)域劃分，重新排列位置。如表3所示，關(guān)鍵點(diǎn)的數(shù)組信息分為2組，關(guān)鍵點(diǎn)數(shù)字特征值分別為{3，2，1}和 {4，2，2} ，其中{3，2，1}的關(guān)鍵點(diǎn)有8個(gè)， {4，2，2} 所對(duì)應(yīng)的關(guān)鍵點(diǎn)有32個(gè)，初定{3，2，1}作為第一組，該組上的8個(gè)關(guān)鍵點(diǎn)隨機(jī)排序。

限于篇幅，后續(xù)優(yōu)化基準(zhǔn)矩陣，對(duì)變換矩陣進(jìn)行關(guān)鍵點(diǎn)的對(duì)比、變換等操作省略，最終的判定結(jié)果與之符合，兩運(yùn)動(dòng)鏈同構(gòu)。通過(guò)比較分析，28桿運(yùn)動(dòng)鏈具有強(qiáng)對(duì)稱性，能夠找到兩個(gè)運(yùn)動(dòng)鏈的構(gòu)件編號(hào)與關(guān)鍵點(diǎn)編號(hào)之間的多種映射關(guān)系，表4給出了其中兩種映射情況。

由上述具有強(qiáng)對(duì)稱性的28桿運(yùn)動(dòng)鏈可知，對(duì)于高對(duì)稱性的圖或運(yùn)動(dòng)鏈，在對(duì)關(guān)鍵點(diǎn)進(jìn)行分布確定時(shí)，關(guān)鍵點(diǎn)對(duì)應(yīng)信息大量趨同，導(dǎo)致對(duì)應(yīng)有大量的變換矩陣 M₂ 。對(duì)于結(jié)構(gòu)對(duì)稱性弱的運(yùn)動(dòng)鏈，利用下三角矩陣自身包含信息素較多、耦合性強(qiáng)的優(yōu)勢(shì)，可以快速地確定基準(zhǔn)矩陣中的大量關(guān)鍵點(diǎn)對(duì)應(yīng)的位置，后續(xù)產(chǎn)生的變換矩陣 M₂ 數(shù)量較少，可以快速對(duì)比獲得運(yùn)動(dòng)鏈之間同構(gòu)判定結(jié)果。

對(duì)于不同構(gòu)的運(yùn)動(dòng)鏈，基于全息下三角矩陣變換對(duì)比的同構(gòu)判定方法往往只需要判定步驟中的前幾步即可發(fā)現(xiàn)運(yùn)動(dòng)鏈結(jié)構(gòu)的差異性，判定效率較高。如對(duì)文獻(xiàn)[25]中的同構(gòu)判定案例，如圖5所示，主要判定步驟如下。

1）獲取兩個(gè)運(yùn)動(dòng)鏈的結(jié)構(gòu)參數(shù)均為 {n，p ，F(xiàn)，L，n₂，n₃，J₃，…，n₁₄，J₁₄}={15，27，-12，13 ，27，6，0，0，6，0，0，3，0，0，…，0，0} 。

2）對(duì)圖5中運(yùn)動(dòng)鏈1和2的構(gòu)件和關(guān)鍵點(diǎn)隨機(jī)編號(hào)，獲得初始的下三角矩陣 M₃ 和 M₄ （矩陣表述掃描OSID碼獲?。?。

3）記錄初始矩陣 M₃ 和 M₄ 的關(guān)鍵點(diǎn)特征信息，如表5所示。

4）對(duì)于初始矩陣 M₃ 和 M₄ ，將關(guān)鍵點(diǎn)區(qū)分為確定的關(guān)鍵點(diǎn)和待確定的關(guān)鍵點(diǎn)，重新排列位置。如表5所示，關(guān)鍵點(diǎn)的數(shù)組信息分為5組，關(guān)鍵點(diǎn)的數(shù)字特征值可分為 {10，5，5} 、{8，5，3}、 {6 3，3}，{6，5，1}，{4，3，1} 五組，其中第一組 {10，5 ，5}的關(guān)鍵點(diǎn)有3個(gè)，其余區(qū)域所對(duì)應(yīng)的關(guān)鍵點(diǎn)均為6個(gè)，則 {10，5，5} 中的關(guān)鍵點(diǎn)作為第一組。對(duì)基準(zhǔn)矩陣 M₃^′"進(jìn)行變換分析，存在8組可兩兩互換的位置待確定，即存在對(duì)應(yīng) P₂²×P₂²×P₂²×P₂²× P₂²×P₂²×P₂²×P₂²=256 種變換矩陣 M₄^′"。

表4兩個(gè)28桿運(yùn)動(dòng)鏈的構(gòu)件與關(guān)鍵點(diǎn)映射關(guān)系

表515桿運(yùn)動(dòng)鏈重新排序的關(guān)鍵點(diǎn)數(shù)字特征值

限于篇幅，后續(xù)優(yōu)化基準(zhǔn)矩陣，對(duì)變換矩陣進(jìn)行關(guān)鍵點(diǎn)的對(duì)比、變換等操作省略，最終得到的基準(zhǔn)矩陣 M₃^′ 和變換矩陣 M₄^′ （矩陣表達(dá)掃描OSID碼獲取）。

由上述兩個(gè)全息下三角矩陣可以得到， M₃^′ 中M_25，11 位置上是非0元素 12，M₄^′ 中相應(yīng)位置為0元素。

繼續(xù)對(duì)上述案例中衍生出來(lái)的其他變換矩陣M₄^′ 進(jìn)行對(duì)比判定，都得到不同構(gòu)的結(jié)果，因此可判定上述2個(gè)運(yùn)動(dòng)鏈不同構(gòu)。

4基于全息下三角矩陣變換對(duì)比的同構(gòu)判定方法總結(jié)

綜上理論與案例分析，采用全息下三角矩陣的變換對(duì)比法進(jìn)行同構(gòu)判定具有以下特點(diǎn)。

1）同構(gòu)判定方法的科學(xué)性。該同構(gòu)判定方法建立在全息下三角矩陣可唯一確定運(yùn)動(dòng)鏈結(jié)構(gòu)的基礎(chǔ)上，即一個(gè)結(jié)構(gòu)描述正確的全息下三角矩陣與對(duì)應(yīng)的運(yùn)動(dòng)鏈結(jié)構(gòu)可以相互推導(dǎo)得到，判定原理為是否同構(gòu)的充要條件，其科學(xué)性和準(zhǔn)確性簡(jiǎn)單易懂、一目了然。

2）同構(gòu)判定方法的計(jì)算量小。該方法只需要檢索矩陣關(guān)鍵點(diǎn)信息和有限個(gè)關(guān)鍵點(diǎn)換位，獲得一定數(shù)量的變換矩陣 M₂ 與基準(zhǔn)矩陣 M₁ 進(jìn)行對(duì)比判定，不需要提取運(yùn)動(dòng)鏈的環(huán)路信息進(jìn)行運(yùn)算，也不需要進(jìn)行特征值或特征向量的計(jì)算。運(yùn)用所提出的同構(gòu)判定方法，對(duì)于對(duì)稱性弱的運(yùn)動(dòng)鏈，具有無(wú)可比擬的計(jì)算量小的優(yōu)勢(shì)；對(duì)于對(duì)稱性強(qiáng)的運(yùn)動(dòng)鏈或圖，無(wú)論采用哪一種同構(gòu)判定方法和對(duì)應(yīng)的特性，如最大周長(zhǎng)環(huán)、本文提出的方法等，都對(duì)應(yīng)有多種可能性，從而導(dǎo)致計(jì)算分析量的幾何級(jí)數(shù)增加。當(dāng)運(yùn)動(dòng)鏈的對(duì)稱性較強(qiáng)時(shí)，可能矩陣中同一區(qū)域的關(guān)鍵點(diǎn)有多個(gè)，在進(jìn)行判定時(shí)，只需進(jìn)行分組排列并將同組非0元素前移，將關(guān)鍵點(diǎn)進(jìn)行細(xì)分，因此該種方法的計(jì)算量主要是分組的檢索量及少數(shù)關(guān)鍵點(diǎn)前移的操作。后續(xù)的變換矩陣 M₂ 與基準(zhǔn)矩陣 M₁ 的逐一對(duì)比，僅簡(jiǎn)單地進(jìn)行元素對(duì)比即可，因此對(duì)比量為 C_np²=n_p× （n_p-1）/2 ，每一次的對(duì)比量是對(duì)2個(gè)一維數(shù)組（n_p-1） 個(gè)元素的對(duì)比。圖6所示為本文所提出的方法與McKay和Ding算法的復(fù)雜性對(duì)比。

3）同構(gòu)判定方法的可編程性。由于同構(gòu)判定原理的簡(jiǎn)易性，故同構(gòu)判定規(guī)則也相對(duì)簡(jiǎn)單，則建立在全息下三角矩陣基礎(chǔ)上的對(duì)比分析非常利于計(jì)算機(jī)程序化設(shè)計(jì)。

5結(jié)論

1）本文提出了一種新的表達(dá)運(yùn)動(dòng)鏈的全息矩陣，重點(diǎn)分析了全息下三角矩陣的數(shù)字分布規(guī)則，下三角矩陣包含構(gòu)件類型、多元復(fù)鉸、構(gòu)件間的連接關(guān)系等大量信息，可唯一確定運(yùn)動(dòng)鏈的結(jié)構(gòu)，分析給出了構(gòu)件編號(hào)變化和關(guān)鍵點(diǎn)編號(hào)變化規(guī)律。

2）在全息下三角矩陣對(duì)應(yīng)確定的運(yùn)動(dòng)鏈結(jié)構(gòu)這一分析基礎(chǔ)上，提出了一種新的全息下三角矩陣變換對(duì)比的運(yùn)動(dòng)鏈同構(gòu)判定新方法。

3）該方法和已有的同構(gòu)判定方法比較，最大的優(yōu)點(diǎn)在于同構(gòu)判定原理簡(jiǎn)單易于理解，同構(gòu)判定規(guī)則簡(jiǎn)單，只有信息檢索和分類、矩陣之間數(shù)值元素分析對(duì)比等，無(wú)需對(duì)環(huán)路或特征值、特征向量等進(jìn)行計(jì)算，與現(xiàn)有同構(gòu)判定方法比較，分析計(jì)算量較小。

參考文獻(xiàn)：

[1]POZHBELKO V， ERMOSHINA E. Number Structural Synthesis and Enumeration Process of All Possible Sets of Multiple Joints for 1-DOF up to 5- loop 12-link Mechanisms on Base of New Mobility Equation[J]. Mechanism and Machine Theory， 2015，90：108-127.

[2]ZOU Yanhuo. An Algorithm for Structural Synthesis of Planar Simple and Multiple Joint Kinematic Chains[J]. Proceedings of Institution of Mechanical Engineers，Part C：Journal of Mechanical Engineering Science，2014，228（12）：2178-2192.

[3] WEN X，SUN W，WANG S，et al. A New Rigid Sub-chain Identification and Elimination Method of Kinematic Chains with Multiple Joints[J].Proceedings of the Institution of Mechanical Engineers，Part C：Journal of Mechanical Engineering Science， 2024，238（5）：1324-1339.

[4]DENG T，XU H，WU C，et al. Topological Symmetry Identification of Kinematic Chains Based on Topological Index[J]. Mechanism and Machine Theory，2020，154：104099.

[5] 丁華鋒，黃真，曹毅.運(yùn)動(dòng)鏈拓?fù)鋱D的自動(dòng)生成及圖 譜庫(kù)的建立[J].機(jī)械工程學(xué)報(bào)，2006，42（4）：32-36. DING Huafeng，HUANG Zhen，CAO Yi. The Automatic Generation of Motion Chain Topological Graph and the Establishment of a Diagram Library [J].Journal of Mechanical Engineering，2006，42 （4）：32-36.

[6]MRUTHYUNJAYA T S，BALASUBRAMANIAN H R.In Quest of a Reliable and Efficient Computational Test for Detection of Isomorphism in Kinematic Chains[J]. Mechanism and Machine Theory， 1987，22（2）：131-139.

[7]BALASUBRAMANIAN K，PARTHASARATHY K R. In Search of a Complete Invariant for Graphs[J]. Lecture Notes in Mathematics，1981，885（1） ：42-59.

[8]YAN H S，HWANG W M. Method for the Identification of Planar Linkage Chains[J]. Journal of Mechanisms， Transmissions， and Automation in Design，1983，105（4）：658-662.

[9]RAI R K，PUNJABI S. A New Algorithm of Links Labelling for the Isomorphism Detection of Various Kinematic Chains Using Binary Code[J]. Mechanism and Machine Theory，2018，131：1-32.

[10] AMBEKAR A G，AGRAWAL V P. CanonicalNumbering of Kinematic Chains and Isomorphism Problem：Min Code[J].Mechanism and Machine Theory，1987，22（5）：453-461.

[11]AMBEKAR A G，AGRAWAL V P. Identification of Kinematic Chains，Mechanisms，Path Generators and Function Generators Using Min Codes[J]. Mechanism and Machine Theory，1987，22（5） ：463-471.

[12]RAO A C，VARADA R D. Application of the Hamming Number Technique to Detect Isomorphism among Kinematic Chains and Inversions[J]. Mechanism and Machine Theory，1991，26（1） ：55-75.

[13] RAO A C，RAO C N. Loop Based Pseudo Hamming Values—I Testing Isomorphism and Rating Kinematic Chains[J].Mechanism and Machine Theory，1993，28（1）：113-127.

[14]KAMESHV V，RAO KM，RAO A BS. An Innovative Approach to Detect Isomorphism in Planar and GearedKinematic Chains Using Graph Theory[J]. Journal of Mechanical Design，2017， 139（12）：122301.

[15]SUN Liang，YE Zhizheng，CUI Rongjiang，et al. Compound Topological Invariant Based Method for Detecting Isomorphism in Planar Kinematic Chains [J]. Journal of Mechanisms and Robotics，2020，12 （5）：054504.

[16]DING Huafeng，HUANG Zhen. IsomorphismIdentification of Graphs： Especially for the Graphs of Kinematic Chains[J]. Mechanism and Machine Theory，2008，44（1）：122-139.

[17］CHU Jinkui，ZOU Yanhuo.An Algorithm for Structural Synthesis of Planar Simple and Multiple Joint Kinematic Chains[J]. Proceedings of the Institution of Mechanical Engineers，Part C：Journal of Mechanical Engineering Science，2014，228（12）： 2178-2192.

[18]WANG L，SUN L，CUI R，et al. Novel Loop Tree for the Similarity Recognition of Kinematic Chains［J].Mechanical Sciences，2022，13（1）： 371-386. （下轉(zhuǎn)第1221頁(yè)）