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

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

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

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

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

1 運(yùn)動(dòng)鏈拓?fù)鋱D的矩陣描述

1.1 運(yùn)動(dòng)鏈拓?fù)鋱D的連桿鄰接矩陣

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

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

圖1 瓦特鏈及其拓?fù)鋱D

1.2 運(yùn)動(dòng)鏈拓?fù)鋱D的漢明矩陣

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

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

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

2.1 識(shí)別碼獲得流程

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

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

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

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

步驟3：求解主對角線元素為0的平方陣H2的特征值λ1，…，λn，并將特征值按從小到大的順序排列得特征值序列。對特征值排序的目的是消除因特征值順序不同而產(chǎn)生的不同識(shí)別碼值和進(jì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：將上述的特征值λ乘以拓?fù)湟蜃觡，并將所得的乘積求和以獲得最終的同構(gòu)識(shí)別碼RC（recognition code）。此處的拓?fù)湟蜃觡定義為從1到n的整數(shù)，此步驟如式（4）所示。拓?fù)湟蜃觡的作用是解決兩圖因特征值不同而總和相同導(dǎo)致的誤判。如：1、2、3與1、1、4的和都為6，如果以此為判定依據(jù)，那么它們是同構(gòu)。但事實(shí)上它們的組成情況卻是不同的，即異構(gòu)。若將其乘以拓?fù)湟蜃忧罢邽?4，后者為15，則可以判定它們?yōu)楫悩?gòu)。如圖1的識(shí)別碼RC＝922.487 380 811 142 7。

2.2 運(yùn)動(dòng)鏈同構(gòu)的識(shí)別

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

3 判定實(shí)例

3.1 10桿運(yùn)動(dòng)鏈

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

圖3 兩10桿異構(gòu)運(yùn)動(dòng)鏈?zhǔn)疽鈭D

兩鏈的漢明矩陣如下：

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

表1 圖3兩運(yùn)動(dòng)鏈的同構(gòu)識(shí)別碼RC

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

3.2 15桿等譜拓?fù)鋱D

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

圖4 兩15桿異構(gòu)運(yùn)動(dòng)鏈拓?fù)鋱D

通過圖2的流程可得兩運(yùn)動(dòng)鏈拓?fù)鋱D的同構(gòu)識(shí)別碼RC，并將其列于表2中。

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

表2 圖4兩拓?fù)鋱D的同構(gòu)識(shí)別碼RC

3.3 28桿運(yùn)動(dòng)鏈拓?fù)鋱D

圖5來自于參考文獻(xiàn)［21］。已知圖5（a）和（b）僅是頂點(diǎn)標(biāo)號不同，（c）為（a）移動(dòng)一條邊后所得的圖形，所以（a）和（b）為同構(gòu)，（a）和（c）為異構(gòu)。計(jì)算可得三拓?fù)鋱D的同構(gòu)識(shí)別碼RC如表3所示。

圖5 三28桿運(yùn)動(dòng)鏈拓?fù)鋱D

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

表3 圖5三拓?fù)鋱D的同構(gòu)識(shí)別碼RC

4 結(jié)論

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

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

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

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

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