基于全息下三角矩陣變換對比的運動鏈同構判定方法

中圖分類號：TH112

DOI：10.3969/j.issn.1004-132X.2025.06.005 開放科學（資源服務）標識碼（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 引言

機構運動鏈構型綜合是機構學領域的一個難題，也是機構創新設計的核心研究內容[1]。在運動鏈型綜合過程中，運動鏈的生成方法[2]、剛性子鏈判定[3]、同構判定4]、拓撲圖和結構圖自動繪制[5]等關鍵技術問題都是必須解決的。

運動鏈的生成過程幾乎都伴隨著大量同構的運動鏈產生。同構判定過程需要將后續所有構型與前面不重復的構型進行逐一對比，需要 C_n² 次計算分析，占據了構型綜合過程的大部分計算分析量。研究人員將圖的同構判定引入機構學研究中，提出同構判定方法必須滿足以下要求，即提出并且能證明運動鏈結構唯一性判定依據、準確可靠、分析計算量小且便于程序化設計。

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

上述已有的代表性同構判定方法通常基于運動鏈的鄰接矩陣，提取某些結構特性（如構件連接距離、多元構件類型、最大周長環等）作為判定依據。然而，這些方法無法實現反向推導出運動鏈的所有結構信息，即信息提取的非全面性，而用運動鏈的部分結構特性作為運動鏈是否同構的判定依據會導致同構判定理論正確性存疑。如哈明數方法[14]存在反例的根本原因在于，這種方法提取的信息只有構件之間的連接關系，而沒有構件類型、復鉸類型以及復鉸連接了哪些構件等信息。此外在這些方法中，有的方法提取信息過程非常繁瑣復雜。

矩陣便于存儲數據信息和進行計算操作，被廣泛應用于分析和解決機構運動鏈型綜合[17]、同構判定[18]、拓撲環路圖自動生成[19]、變胞機構的構態描述[20]等研究領域。找到合適的方法表述機構信息是研究和分析機構的重要前提。在描述機構運動鏈時，代表性的有鄰接矩陣和關聯矩陣，以及基于此的改進矩陣等[21]。表達運動鏈時，無論是鄰接矩陣還是關聯矩陣，該構件是否為多元構件、是否含復鉸，以及多元構件結構幾何尺寸等信息都沒有包含在內。即便是后續增加了多元構件信息的度矩陣，以及前述鄰接矩陣、關聯矩陣及其改進矩陣，均無法反向推導出結構信息完整的運動鏈。以上述矩陣信息作為運動鏈的同構判定原理，在理論分析上無法提供充分必要證明。

本文提出了一種新的表達運動鏈的全息矩陣，分析了矩陣的一些特性，如多元構件判定定理、多元復鉸判定定理等，提出了一種新的同構判定方法一—全息下三角矩陣變換對比法。

1描述運動鏈的全息矩陣

1.1 全息矩陣的定義

在使用計算機對全鉸鏈機構進行運動學仿真時，只需要知道機構中關鍵點（兩構件的連接點，該點可能對應多個運動副鉸接）坐標，以及該關鍵點處構件的連接運動副元素，即可知曉機構的全部結構信息，并繪制出機構。基于這種思想，本文提出了一種新的運動鏈全息矩陣表達方法，運動鏈的結構信息用全息矩陣（matrixwithwholeinformation， MWI）M 描述如下：

該矩陣為一個 n_p×n_p 矩陣， n_p 為運動鏈的關鍵點數。關鍵點即構件之間的連接點。若無復鉸，則關鍵點數對應運動副數；若有復鉸，則多個構件間的連接點為同一個關鍵點，此時關鍵點數少于運動副數。

矩陣對角線元素 a_i，i 為運動鏈中兩相鄰構件的連接關鍵點對應的運動副元素，如運動副元素有移動副P、轉動副R、球面副S等。本文只研究全轉副的運動鏈，所以 a_i，i=R 。

下三角矩陣元素 a_i，j（igt;j） 為兩關鍵點 i 和j 所在的構件對應的編號 k ，構件編號從1開始賦值，因此機構中的構件數就是下三角矩陣中最大的構件編號值。由于運動鏈中可能有多元構件，對應有多個關鍵點，因此在下三角矩陣元素中可能出現多個元素具有相同值。若兩關鍵點 i 和 j 之間無實際構件，則 a_i，j=0 。

上三角矩陣 l_i，j（ii，j 表示構件中編號為 i，j 的兩關鍵點之間的實際長度值。若兩關鍵點 i 和 j 之間無實際構件，即兩關鍵點不在同一構件上，則 l_i，j=0 。

圖1a所示的全鉸鏈運動鏈結構含1個四元構件、2個三元構件、1個四元復鉸、2個三元復鉸，總計由12個桿件、16個鉸鏈和5個環組成，且其自由度為1，構件編號和關鍵點（構件之間的鉸接點）編號標注如圖所示。根據運動鏈的雙色拓撲圖定義[22]，黑色實心圓代表構件，引出的線條代表運動副，此處為關鍵點，空心圓代表復鉸，空心圓引出的線條都是同一個關鍵點，圖1b為其雙色拓撲圖。

該運動鏈對應的鄰接矩陣（adjacencymatrix，AM）A為

對比鄰接矩陣 A 和全息矩陣 M ，同樣是 12× 12矩陣，如果一個構件同時與多個構件連接，則判斷該構件是否為多元構件的總時間復雜度為O（n²） ，近似來說，時間復雜度與構件節點個數的平方成正比。

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

1.2 全息矩陣相關特征參數的判定定理

本文只研究全鉸鏈運動鏈，對表達運動鏈的全息矩陣只研究下三角矩陣。

定理1（多元連桿判定）運動鏈對應的全息下三角矩陣中的元素為構件編號 i 和0，某個 n 元構件有 n 個關鍵點，對應其相同的構件編號 i 出現在下三角矩陣的數量應為 C_n² ，且該全息矩陣中C_n² 個元素對應的矩陣行和列的不同數字（也是關鍵點數）為 n 個。進一步，當某個關鍵點對應的下三角矩陣的所有行與列元素中出現了 k 個相同的數值 j ，則多元構件 j 為 （k+1） 元構件。

例如：在全息矩陣中，某個三元構件編號為2，數值2在全息矩陣中出現3次，分別對應全息矩陣的元素 ，有3個關鍵點7、8、9。

對應的全息矩陣 M 為

推論1當知道 n 元構件上某個關鍵點對應的行和列元素位置之后，其中包含的構件 i 其余關鍵點和編號 i 出現的位置都可以確定。

如四元構件編號為1，在關鍵點4處對應的行和列元素轉變為一維數組 {1，1，1，4，0，0，0，0，0 0，0}，其中編號為1的元素為 a_?4，1…a_?4，2…a_?4，3 ，則可判定構件1為四元構件，其余關鍵點為1、2、3，且構件編號1對應的其他位置也可以確定為 。如編號為4的元素為 a_5，4 ，則可判定構件4為二元構件，其他位置不再出現構件4。

如提取關鍵點9上對應的行與列元素為一維數組 {0，0，0，0，0，0，2，2，3，3，0} ，則可判斷構件2和3都是三元構件。構件編號2對應的其他位置可確定為 a_8，7 ，構件編號3對應的其他位置也可確定為a11，10 。

從推論1和案例分析可知，當將下三角矩陣的某個關鍵點單獨提取出對應的行和列元素時，同一個構件上的不同關鍵點之間還是存在耦合關系的。例如關鍵點7、8、9均為構件2上的三個關鍵點，提取其下三角元素分別為 {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（多元復鉸判定）運動鏈對應的全息下三角矩陣中，若關鍵點 i 對應的行元素 a_i，j 和列元素 a_k，i（0p） 中有 n 個非0且不相等的值，表明該處復鉸連接了 n 個不同構件，則關鍵點 i 處的鉸鏈為 n 元復鉸。

如圖1所示，提取下三角矩陣中關鍵點6對應的行和列元素為一維數組 {0，0，7，0，6，0，8，0 .9，0，0} ，其中有4個不相同且不為0的數字6、7、8、9，則可判定該處為四元復鉸，分別對應相互鉸接的4個構件。

定理3（桿件編號變換規律）改變運動鏈中的桿件編號相當于給構件取了一個不同的序列號而已，不影響運動鏈的連接關系和結構，只是重新對運動鏈的構件進行了編號。對應全息下三角矩陣中元素值為0的位置不變，非0的對應的桿件編號數值相應改變。

定理4（關鍵點編號變換規律）改變運動鏈中的關鍵點編號不影響運動鏈的連接關系和結構，對應全息下三角矩陣中構件的性質（是否多元連桿、兩構件間連接關系等）不變，其結果是各關鍵點（如 i 和 j ）對應的行和列的位置互換。

例如：將式（3）的關鍵點3和4、構件編號7和8互換后得到新的全息矩陣為

2基于全息下三角矩陣的同構判定

基于上述分析，全息下三角矩陣可以確定結構信息唯一的運動鏈，本文提出了一種基于全息下三角矩陣變換對比的同構判定新方法。以圖2所示兩個12構件運動鏈[23]的拓撲圖同構判定為例，說明基于全息下三角矩陣對比變換的同構判定方法的具體步驟和分析思路。

1）首先檢索并獲得兩個運動鏈的結構參數，如構件類型和構件數、多元復鉸類型和數量，獨立環路數等，再進行比較。以運動鏈總構件數 n 、低副數 p 、自由度數 F 、獨立環路數 L 、關鍵點數 n_p 、多元構件數和多元復鉸數 的組合 {n，p，F，L，n_p，n₂，n₃，J₃，…，n_L+1，J_L+1} 作為運動鏈結構參數。上述運動鏈的基本結構參數如不相同，則可以直接判定不同構。圖2中，運動鏈1和2的結構參數都是{12，16，1，5，16，5，6，0，1，0，0，0，0，0} 。

2）對運動鏈1和2的構件和關鍵點進行隨機編號，如圖2所示，用全息下三角矩陣表示，獲得初始的下三角矩陣 M₁ 和 M₂ ，將下三角矩陣 M₁ 作為基準矩陣，下三角矩陣 M₂ 作為變換矩陣。

3）獲得初始矩陣 M₁ 和 M₂ 各個關鍵點對應的下三角矩陣元素的信息，對于 n_p 個關鍵點，每個關鍵點 i 對應的下三角行和列均有 個元素 （a_i，j（jk，i（kgt;i）） 。對于每一個關鍵點 i ，獲得其非0元素的總個數，以及相同非0元素出現次數，按數字從大到小排列，相同的數字不區分排序先后。獲得所有關鍵點對應的元素信息從大到小排列的一維數組，并將這些數組按照相同值進行分類。基準矩陣 M₁ 為

變換矩陣 M₂ 為

如初始的基準矩陣 M₁ 中，關鍵點1對應元素的一維數組為 {1，1，1，0，0，3，3，0，0，0，0，0，0，0，0，0} ，非0元素的總個數為5，不同的非0元素有2個，其中元素“1”出現3次，即構件1為四元構件，元素“3”出現2次，即構件3為三元構件，則關鍵點1對應的數組可表示為 {5，3，2} ，從該數組信息中可以得到前述多元構件特性，構件1為四元構件，構件3為三元構件。表1所示為2個運動鏈的初始矩陣所對應的關鍵點數字特征值，表2給出了數值相同的分組，16個關鍵點共分為了4組。關鍵點數組信息是運動鏈同構的必要條件之一，當基準矩

表1兩個12桿運動鏈關鍵點數字特征值

陣 M₁ 中的某個關鍵點的數組與變換矩陣 M₂ 對應組別中的關鍵點數組均無法匹配時則可判斷兩個運動鏈不同構。

4）獲得兩個矩陣的關鍵點對應數字特征值后，按照其中不同組關鍵點的數值大小進行排序，相同值的同組關鍵點排列次序隨機。根據數字特征值是否唯一或多組相同，將關鍵點區分為確定的關鍵點和待確定的關鍵點。表2中沒有一組關鍵點的數字特征值是唯一的，根據數字特征值相同劃分為4組待確定關鍵點。矩陣 M₁ 中，同組中存在多個特征數字相同的情況，4組關鍵點內的排序先隨機排列，對應運動鏈1所有關鍵點的初始排序如下：

經過上述變化后，基準矩陣中只有上述8個關鍵點的位置待確定。存在對應 P₂²×P₂²×P₂²× P₂²=16 種變換矩陣 M₂ 。限于篇幅，這里不一一列舉。

上述16個變換矩陣 M₂ 對應的運動鏈2與基準矩陣 M_i 對應的運動鏈1若同構，則其關鍵點的位置與基準矩陣 M₁ 中關鍵點具有一一映射關系。

6）根據構件編號變換原則，將所有衍生出來的變換矩陣 M₂ 逐一與基準矩陣 M₁ 進行匹配對比和同構判定。

同構判定原則：根據關鍵點互換定理和構件編號互換定理，在假定運動鏈2和運動鏈1的關鍵點具有逐一映射關系的前提下，對應的下三角矩陣 M₁ 和 M₂ 中，0元素的位置相同，非0元素的位置對應的構件編號可以不同（對應著構件編號的逐一映射關系），但是多元構件類型必須相同，同一多元構件對應的同一構件編號在兩個矩陣中多個位置是相同的。

對角線標記了隨機排序后的初始關鍵點編號。同理，如果對變換矩陣 M₂ 按照上述規則進行關鍵點排序時，理論上一共有 P₂²×P₂²×P₄⁴×P₈⁸= 3870720種匹配的可能。

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

檢索判定的操作為： ① 基準矩陣 M₁ 中某個位置出現0，對應變換矩陣 M₂ 中相同位置必須是0； ② 某個位置出現非0元素 i ，檢索 i 出現在基準矩陣 M₁ 的位置，對應變換矩陣 M₂ 中相同的位置必須是同一個非0元素 j 。

將得到的變換矩陣 M₂ 依據同構判定原則和上述操作進行對比分析，若其中某個變換矩陣符合，則運動鏈1和2同構，剩余的變換矩陣 M₂ 不用繼續判別；若所有的變換矩陣 M₂ 都不符合，則運動鏈1和2不同構。上述16個變換矩陣中的一個如下：

將式（9）與式（8）基準矩陣 M₁ 進行對比分析，式（8）中 M_6，1 是非0元素3，式（9）中為0元素，因此該情況不同構。本方法是在下三角矩陣可唯一確定運動鏈結構的理論分析基礎上，基于2個重要的定理（構件編號變換定理和關鍵點編號變換定理），將運動鏈用全息下三角矩陣表達，選擇其中矩陣 M₁ 作為基準矩陣，經過分組排列和同組非0元素前移后，分兩步將關鍵點進行細分，得到確定的關鍵點和待確定的關鍵點。在假定變換矩陣 M₂ 中所有關鍵點與基準矩陣 M₁ 中所有關鍵點位置逐一對應的情況下，將有限個變換矩陣 M₂ 與基準矩陣 M₁ 進行數字對比，可快速獲得同構判定結果。

上述基于全息下三角矩陣進行運動鏈同構判定方法的思路具體如圖3所示。

3 同構判定舉例

應用本方法完成文獻［24]中的28桿運動鏈的判定，構件與關鍵點編號如圖4所示，主要判定步驟如下。

1）獲取兩個運動鏈的結構參數 {n，?，F，L n ₂，n₃，J₃，…，n₁₄，J₁₄}={28，40，1，13，40，4，24 ，0，0，…，0，0} 。

2）對圖4中運動鏈1和2的構件和關鍵點隨機編號，獲得初始的下三角矩陣 M₁ 和 M₂ （具體矩陣表達式掃描本文首頁OSID碼獲取）。

3）記錄初始矩陣 M₁ 和 M₂ 的關鍵點特征信息，如表3所示。

4）對初始矩陣 M₁ 和 M₂ 的關鍵點信息按確定和待確定區域劃分，重新排列位置。如表3所示，關鍵點的數組信息分為2組，關鍵點數字特征值分別為{3，2，1}和 {4，2，2} ，其中{3，2，1}的關鍵點有8個， {4，2，2} 所對應的關鍵點有32個，初定{3，2，1}作為第一組，該組上的8個關鍵點隨機排序。

限于篇幅，后續優化基準矩陣，對變換矩陣進行關鍵點的對比、變換等操作省略，最終的判定結果與之符合，兩運動鏈同構。通過比較分析，28桿運動鏈具有強對稱性，能夠找到兩個運動鏈的構件編號與關鍵點編號之間的多種映射關系，表4給出了其中兩種映射情況。

由上述具有強對稱性的28桿運動鏈可知，對于高對稱性的圖或運動鏈，在對關鍵點進行分布確定時，關鍵點對應信息大量趨同，導致對應有大量的變換矩陣 M₂ 。對于結構對稱性弱的運動鏈，利用下三角矩陣自身包含信息素較多、耦合性強的優勢，可以快速地確定基準矩陣中的大量關鍵點對應的位置，后續產生的變換矩陣 M₂ 數量較少，可以快速對比獲得運動鏈之間同構判定結果。

對于不同構的運動鏈，基于全息下三角矩陣變換對比的同構判定方法往往只需要判定步驟中的前幾步即可發現運動鏈結構的差異性，判定效率較高。如對文獻[25]中的同構判定案例，如圖5所示，主要判定步驟如下。

1）獲取兩個運動鏈的結構參數均為 {n，p ，F，L，n₂，n₃，J₃，…，n₁₄，J₁₄}={15，27，-12，13 ，27，6，0，0，6，0，0，3，0，0，…，0，0} 。

2）對圖5中運動鏈1和2的構件和關鍵點隨機編號，獲得初始的下三角矩陣 M₃ 和 M₄ （矩陣表述掃描OSID碼獲取）。

3）記錄初始矩陣 M₃ 和 M₄ 的關鍵點特征信息，如表5所示。

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

表4兩個28桿運動鏈的構件與關鍵點映射關系

表515桿運動鏈重新排序的關鍵點數字特征值

限于篇幅，后續優化基準矩陣，對變換矩陣進行關鍵點的對比、變換等操作省略，最終得到的基準矩陣 M₃^′ 和變換矩陣 M₄^′ （矩陣表達掃描OSID碼獲取）。

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

繼續對上述案例中衍生出來的其他變換矩陣M₄^′ 進行對比判定，都得到不同構的結果，因此可判定上述2個運動鏈不同構。

4基于全息下三角矩陣變換對比的同構判定方法總結

綜上理論與案例分析，采用全息下三角矩陣的變換對比法進行同構判定具有以下特點。

1）同構判定方法的科學性。該同構判定方法建立在全息下三角矩陣可唯一確定運動鏈結構的基礎上，即一個結構描述正確的全息下三角矩陣與對應的運動鏈結構可以相互推導得到，判定原理為是否同構的充要條件，其科學性和準確性簡單易懂、一目了然。

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

3）同構判定方法的可編程性。由于同構判定原理的簡易性，故同構判定規則也相對簡單，則建立在全息下三角矩陣基礎上的對比分析非常利于計算機程序化設計。

5結論

1）本文提出了一種新的表達運動鏈的全息矩陣，重點分析了全息下三角矩陣的數字分布規則，下三角矩陣包含構件類型、多元復鉸、構件間的連接關系等大量信息，可唯一確定運動鏈的結構，分析給出了構件編號變化和關鍵點編號變化規律。

2）在全息下三角矩陣對應確定的運動鏈結構這一分析基礎上，提出了一種新的全息下三角矩陣變換對比的運動鏈同構判定新方法。

3）該方法和已有的同構判定方法比較，最大的優點在于同構判定原理簡單易于理解，同構判定規則簡單，只有信息檢索和分類、矩陣之間數值元素分析對比等，無需對環路或特征值、特征向量等進行計算，與現有同構判定方法比較，分析計算量較小。

參考文獻：

[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] 丁華鋒，黃真，曹毅.運動鏈拓撲圖的自動生成及圖 譜庫的建立[J].機械工程學報，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. （下轉第1221頁）