商慧亮， 劉 洋， 柳志棟， 董文杰， 李 鋒

1.復旦大學電子工程系，上海200433

2.東方電子有限公司，山東煙臺264000

長期以來，新型電力電子電路拓撲的建立主要依賴于靈感和經驗，并沒有一個嚴密的邏輯可以遵循.隨著電路拓撲的日益復雜，有必要建立一種嚴密而有邏輯可循的電路拓撲建立方法.文獻[1]對于在電路拓撲建立過程中如何確定有效的研究范圍作了詳細的介紹，其中一個重要的判定條件為結構條件，即根據(jù)圖論等數(shù)學知識來剔除同構的電路拓撲，以生成一個最大不同構的電路拓撲基底.由此看來，在混合開關拓撲的建立過程中，需要解決一個很重要的問題——同構混合開關拓撲的辨識問題.

對混合開關拓撲進行數(shù)學建模，可以將同構混合開關拓撲的辨識問題轉換為與其對應的含權無向圖的同構判定問題.圖的同構判定問題是圖論研究中的一個基本問題，在電路拓撲[1]、機構學[2-3]、化學結構[4]、數(shù)據(jù)處理[5]等研究領域均有較為廣泛的應用.對于圖的同構判定問題，目前從理論上還無法證明它究竟屬于NP完全問題還是P問題，于是眾多學者予以關注和研究，并提出了各種圖同構判定算法[6-15]，主要包括改進的頂點順序交換法、頂點度數(shù)序列法、基于神經網絡的算法、基于搜索的算法等幾類.其中基于搜索的算法在實際過程中表現(xiàn)最好，如SD算法、Ullmann算法、VF算法、Nauty算法等[12].文獻[6-7]提出了一種新的圖同構判定方法——電路模擬法，通過建模將圖同構判定問題轉換為判定其對應的伴隨電路是否相同的問題，繼而通過電路仿真來加以判定.理論分析和實際測試均表明，電路模擬法能夠實現(xiàn)多項式時間復雜度內的隨機圖同構判定[7].

本文在原始電路模擬法的基礎上進行改進，通過引入參考節(jié)點，進一步提高了電路模擬法的判定效率.在此基礎上，結合對混合開關拓撲的數(shù)學建模，將改進的電路模擬法應用到同構混合開關拓撲的辨識中.經實例測試表明改進的電路模擬法在解決混合開關拓撲同構辨識問題上是有效的，且在判定速度以及節(jié)點匹配能力上有較大優(yōu)勢.

1 混合開關拓撲的定義和數(shù)學描述

1.1 混合開關拓撲的基本概念

開關拓撲是對含有電感、電容和開關元件的電力電子電路的抽象.考慮到效率因素，電阻元件在電力電子電路中通常作為負載出現(xiàn)在保護、采樣電路中，因此在開關拓撲中一般不包含電阻元件.由電感、電容、開關元件、電壓源、電流源組成的開關拓撲被稱為混合開關拓撲[1].

1.2 混合開關拓撲的數(shù)學描述

文獻[1]針對混合開關拓撲提出了一種較為直觀的數(shù)學描述方法，該方法篩選出混合開關拓撲中所有有效的混合支路，并對其進行編號.參照這種方法，可以將混合開關拓撲中所有17種符合電路原理的有效的混合支路用圖1所示的編號來表示.

1.2.1 混合開關拓撲的鄰接矩陣表示

對于一個節(jié)點數(shù)為n的混合開關拓撲，設其任意兩節(jié)點間最多存在1條圖1所示的有效混合支路，那么其鄰接矩陣D可定義為一個n×n的矩陣，其中第i行第j列元素

式中，e為混合開關拓撲中節(jié)點i和j之間所連接的混合支路在圖1中所對應的編號.

圖1 有效的混合支路及其編號Figure 1 Valid hybrid branches and corresponding indices

例1給出了一個混合開關拓撲及其相應的鄰接矩陣表示示例.

例1圖2是一個典型的零電壓轉換PWM軟開關升壓斬波電路拓撲圖，圖中已對相關節(jié)點進行編號[1].

圖2 混合開關拓撲示意圖Figure 2 Example of hybrid switching topology

例如在圖2中，節(jié)點2和5之間并聯(lián)開關和電容，該混合支路在圖1中對應的編號為3，所以在對應鄰接矩陣中的第2行、第5列和第5行、第2列的元素值都是3.以此類推，可以列寫出完整的鄰接矩陣.

圖2所示的混合開關拓撲所對應的鄰接矩陣為

1.2.2 混合開關拓撲對應的含權無向圖表示

對于一個給定的混合開關拓撲，以原先拓撲圖中的節(jié)點為對應的含權無向圖中的相應節(jié)點，以原先拓撲圖中節(jié)點間連接的混合支路在圖1中所對應的編號為含權無向圖中相應節(jié)點間相連的邊的權值，由此可以構建出混合開關拓撲所對應的含權無向圖.若原先拓撲圖中兩節(jié)點間沒有電路連接，則其對應的含權無向圖中的相應節(jié)點間也沒有邊相連.

圖3為圖2所示的混合開關拓撲所對應的含權無向圖.

圖3 混合開關拓撲對應的含權無向圖的示意圖Figure 3 Example of the corresponding undirectedweighted graph of hybrid switching topology

根據(jù)這種方法得到的含權無向圖中的節(jié)點以及節(jié)點間的連接關系與原先混合開關拓撲中的節(jié)點以及節(jié)點間的電路連接是一一對應的.顯然，若待判定的兩個混合開關拓撲是同構的，則其分別對應的含權無向圖也是同構的；反之亦然.于是，可以將同構混合開關拓撲的辨識問題轉換為與其對應的含權無向圖的同構判定問題.對此，本文在電路模擬法[6-7]的基礎上進行改進，并提出了一種更高效的圖同構判定算法——改進的電路模擬法.

2 改進的電路模擬法

2.1 電路模擬法的基本原理

基于文獻[6-7]，本節(jié)將針對含權無向圖的同構判定簡要地介紹電路模擬法的基本原理.

對于待判定圖G和G′，若要滿足同構，則圖G和G′必須滿足兩個必要條件：1）頂點數(shù)相等；2）邊數(shù)相等.如果不滿足這兩個條件，則可判定圖G和G′不同構.

下面的敘述均假設圖G和G′已經滿足上述兩個必要條件.本節(jié)將針對含權無向圖引入度、相同電路、圖的伴隨電路、全激勵、節(jié)點電壓序列以及節(jié)點電壓序列集等概念，并以此為基礎推演出相關定理，從而奠定電路模擬法的理論基礎.

定義1度圖G中與一個點vi關聯(lián)的邊的數(shù)目被稱為點vi的度[16].

定義2度數(shù)序列和度數(shù)分布序列對應統(tǒng)計G各頂點的度數(shù)，記下各頂點度數(shù)的數(shù)量統(tǒng)計，按照相同度數(shù)頂點的多少對度數(shù)進行排序.將相同度數(shù)少的頂點的度數(shù)排在前面，相同度數(shù)多的頂點的度數(shù)排在后面，度數(shù)相同的頂點的度數(shù)排在一起，從而得到度數(shù)序列.具有相同度數(shù)的各頂點的數(shù)量統(tǒng)計序列被稱為度數(shù)分布序列.

例2圖4為一對同構圖G和G′.

圖4同構圖示例Figur e 4 Example of isomorphic graphs

圖4 中(a)和(b)的各頂點度數(shù)分布統(tǒng)計如表1所示：

表1 圖度數(shù)分布統(tǒng)計表Table 1 Degree distribution of vertices

那么圖G和G′的度數(shù)序列和度數(shù)分布序列如下：

對于圖G，度數(shù)序列為[2,3,7,4,4,4]，度數(shù)分布序列為[1,1,1,3]；

對于圖G′，度數(shù)序列為[2,3,7,4,4,4]，度數(shù)分布序列為[1,1,1,3].

定理1如果圖G和G′是同構的，那么圖G和G′對應的度數(shù)序列和度數(shù)分布序列是相同的.

定義3相同電路如果電路N和N′對應的拓撲圖G和G′是同構的，并且對應支路上具有相同的元件，那么電路N和N′稱為相同電路，記為N=N′.

定義4圖的伴隨電路對于含權無向圖G，將圖中每條邊均用電阻替代，讓電阻的導納值等于圖G中相應邊的權值，由此得到的電路N被稱為圖G的伴隨電路.

例3如圖5所示，將圖(a)所示的含權無向圖G中的每條邊均用電阻替代，使電阻的導納值等于圖G中相應邊的權值，由此可以得到圖(b)所示的伴隨電路N.

圖5 圖的伴隨電路示意圖Figure 5 Example of a graph and its corresponding associate circuit

定理2同構圖所對應的伴隨電路是相同電路；反之，互為相同電路的伴隨電路所對應的圖是同構的.

定義5全激勵在含有n個節(jié)點的伴隨電路N中，若以節(jié)點i為參考點，在節(jié)點i與其余(n-1)個節(jié)點間分別施加相同的電流源Is(為便于計算，相同的電流源Is選用1A)，電流方向都是從節(jié)點i指向其余節(jié)點，這樣一種激勵方式稱為節(jié)點i的全激勵.圖5(b)所示的伴隨電路N中以節(jié)點1為參考點施加全激勵的情況如圖6所示.

定義6節(jié)點電壓序列和節(jié)點電壓序列集在包含n個節(jié)點的伴隨電路N中，以節(jié)點i為參考點施加全激勵，將得到的節(jié)點電壓序列按照升序排列(相等的電壓排列在一起)，得到的電壓序列Si(i=1,2,3,···,n)稱為節(jié)點i的節(jié)點電壓序列.對伴隨電路N中所有節(jié)點依次施加全激勵，得到的所有節(jié)點電壓序列的集合稱為節(jié)點電壓序列集，記為SN={Si}，i=1,2,···,n.

圖6 節(jié)點1的全激勵示意圖Figur e 6 Complete excitation of node 1

定理3對圖G和G′所對應的伴隨電路N和N′中所有節(jié)點施加相同全激勵，若圖G和G′同構，那么所得到的節(jié)點電壓序列集是相同的，并且N和N′中對應節(jié)點的節(jié)點電壓序列相等.

定理4設圖G和G′對應的鄰接矩陣分別為D和D′，對應的伴隨電路分別為N和N′，對伴隨電路N和N′中所有節(jié)點施加相同全激勵.如果得到的節(jié)點電壓序列集SN=SN′，并且SN和SN′中的節(jié)點電壓序列各不相等，根據(jù)SN和SN′中節(jié)點電壓序列間的對應關系調整圖G′對應的鄰接矩陣D′，調整規(guī)則如下：

對于有n個節(jié)點的圖G和G′，若圖G中節(jié)點i所對應的節(jié)點電壓序列Si與圖G′中節(jié)點j′所對應的節(jié)點電壓序列Sj′相等，那么圖G中的節(jié)點i與圖G′中的節(jié)點j′互為對應節(jié)點，記j′為π(i).而定理4中已假設節(jié)點電壓序列集SN=SN′，并且SN和SN′中的節(jié)點電壓序列各不相等，因而可以得出所有節(jié)點間的對應關系：i?π(i)(i=1,2,3,···,n)，其中i為圖G中的節(jié)點，π(i)為圖G′中與節(jié)點i成對應關系的節(jié)點的編號.

在此基礎上，根據(jù)節(jié)點間的對應關系調整圖G′對應的鄰接矩陣D′.首先依次將D′中的第π(i)行存放于一個中間矩陣Dn的第i行(i=1,2,3,···,n)，然后將Dn中的第π(i)列依次存放于最終調整后得到的矩陣的第i列(i=1,2,3,···,n).

在此基礎上可以得到如下結論：

定理5圖G和G′對應的伴隨電路分別為N和N′，對伴隨電路N和N′中所有節(jié)點施加相同全激勵，假設得到的節(jié)點電壓序列集SN=SN′，如果圖G和G′同構，那么僅節(jié)點電壓序列相等的節(jié)點所對應的圖的頂點間可能存在對應關系.

定理1～5的詳細證明見文獻[6-7]，這里不再贅述.

2.2 電路模擬法的改進

在同構判定過程中若采用原始的電路模擬法，則待判定圖所對應的伴隨電路中的所有節(jié)點應輪流作為施加全激勵的參考點，從而得到作為同構判定依據(jù)的節(jié)點電壓序列.因此，對于頂點數(shù)為n的兩個圖，一次完整的同構判定過程需要遍歷所有2n個頂點，并依次施加全激勵以求解節(jié)點電壓序列.理論分析和實驗結果均表明，原始的電路模擬法能夠實現(xiàn)多項式時間復雜度內的隨機圖同構判定[6].為進一步提高電路模擬法的判定效率，本文提出了一種增加參考頂點的改進措施，通過對待判定圖進行預處理，使得在判定頂點數(shù)為n的兩個圖時，只需計算對新增的參考頂點施加全激勵得到的節(jié)點電壓序列，于是大大降低了算法的計算復雜度.

2.2.1 待判定圖的預處理

本節(jié)將針對含權無向圖介紹改進的電路模擬法對待判定圖的預處理過程.

預處理規(guī)則如下：對于有n個頂點的待判定圖G，增加一個參考頂點，記為頂點m，將頂點m與其余n個頂點分別用含權無向邊ki(i=1,2,···,n)相連，其中ki表示頂點m與頂點i之間相連的含權無向邊，邊的權值等于頂點i的度數(shù).

例4 對于圖5(a)所示的含權無向圖G，根據(jù)待判定圖預處理規(guī)則進行預處理，得到的圖Gm如圖7所示.

圖7 待判定圖預處理示例Figure 7 Example of the pre-processing of the graph to be determined

定理6如果待判定圖G和G′是同構的，那么圖G和G′分別根據(jù)預處理規(guī)則處理后得到的圖Gm和也是同構的，且新增的參考頂點互為對應頂點.

由預處理規(guī)則可知：對于有n個頂點的圖G和G′，如果它們是同構的，那么經過預處理后得到的圖Gm和中增加的參考頂點m和m′與原圖中對應頂點間的連接均是相同的，不影響原圖中頂點間的對應關系，因此預處理后的圖Gm和也是同構的，且頂點m和頂點m′互為對應頂點.

在定理6的基礎上，根據(jù)定理3可以得出：對圖Gm和對應的伴隨電路Nm和中的節(jié)點m和m′分別施加相同全激勵，得到的節(jié)點電壓序列Sm和相等.

類似于定理4，可以推導出定理7.

定理7 設頂點數(shù)為n的圖G和G′對應的鄰接矩陣分別為D和D′，根據(jù)預處理規(guī)則分別對圖G和G′進行預處理得到圖Gm和，構建相應的伴隨電路Nm和，分別以新增的頂點m和m′作為參考節(jié)點施加相同全激勵，如果得到的節(jié)點電壓序列Sm=，且Sm和中各個節(jié)點電壓各不相等，那么根據(jù)Sm和中節(jié)點電壓間的對應關系調整圖G′對應的鄰接矩陣D′(具體的操作參照定理4中的調整規(guī)則)，調整后的矩陣為，在此基礎上可得到如下結論：

1)若D′n=D，則可判定圖G和G′同構.

2)若D′n/=D，則可判定圖G和G′不同構.

類似于定理5，可以推導出定理8.

定理8 根據(jù)待判定圖預處理規(guī)則對待判定圖G和G′進行預處理，分別增加參考頂點m和m′，得到圖Gm和，構造相應的伴隨電路Nm與，并以節(jié)點m和m′為參考點施加相同全激勵.假設得到的節(jié)點電壓序列Sm=，那么圖G和G′同構，僅節(jié)點電壓相等的節(jié)點所對應的圖的頂點間可能存在對應關系.

對于預處理后得到的圖Gm和所對應的伴隨電路Nm和來說，新增的參考頂點m和m′是唯一的度數(shù)最大的點，因此可以唯一確定，這樣只需對新增的參考節(jié)點施加全激勵，然后比較得到的節(jié)點電壓序列即可判定兩圖是否同構.由于原始的電路模擬法需遍歷待判定圖所對應的伴隨電路中所有的節(jié)點并施加全激勵，改進的電路模擬法的判定效率大大提高了.

2.2.2 改進的電路模擬法的判定流程

本節(jié)將給出改進的電路模擬法的判定過程.

假設待判定圖G和G′滿足圖同構的兩個必要條件：1）頂點數(shù)相同；2）邊數(shù)相等.如果不滿足上述任何一個條件，則可直接判定圖G和G′不同構；如果滿足，則繼續(xù)下面的步驟1～7：

步驟1寫出圖G和G′對應的鄰接矩陣D和D′.

步驟2對圖G和G′中頂點的度數(shù)分布進行統(tǒng)計，如果統(tǒng)計得出的度數(shù)序列和度數(shù)分布序列均相等，則繼續(xù)步驟3～7，否則可判定圖G和G′不同構，判定過程終止.

步驟3根據(jù)預處理規(guī)則對圖G和G′進行預處理，得到圖Gm和.

步驟4構建圖Gm和對應的伴隨電路Nm和，并以新增的節(jié)點m和m′作為參考節(jié)點施加相同全激勵，構建節(jié)點電壓方程，求出相應的節(jié)點電壓序列Sm和S′m.

步驟5比較節(jié)點電壓序列Sm和，若不相等則可判定圖G和G′不同構，判定過程終止；若Sm=則兩圖可能同構，檢測Sm和中有沒有相同的節(jié)點電壓，如果有，跳至步驟7，否則繼續(xù).

步驟6根據(jù)節(jié)點電壓序列Sm和中得出的頂點間的對應關系調整G′的鄰接矩陣D′，若調整后得到的矩陣=D，則可判定圖G和G′同構，否則兩圖不同構，判定過程終止.

步驟7Sm和中含有相同的節(jié)點電壓，表明待判定圖中存在對稱頂點.對具有相同節(jié)點電壓的頂點列出其所有可能的對應關系，根據(jù)每一種對應關系相應調整G′的鄰接矩陣D′.若調整后得到的矩陣=D，則可判定圖G和G′同構；若經過所有可能的調整后/=D，則可判定圖G和G′不同構.

3 同構混合開關拓撲辨識實例

本文第1節(jié)介紹了如何通過建模將同構混合開關拓撲的辨識問題轉換為其相應的含權無向圖的同構判定問題，在此基礎上，本節(jié)將改進的電路模擬法和特征值判定法應用到同構混合開關拓撲辨識上，并分別給出判定實例.

以圖2所示的電路拓撲為基礎，圖8給出了該電路的一對同構混合開關拓撲，且已對電路中的節(jié)點進行編號.

本節(jié)將分別應用文獻[1]提出的特征值判定法以及本文提出的改進的電路模擬法分別對圖8所示的一對混合開關拓撲進行同構判定.

3.1 特征值判定法

對于混合開關拓撲的同構判定，文獻[1]提出了一種有效的判定方法——特征值判定法，其基本流程如下：先根據(jù)混合開關拓撲的數(shù)學表示方法列出其鄰接矩陣，再判斷計算出的鄰接矩陣的特征值是否相等.若不相等，則不同構；若相等，則兩個開關拓撲所對應的鄰接矩陣相似.計算這兩個相似矩陣之間的相似變換矩陣，如果其相似變換矩陣為置換矩陣，則兩個開關拓撲是同構的，否則不同構.

根據(jù)本文第1節(jié)提出的混合開關拓撲的數(shù)學描述方法可以將圖8所示的兩個混合矩陣拓撲的鄰接矩陣D和D′分別表示為

圖8 同構混合開關拓撲示意圖Figure 8 Example of isomorphic hybrid switching topology

根據(jù)特征值判定法，使用Visual C++進行編程，編程環(huán)境為：Windows7,Pentium Dual-core CPU T4200 2.0GHz×2,2GB RAM.輸入待判定的混合開關拓撲的鄰接矩陣D和D′，其計算結果如下：

首先算出鄰接矩陣D的特征值

鄰接矩陣D′的特征值為

比較可得兩組特征值相等，表明輸入的兩個鄰接矩陣相似.接著計算鄰接矩陣間的相似變換矩陣，其相似變換矩陣T為

滿足D′=T-1D T

顯然相似變換矩陣T為置換矩陣，于是可以判定兩開關拓撲同構，但在這種情況下并不能直接得到同構的混合開關拓撲中節(jié)點的對應關系.

3.2 改進的電路模擬法

首先構建圖8所示的一對混合開關拓撲所對應的含權無向圖G和G′，如圖9所示：

圖9 混合開關拓撲對應的含權無向圖Figure 9 Hybrid switching topology and corresponding undirected-weighted graph

對圖9所示的含權無向圖G和G′中的頂點度數(shù)分布進行統(tǒng)計，得到的統(tǒng)計結果見表2.

那么圖G和G′的度數(shù)序列和度數(shù)分布序列分別如下：

對于圖G，度數(shù)序列為[2,3,3,4,4]，度數(shù)分布序列為[1,2,2]；對于圖G′，度數(shù)序列為[2,3,3,4,4]，度數(shù)分布序列為[1,2,2].

根據(jù)改進的電路模擬法中提出的待判定圖的預處理規(guī)則，可以得到圖9所示的含權無向圖G和G′經過預處理后得到的圖Gm和G′m，如圖10所示.

圖10 預處理后的含權無向圖Figure 10 Pre-processed undirected-weighted graph

相比于圖9所示的原始的含權無向圖G和G′，圖10所示的Gm和分別增加了頂點6和6′作為參考頂點，并將參考頂點和原圖所有的頂點都用含權無向邊連接起來(其權值為原圖對應頂點的度數(shù)).

表2 度數(shù)分布統(tǒng)計表Table 2 Degree distribution of vertices

構造圖Gm和對應的伴隨電路Nm與，如圖11所示.

圖11 預處理后的含權無向圖對應的伴隨電路Figure 11 Corresponding associated circuits of thepreprocessed undirected-weighted graphs

分別以節(jié)點6和6′作為參考點施加全激勵，將所有的電流Is設為1A，列寫節(jié)點電壓方程.

對于無向含權圖Gm對應的伴隨電路Nm，節(jié)點電壓方程為

解得的節(jié)點電壓分別為

節(jié)點6和6′對應的節(jié)點電壓序列S6和S6′分別為

S6=[0.3069,0.3069,0.3137,0.3165,0.3272],

可以發(fā)現(xiàn)節(jié)點電壓序列S6和中的節(jié)點電壓一一對應相等，且每個序列中的電壓值各不相等.由此可以判定原先的混合開關拓撲可能是同構的，根據(jù)節(jié)點電壓間的對應關系，可以得出其頂點間可能的對應關系為1-1′，2-3′，3-2′，4-5′，5-4′.

根據(jù)對應關系交換G′對應的鄰接矩陣D′，得到矩陣

在此基礎上，本文針對更大規(guī)模的混合開關拓撲分別采用改進的電路模擬法和特征值判定法進行同構判定測試，在Windows7,Pentium Dual-core CPU T4200 2.0GHz×2,2 GB RAM的配置環(huán)境下，比較兩種判定方法同構判定所消耗的時間，判定0～150個點的拓撲的平均耗時如圖12所示.

由圖12可以發(fā)現(xiàn)，改進的電路模擬法的判定耗時遠小于特征值法，在處理150個點以內的混合開關拓撲的同構判定時，改進的電路模擬法的耗時變化不大，最大耗時在0.016s.而特征值判定法的耗時則隨著電路節(jié)點數(shù)的增加而急劇增加，判定150個節(jié)點的電路拓撲的耗時為6.2240s，遠大于改進的電路模擬法.由此可見，改進的電路模擬法在判定速度上有較大的優(yōu)勢.

圖12 改進的電路模擬法和特征值判定法的耗時比較Figure 12 Comparison of time consumtions between optimized circuit simulation method and eigenvalue algorithm

3.3 改進的電路模擬法與特征值判定法的比較分析

3.3.1 節(jié)點匹配能力

特征值判定法先通過計算來比較兩個電路鄰接矩陣的特征值，并判定兩個拓撲所對應的鄰接矩陣是否相似，接著判定鄰接矩陣間的相似變換矩陣是否為置換矩陣，進而判定混合開關拓撲是否同構.假設判定得出兩個拓撲同構，則該方法只能得到兩個電路拓撲的鄰接矩陣之間的相似變換矩陣，而不能直接得到原先電路拓撲中節(jié)點間的對應關系.

改進的電路模擬法首先將混合開關拓撲的同構判定問題轉換為對應的含權無向圖的同構判定問題，接著構建含權無向圖的伴隨電路進行電路仿真，解得節(jié)點所對應的節(jié)點電壓，最后判斷解得的節(jié)點電壓值是否完全對應相等來判定混合開關拓撲是否同構.由于解得的節(jié)點電壓值和電路拓撲中的節(jié)點是一一對應的，節(jié)點電壓對應相等的兩個節(jié)點分別對應的電路拓撲中的節(jié)點也互為對應關系，于是可以直接得出同構的電路拓撲中節(jié)點間的對應關系.

3.3.2 算法復雜度分析

假設待判定的混合開關拓撲有n個節(jié)點，那么采用改進的電路模擬法進行同構判定時在最優(yōu)情況下的計算復雜度主要依賴于以下幾個步驟：

步驟1列寫節(jié)點電壓方程的通用導納矩陣，運算次數(shù)為2次，單次運算的時間復雜度為O((n+1)2).

步驟2求解節(jié)點電壓方程，方程維數(shù)為n，運算次數(shù)為2次，由于圖的伴隨電路節(jié)點電壓方程一般為稀疏矩陣線性方程組，因而本算法采用廣義最小殘差法[17]來解，單次運算的時間復雜度為O(n2).

步驟3根據(jù)計算得到的一對節(jié)點電壓序列獲得節(jié)點間的對應關系，其運算次數(shù)為1次，單次運算的時間復雜度為O(n2).

步驟4根據(jù)節(jié)點間的對應關系調整其中一個鄰接矩陣，其運算次數(shù)為1次，單次運算的時間復雜度為O(n2).

步驟5將調整后的鄰接矩陣與未調整的鄰接矩陣作比較運算，運算次數(shù)為1次，單次運算的時間復雜度為O(n2).

由此可見，對于改進的電路模擬法，在最優(yōu)情況下的算法時間復雜度在O(n2)量級上.對于一些對稱性較強的圖，節(jié)點電壓序列中可能出現(xiàn)節(jié)點電壓相同的情況，此時需要遍歷這些節(jié)點間所有可能的對應關系，相應地調整鄰接矩陣，得出最終的判定結果.在這種情況下，改進的電路模擬法的判定效率會有所降低，但不影響算法的正確性，且這種情況在實際電路拓撲中并不多見.

對于特征值判定法，應先求解鄰接矩陣的特征值，再計算相似變換矩陣，因此算法的計算大多集中在電路拓撲鄰接矩陣的特征值和特征向量上.隨著電路節(jié)點數(shù)目的增加，混合開關拓撲的鄰接矩陣一般為稀疏矩陣，因而特征值判定法在實現(xiàn)過程中采用Jacobi迭代法來求解鄰接矩陣的特征值和特征向量.對于一個n階的混合開關拓撲，該方法的時間復雜度為O(n3)，而其余計算步驟的復雜度均在O(n2)量級上，因而特征值判定法總體的算法時間復雜度在O(n3)量級上.隨著待判定開關拓撲節(jié)點數(shù)的增加，改進的電路模擬法與特征值判定法的算法耗時差距急劇加大，這也與圖12所示的測試結果相符合.

由此可見，改進的電路模擬法在節(jié)點匹配能力以及算法時間復雜度上較特征值判定法有較大的優(yōu)勢.

4 結語

本文基于圖同構判定算法——電路模擬法[6-7]，通過對待判定圖增加一個參考頂點的改進，大大提升了原先算法的判定效率.在此基礎上，參照文獻[1]中對混合開關拓撲的數(shù)學描述，將改進后的電路模擬法巧妙地運用到混合開關拓撲的同構判定中，并由理論分析和實例證明了該方法的有效性，同時將改進的電路模擬法與特征值判定法進行比較，證明了改進的電路模擬法在判定速度和節(jié)點匹配能力方面的優(yōu)勢.

[1]石勇，楊旭，何群，王兆安.同構混合開關拓撲的辨識[J].中國電機工程學報，2003,23(11):116-121.SHIYong,YANGXu,HEQun,WANGZhao'an.Identif ication of hybrid switching topology[J].Proceedings of the Chinese Society for Electrical Engineering,2003,23(11):116-121.(in Chinese)

[2]丁華鋒，黃真.平面機構統(tǒng)一拓撲描述模型的建立及同構判別[J].機械工程學報，2009,45(3):99-103.

DING Huafeng,HUANG Zhen.Uniform topological representation model of planar mechanisms and isomorphism identif ication[J].Journal of Mechanical Engineering,2009,45(3):99-103.(in Chinese)

[3]丁玲，路懿.運動鏈拓撲圖的特征數(shù)組表示及同構判斷[J].機械工程學報，2010,46(7):63-67.

DING Ling,LU Yi.Character arrays representation and isomorphism identif ication of kinematic chain topology graphs[J].Journal of Mechanical Engineering,2010,46(7):63-67.(in Chinese)

[4]GOLOVAN A,HENRICK K.Chemical substructure search in SQL[J].Journal of Chemical Information and Modeling,2009,49(1):22-27.

[5]CHEN Kai,GUO Chuanxiong,WU Haitao,YUAN Jing,FENG Zhenqian,CHEN Yan,LU Songwu,WU Wenfei.Generic and automatic address conf iguration for data center networks[C]//Proceedings of the ACM SIGCOMM 2010 Conference.New Delhi,India,2010:39-50.

[6]SHANGH,LIF,TANGX,WOOP Y.A new algorithm for isomorphism determination of undirected graphscircuit simulation method[J].Circuits,Systems,and Signal Processing,2011,30(5):1115-1130.

[7]LIF,SHANGH,WOOP Y.Determination of isomorphism and its applications for arbitrary graphs based on circuit simulation[J].Circuits,Systems,and Signal Processing,2008,27(5):749-761.

[8]SHANG Huiliang,LI Jichuan,CAI Qi,DONG Wenjie.An optimized algorithm for the identif ication of isomorphic undirected graphs[C]//Proceedings of 2011 International Conference on Modelling,Identif ication and Control,ICMIC 2011,Shanghai,2011:351-356.

[9]李鋒，李曉艷.圖的同構判定算法：關聯(lián)度序列法及其應用[J].復旦學報：自然科學版，2001,40(3):318-325.

LIFeng,LI Xiaoyan.Isomorphism testing algorithm for graphs:incidence degree sequence method and applications[J].Journal of Fudan University:Science Edition,2001,40(3):318-325.(in Chinese)

[10]李鋒，商慧亮.有向圖的同構判定算法:出入度序列法[J].應用科學學報，2002,20(3):258-262.

LI Feng,SHANG Huiliang.An isomorphism testing algorithm for directed graphs:the in-degree and outdegree sequence method[J].Journal of Applied Science,2002,20(3):258-262.(in Chinese)

[11]南晉華，齊歡.圖同構問題的決策神經網絡模型[J].計算機學報，2010,33(2):300-304.

NAN Jinhua,QI Huan.The decision-making neural networks model for solving the graph isomorphism problem[J].Chinese Journal of Computers,2010,33(2):300-304.(in Chinese)

[12]PORUMBEL D C. Isomorphism testing via polynomial-time graph extensions[J].Journal of Mathematical Modeling and Algorithms, 2010,10(2):119-143.

[13]ZAHIDI U A.Spectral solution for detecting isomorphic graphs with nondegenerate eigenvalues[C]//11th IEEE International Multitopic Conference,INMIC2007.Lahore,Pakistan,2007:1-4.

[14]QIU Ming,HU Haibin,JIANG Qingshan,HU Hailong.A new approach of graph isomorphism detection based on decision tree[C]//2nd International Workshop on Education Technology and Computer Science,ETCS 2010,Wuhan,Hubei,2010:32-35.

[15]ZHANG Baida,TANG Yuhua,WU Junjie,HUANG Linqi.A unique vertex deleting algorithm for graph isomorphism[C]//2011 International Symposium on Image and Data Fusion,2011,Tengchong,Yunnan,2011:1-4.

[16]徐俊明.圖論及其應用[M].安徽：中國科學技術大學出版社，1998:16.

[17]MEISTER A. Numerik linearer gleichungssysteme[M].2nd ed.Germany:Vieweg,2005.