一種基于漢明矩陣的運動鏈同構(gòu)識別方法

趙 柯，許 輝，吳昌軍，鄧 濤

（1.重慶交通大學(xué) 機電與車輛工程學(xué)院，重慶 400074；2.重慶交通大學(xué) 航空學(xué)院，重慶 400074）

在機械結(jié)構(gòu)設(shè)計過程中，同構(gòu)運動鏈的識別既是重點也是難點［1-2］。為了解決這一問題，許多有效的方法被相繼提出。

最早的同構(gòu)識別主要依靠設(shè)計者的視覺觀察，這種方法只適用于桿副數(shù)量較低的情況，且效率低，缺乏理論依據(jù)［3］。后來隨著圖論的發(fā)展和引入，運動鏈的同構(gòu)問題得以簡化，識別方法開始向系統(tǒng)化和理論化方向發(fā)展。按照識別原理的不同，這些方法大致可以分為以下幾大類。特征多項式法［4-8］主要通過對比矩陣的特征多項式來判別同構(gòu)，此類方法效率高，但部分方法已發(fā)現(xiàn)反例，盡管這些反例對于機械領(lǐng)域來說并沒有實際意義。代碼法［9-10］主要通過轉(zhuǎn)化拓撲圖為唯一的形式來獲得判定同構(gòu)的代碼，此類方法具有較高的有效性且具有解碼性，但當拓撲圖的桿副數(shù)量較大或圖形對稱性較強時，其效率較低。路徑［11］或距離法［12］主要利用其特定的概念來生成一些判定碼，這類方法的有效性較高，但涉及的概念和參數(shù)較多，不便于計算機實現(xiàn)。人工神經(jīng)網(wǎng)絡(luò)法［13］為解決同構(gòu)提供了新的方向，但方法的有效性尚須進一步驗證。連桿連接數(shù)和平均信息量法［14］引入了信息論領(lǐng)域的概念，2個新的不變量被提出來檢測同構(gòu)，但其并不適用于復(fù)鉸鏈。鄰接矩陣冪序列法［15-16］依賴于鄰接矩陣的冪來判定同構(gòu)，但后者［16］在判別機構(gòu)倒置的某些情況下已經(jīng)出現(xiàn)失效。漢明數(shù)串法［17］是一種將漢明矩陣簡化表示為數(shù)字串來識別同構(gòu)的方法。此方法效率高，計算簡單，但漢明數(shù)串非常長，特別是在大型運動鏈的情況下。此外，如果一階漢明數(shù)串失敗，則需要二階漢明數(shù)串，這使得過程變得更加復(fù)雜。分裂漢明數(shù)串（SHS）法［18］是將漢明數(shù)串劃分為3部分以判定含有移動副的運動鏈。

機械結(jié)構(gòu)創(chuàng)新設(shè)計迫切需要一種簡單、高效和可靠的同構(gòu)篩選方法。上述大多數(shù)方法都涉及抽象的概念和復(fù)雜的中間參數(shù)比較，且隨著桿副數(shù)量增大，一些方法的效率和有效性會大大降低。因此，本文基于漢明矩陣提出了一種新的同構(gòu)識別方法，即從漢明矩陣的平方陣中導(dǎo)出同構(gòu)識別碼識別同構(gòu)運動鏈。若兩拓撲圖的同構(gòu)識別碼相同，則它們是同構(gòu)的，否則是非同構(gòu)的。此方法簡單、高效且整個判定過程在計算機上極易實現(xiàn)。

1 運動鏈拓撲圖的矩陣描述

1.1 運動鏈拓撲圖的連桿鄰接矩陣

對于運動鏈來說，將其桿件表示為頂點，運動副表示為邊，便轉(zhuǎn)化成了其對應(yīng)的運動鏈拓撲圖［19］，瓦特鏈及其拓撲圖如圖1所示。運動鏈拓撲圖的連桿鄰接矩陣A是其最基礎(chǔ)的矩陣，大多數(shù)同構(gòu)識別方法都以它為已知量。其元素aij為：

其中，i和j為連桿標號或頂點標號，i和j為從1到n的整數(shù)，n為運動鏈的連桿數(shù)。圖1所示的瓦特鏈連桿鄰接矩陣如下：

圖1 瓦特鏈及其拓撲圖

1.2 運動鏈拓撲圖的漢明矩陣

連桿鄰接矩陣的每一行代表了該標號的連桿是否與其他標號的連桿直接連接。但運動鏈中的間接連接等其他信息并未直觀地表現(xiàn)在連桿鄰接矩陣中。兩連桿之間的連接信息需要更深入地挖掘以提高識別方法的辨別能力。因此數(shù)字通信領(lǐng)域的漢明技術(shù)被引入以生成連桿漢明矩陣H，它的元素hij表示了連桿i和連桿j各自連接關(guān)系的不同程度［17］。以連桿鄰接矩陣為已知，hij定義為連桿鄰接矩陣的第i行和第j行所有列中不同元素的總和，數(shù)學(xué)表達如式（2）和式（3）所示。

例如，對于上述瓦特鏈連桿鄰接矩陣中的第1行和第2行來說，其第1、2、3、4、6列的元素都不同，故h12＝1+1+1+1+1＝5。同理可得圖1的漢明矩陣，如下所示：

2 識別碼的獲得流程與同構(gòu)識別

2.1 識別碼獲得流程

以連桿鄰接矩陣為已知量的同構(gòu)識別碼獲得流程如圖2所示。

圖2 同構(gòu)識別碼流程框圖

步驟1：導(dǎo)出漢明矩陣。根據(jù)式（2）和式（3）從連桿鄰接矩陣中獲得漢明矩陣。

步驟2：求漢明矩陣的平方得平方陣H2，并將平方陣H2的主對角線元素置為0。一方面，由于以漢明矩陣為判定依據(jù)的一階漢明數(shù)串在10桿鏈中已經(jīng)失效，這證明漢明矩陣中包含的信息量仍舊不足。于是本文求得漢明矩陣平方以獲得更多的細節(jié)特征，并以此為基礎(chǔ)，利用后續(xù)步驟進一步挖掘深層次的拓撲特性。另一方面，之所以將主對角線元素置為0，主要是為了排除對角線元素對特征值的影響，因為存在于運動鏈中的連桿不能與自身相連接。

步驟3：求解主對角線元素為0的平方陣H2的特征值λ1，…，λn，并將特征值按從小到大的順序排列得特征值序列。對特征值排序的目的是消除因特征值順序不同而產(chǎn)生的不同識別碼值和進一步導(dǎo)致的誤判。如圖1的特征值序列為：-78.027 969 292 722 6，-76.115 844 782 509 9，-58.000 000 000 000 0，-58.000 000 000 000 0，62.115 844 782 509 9，208.027 969 292 723。

步驟4：將上述的特征值λ乘以拓撲因子k，并將所得的乘積求和以獲得最終的同構(gòu)識別碼RC（recognition code）。此處的拓撲因子k定義為從1到n的整數(shù)，此步驟如式（4）所示。拓撲因子k的作用是解決兩圖因特征值不同而總和相同導(dǎo)致的誤判。如：1、2、3與1、1、4的和都為6，如果以此為判定依據(jù)，那么它們是同構(gòu)。但事實上它們的組成情況卻是不同的，即異構(gòu)。若將其乘以拓撲因子前者為14，后者為15，則可以判定它們?yōu)楫悩?gòu)。如圖1的識別碼RC＝922.487 380 811 142 7。

2.2 運動鏈同構(gòu)的識別

由于運動鏈連桿的標號是任意的，不同的標號會得到不同的運動鏈，但這些運動鏈擁有相同的桿副連接特征，所以它們被稱為同構(gòu)運動鏈，其對應(yīng)的拓撲圖被稱為同構(gòu)拓撲圖。本文提出的RC是一個運動鏈拓撲圖的不變量，它不隨著連桿標號的改變而改變。因此RC可以作為同構(gòu)判定的依據(jù)。若已知兩條鏈是同構(gòu)，那么它們的識別碼RC應(yīng)相等，反之亦然。

3 判定實例

3.1 10桿運動鏈

圖3為一階漢明數(shù)串誤判為同構(gòu)的兩10桿1自由度異構(gòu)運動鏈［17］。

圖3 兩10桿異構(gòu)運動鏈示意圖

兩鏈的漢明矩陣如下：

由上可知，兩矩陣的行和元素組成情況存在著一一對應(yīng)關(guān)系，這直接導(dǎo)致了一階漢明數(shù)被判定為同構(gòu)。由前文可得兩鏈的同構(gòu)識別碼，如表1所示。

表1 圖3兩運動鏈的同構(gòu)識別碼RC

顯然表1的兩RC不相等，因此圖3中的兩運動鏈為異構(gòu)鏈。

3.2 15桿等譜拓撲圖

圖4中的兩運動鏈為眾多特征向量法的判別反例。由于其結(jié)構(gòu)的冗余，盡管它們在機械領(lǐng)域中并沒實用價值，但眾多學(xué)者仍舊熱衷于判定此圖，并將其作為檢驗各種判定方法的常用實例，本文也不例外。圖4的特殊性在于其連桿鄰接矩陣的特征值相同即等譜，這是導(dǎo)致誤判為同構(gòu)的重要原因。另外，一些方法即使能夠正確判定這一實例，但卻需要很大的計算量［20］。

圖4 兩15桿異構(gòu)運動鏈拓撲圖

通過圖2的流程可得兩運動鏈拓撲圖的同構(gòu)識別碼RC，并將其列于表2中。

顯然表2的兩RC不相等，因此圖4中的兩拓撲圖為異構(gòu)圖。另外，值得一提的是此兩RC的計算量并不大。

表2 圖4兩拓撲圖的同構(gòu)識別碼RC

3.3 28桿運動鏈拓撲圖

圖5來自于參考文獻［21］。已知圖5（a）和（b）僅是頂點標號不同，（c）為（a）移動一條邊后所得的圖形，所以（a）和（b）為同構(gòu)，（a）和（c）為異構(gòu)。計算可得三拓撲圖的同構(gòu)識別碼RC如表3所示。

圖5 三28桿運動鏈拓撲圖

由表3可知，圖5（a）與（b）的RC相等，即它們?yōu)橥瑯?gòu)拓撲圖；圖5（a）與（c）的RC不相等，即它們?yōu)楫悩?gòu)拓撲圖。此結(jié)果與參考文獻一致。

表3 圖5三拓撲圖的同構(gòu)識別碼RC

4 結(jié)論

1）本判別方法創(chuàng)造性地對漢明矩陣進行平方運算以獲得運動鏈的更多連接細節(jié)，并將平方陣主對角線元素置為0，排除其對后續(xù)特征值的影響。此外，本文定義了拓撲因子，并將拓撲因子與特征值的乘積求和得到運動鏈的不變量，即運動鏈同構(gòu)識別碼RC。

2）本方法邏輯簡單易理解，開發(fā)本方法的計算機程序非常容易，即使對于僅有編程基礎(chǔ)的人員也容易掌握。另外在計算機程序的幫助下，只需輸入連桿鄰接矩陣即可實現(xiàn)自動識別，判別過程簡單、高效、準確。

3）對于其他方法失效的實例，本方法也能夠成功識別。此外，在研究階段，本方法的有效性經(jīng)過了大量的實例驗證，由于篇幅限制，并未將其列入此文中。

4）本方法易推廣到其他類型運動鏈的同構(gòu)識別中，如復(fù)鉸鏈、齒輪鏈，只需簡單地修改連桿鄰接矩陣的元素，識別方法無需修改。

5）本方法對于連桿數(shù)高于28的運動鏈的有效性尚須進一步驗證，另外本方法也不具有解碼性。