一種通用的電路基本割集直接確定方法

曹 磊 甘志龍 賈姍姍

(華中科技大學 電氣與電子工程學院, 武漢 430074)

在求解復雜電路時,常需要借助計算機建立電路模型并進行分析。作為數(shù)學的分支,圖論為計算機輔助分析提供了一種描述復雜電路結(jié)構(gòu)的有效方法,將電路結(jié)構(gòu)(有向圖)表示為節(jié)點關(guān)聯(lián)矩陣、基本回路矩陣、基本割集矩陣等形式,得到由這些矩陣確定的獨立的基爾霍夫電壓(KVL)或電流(KCL)方程,結(jié)合支路電壓電流關(guān)系(VCR)求解出節(jié)點電位、樹支電壓或連支電流。其中,在確定基本割集矩陣時,對于平面電路的一種樹,可以采用閉合面切割法;而對于非平面電路,通常要利用基本割集的定義采用排除法一一確定,不易找全、易錯費時,適用于支路數(shù)量少、網(wǎng)絡結(jié)構(gòu)簡單的電路且通常無法確定基本割集的方向。節(jié)點關(guān)聯(lián)矩陣A轉(zhuǎn)換法利用了電路節(jié)點關(guān)聯(lián)矩陣與基本割集矩陣之間的數(shù)學對應關(guān)系,且根據(jù)計算得到的基本割集矩陣中的元素可以確定電路中的基本割集構(gòu)成及其方向,這種方法適用于所有的電路,但是計算繁瑣復雜且直觀性較差,缺乏封閉面的概念,不利于學生的理解。

本文實現(xiàn)了一種通用的電路基本割集直接確定方法和相應程序,通過平面電路和非平面電路的具體案例對程序進行了測試和驗證,豐富擴展了“電路理論”課程的相關(guān)教學內(nèi)容,促進了學生的直觀理解。

1 方法描述和程序設計

圖是節(jié)點和支路的集合[1-2]。若將電路模型轉(zhuǎn)換成電網(wǎng)絡的拓撲圖,需要把電路中的支路用線段表示、電路中的節(jié)點保持不變,并在拓撲圖上標注每條支路的參考方向,從而得到電網(wǎng)絡的有向圖。對于大規(guī)模的復雜電路,以有向圖建立矩陣,以節(jié)點電位、支路的電壓或電流作為電路變量,可列寫相應的KCL方程或KVL方程。用于描述有向圖的矩陣包括節(jié)點關(guān)聯(lián)矩陣、基本回路矩陣和基本割集矩陣[3]。針對有向圖的一種樹,割集指的是一組支路的集合,滿足條件:將割集中的全部支路移走,原先連通圖分離成且只分離成兩部分;且若少移走割集中的任意一條支路,則仍為連通圖[4]。為了保證割集的獨立性,基本割集除了滿足割集的定義外,還要求每個割集中只含有一個樹支。因此,基本割集的個數(shù)等于樹支的數(shù)目,對于含有n個節(jié)點、b條支路的電網(wǎng)絡,其樹支數(shù)為n-1,基本割集矩陣Qf的維數(shù)為(n-1) ×b。

對于簡單的二維非交叉平面電路,使用閉合面切割法可以快速找到電路每個樹支對應的基本割集及方向。但對于復雜的三維電路,傳統(tǒng)的閉合面切割法不再適用。本文提出一種通用的電路基本割集確定方法,通過輸入表示電路各節(jié)點之間連接關(guān)系的節(jié)點-節(jié)點關(guān)系矩陣,在給定電路某一種樹情況下,經(jīng)過程序的處理和計算直接得到電路的基本割集,并且能夠確定基本割集的方向。

基本割集的具體確定流程如圖1所示,實現(xiàn)的步驟如下:

圖1 基本割集的確定流程

(1)自定義節(jié)點-節(jié)點關(guān)系矩陣N,表示原電路各節(jié)點之間的連接關(guān)系(維數(shù)為n×n),矩陣元素僅由0、1和2這三個值構(gòu)成,當?shù)趇行、第j列(i≠j)的元素Nij=1時,表示電路第i和第j個節(jié)點之間連接的支路是樹支且方向由第i個節(jié)點指向第j個節(jié)點;當Nij=2時,表示第i和第j個節(jié)點之間連接的支路是連支,且方向由第i個節(jié)點指向第j個節(jié)點;當Nij=0時,表示第i和第j個節(jié)點之間沒有支路,或者第i和第j個節(jié)點之間有支路但方向由第j個節(jié)點指向第i個節(jié)點。當i=j時,Nij=0。

(1)

(2)定義原有向圖各節(jié)點的節(jié)點平面坐標矩陣P(不唯一,依據(jù)電路的對稱性和繪圖的美觀性自由確定,僅用于三維有向圖的繪制,不影響基本割集的確定),Matlab程序?qū)⒃谌S空間中重新分布所有樹支和連支,將原有向圖改畫為物理上無任何支路交叉點(除節(jié)點外)的有向圖。依據(jù)N查找電路的所有樹支和連支,對于樹支,將其在xoy面內(nèi)用帶有參考方向的線段表示(line函數(shù)),若原有向圖存在視覺上有交叉的樹支,則將兩樹支標記并且將其中任意一個樹支以曲線形式(spcrv函數(shù))拉伸到xoy面的下半空間(-z),節(jié)點均保留在xoy面內(nèi)。而對于全部連支,則將其以曲線形式拉伸到xoy面的上半空間 (+z),且具有不同的高度或方向以確保每條連支均無物理相交點,最終可以得到改畫后的三維空間有向圖。

(3)根據(jù)N以及自行編寫的基本割集搜索函數(shù)Find_CutSet確定各樹支對應的基本割集,如圖2所示。將平面電路基本割集的閉合平面切割判斷方法擴展到三維空間,則空間中存在閉合曲面C僅與某個樹支和任意多個連支相切割。Find_CutSet函數(shù)首先將節(jié)點-節(jié)點關(guān)系矩陣N中所有的樹支連接情況提取并存儲在樹支-節(jié)點關(guān)系矩陣T中,該矩陣的行數(shù)為樹支的個數(shù),列數(shù)為節(jié)點數(shù),矩陣元素的定義為:

圖2 Find_CutSet函數(shù)確定基本割集節(jié)點編號向量S1和S2

(2)

依據(jù)此定義,假設樹支i的兩個節(jié)點編號分別為j1和j2,則有Tij1=1,Tij2=1,且第i行的其余元素為0。依據(jù)基本割集的定義,三維曲面C將節(jié)點j1和j2分隔在曲面的兩側(cè)的半空間中,而其他任一樹支的兩個節(jié)點均分布在曲面C的同一側(cè)。程序分別使用行向量S1和S2存儲j1和j2所在半空間中的所有電路節(jié)點編號,因此行向量S1和S2具有下述特征:S1和S2的最少元素個數(shù)為1;兩者存儲的節(jié)點編號不重合,且元素個數(shù)之和為常數(shù)(電路的總節(jié)點數(shù));每個樹支均對應一對獨立的S1和S2。最后通過N矩陣查詢并恢復S1和S2中各節(jié)點之間的真實連接關(guān)系,即可以得到樹支i對應的基本割集,其余樹支對應的基本割集采用同樣的方法。

圖2描述了Find_CutSet函數(shù)確定節(jié)點編號向量S1和S2的具體過程。假設有向圖含n個節(jié)點,則電路連接矩陣為方陣Nn×n,若有向圖的一種樹按照a12、a23、a34、…、a(n-1)n元素所對應的支路順序構(gòu)成,則根據(jù)電路連接矩陣的定義有a12=a23=a34=…=a(n-1)n=1,Nn×n中的其他元素(0或2)根據(jù)有向圖具體確定。然后,程序從Nn×n的第一列開始查找所有值為1的元素,即電路中的樹支支路,豎直的虛線箭頭表示沿列的搜索方向是從上到下,水平的虛線箭頭表示沿行的搜索方向是從左到右。遍歷完成后,矩陣Nn×n中的元素a12、a23、a34、…、a(n-1)n被篩選出來,然后按照搜索到的先后順序?qū)⒅愤B接信息保存到矩陣T(n-1)×n中。例如,搜索到的第一個樹支a12信息保存在矩陣T(n-1)×n的第一行,該樹支包含節(jié)點1和2,所以第一行中節(jié)點n1和n2所在列的元素值為1,該行其余元素值均為0。剩余樹支的連接情況以此類推,可以得到完整的樹支-節(jié)點關(guān)系矩陣T(n-1)×n。最后,以樹支a23為例說明獲取其對應的節(jié)點編號向量S1和S2以及基本割集的具體過程。第一步,確定樹支a23在矩陣T(n-1)×n中對應的行(第二行),并將該樹支的兩個節(jié)點n2和n3的編號分別臨時存儲在向量S1和S2中,因此有S1=[2],S2=[3]。第二步,先從矩陣T(n-1)×n中節(jié)點n2所在位置開始,沿著該列(第二列)搜索,查詢是否存在除自身(T22)以外值為1的元素,有T12=1,然后在該元素所對應的行(第一行)內(nèi)繼續(xù)搜索除T12之外值為1的元素,有T11=1,并將節(jié)點n1的編號補充到向量S1中。繼續(xù)從T11所在的列搜索,若該列僅存在一個值為1元素(即T11自身),則結(jié)束該循環(huán)過程,得到最終的節(jié)點編號向量S1=[2, 1]。需要指出的是,如果T22所在的列存在多個值為1的元素,則需要采用同樣的規(guī)則并行獨立尋找,并將全部符合條件的節(jié)點編號都存儲在向量S1中,且節(jié)點編號的位置順序可以是任意的。同理,沿著節(jié)點n3所在的列搜索可以得到S2=[3, 4, …,n-1,n]。第三步,查詢矩陣Nn×n,按照原有向圖獲取S1和S2中各節(jié)點之間的連接支路關(guān)系(樹支、連支),從而得到樹支a23對應的基本割集。

(4)將基本割集在三維空間形象顯示。用一個三維的半球面表示用于切割電路的三維曲面,將基本割集中的各支路描繪在同一個三維圖中,利用連接支路的兩個節(jié)點編號來表示支路,其中樹支上的箭頭方向代表該基本割集的方向(流入或者流出基本割集對應的半球面)。

2 案例一:平面電路基本割集

以圖3所示的含有5個節(jié)點、8條支路的平面電路為例,選取{①,②,⑥,⑦}(實線)四條支路作為樹支,剩余支路(虛線)作為連支。

圖3 平面電路有向圖

依據(jù)程序設計原理和流程,該平面電路有向圖對應的節(jié)點-節(jié)點關(guān)系矩陣為:

(3)

為保證繪制出來的三維圖像的對稱和美觀性,定義電路中各節(jié)點(均位于同一平面z=0內(nèi))的節(jié)點平面坐標矩陣為:

(4)

其中,節(jié)點1為參考原點(0,0),水平向右方向代表+x軸,豎直向下代表+y軸,支路①,②,③,④構(gòu)成正方形,支路相對長度(邊長)為2(無單位)。

以節(jié)點-節(jié)點關(guān)系矩陣和節(jié)點平面坐標矩陣為輸入,程序會自動在三維空間改畫電路,將電路的樹支和連支分配或拉伸到不同的空間位置,如圖4所示。

根據(jù)輸入的節(jié)點-節(jié)點關(guān)系矩陣,程序調(diào)用函數(shù)Find_CutSet來求解電路的基本割集,首先根據(jù)節(jié)點-節(jié)點關(guān)系矩陣N得到樹支-節(jié)點關(guān)系矩陣T為:

(5)

矩陣的第一行表示樹支①,只有第一列和第二列的矩陣值不為0,表示電路的樹支①由電路節(jié)點1和2連接而成,據(jù)此可以分析其他樹支連接情況。

按照圖2描述的邏輯和流程,可以得到電路每個樹支所對應的兩個存儲半空間中電路節(jié)點編號的向量S1和S2,以T矩陣中第一行的樹支①為例,得到的行向量S1和S2分別為:

(6)

式(6)表示節(jié)點1被曲面C分隔在某半空間中,其余節(jié)點分隔在另一半空間中,然后查詢N矩陣,確定S1中節(jié)點與S2中節(jié)點存在的所有支路,即節(jié)點1和2構(gòu)成樹支①,節(jié)點4和1構(gòu)成連支④,節(jié)點3和1構(gòu)成連支⑧,因此樹支①對應的基本割集為{①,④,⑧}。以此類推,最終可以得到所有樹支對應的基本割集,將曲面C以半球面的形式形象地顯示,該平面電路所對應的基本割集(含方向)如圖5所示。

(a) 樹支①基本割集

(b) 樹支②基本割集

(c) 樹支⑥基本割集

(d)樹支⑦基本割集圖5 平面電路的基本割集

以圖5(a)所示的樹支①所對應基本割集為例,采用支路兩端的節(jié)點來表示該支路,例如線段1-2表示節(jié)點1和2所連接的樹支①,線段1-3表示節(jié)點1和3所連接的連支⑧,線段1-4表示節(jié)點1和4所連接的連支④。圖中的箭頭表示原有向圖各支路的參考方向,其中樹支上的箭頭代表該基本割集的方向。

該程序運行得到的結(jié)果與采用閉合面切割或定義法(請讀者自行驗證)得到結(jié)果一致。

3 案例二:非平面電路基本割集

為進一步驗證方法的應用廣泛性,以圖6所示的含有6個節(jié)點、9條支路的非平面電路為例,選取{①,③,⑦,⑧,⑨}(實線)五條支路作為樹支,剩余支路(虛線)作為連支。

圖6 非平面電路有向圖

根據(jù)非平面電路的有向圖列寫電路的節(jié)點-節(jié)點關(guān)系矩陣:

(7)

電路中6個節(jié)點(均位于同一平面z=0)的節(jié)點平面坐標矩陣為:

(8)

其中,節(jié)點1為參考原點(0,0),水平向右方向代表+x軸,豎直向下代表+y軸,支路①,②,③,④構(gòu)成正方形,支路相對長度(邊長)為4(無單位)。所有節(jié)點均位于同一平面內(nèi)(z=0)。

以節(jié)點-節(jié)點關(guān)系矩陣和節(jié)點平面坐標矩陣為輸入,程序會自動在三維空間改畫電路,將電路的樹支和連支分配或拉伸到不同的空間位置,如圖7所示。

圖7 非平面電路的三維畫法

根據(jù)節(jié)點-節(jié)點關(guān)系矩陣N得到樹支-節(jié)點關(guān)系矩陣T為:

(9)

以T矩陣中第一行的樹支①為例,得到的基本割集節(jié)點編號向量S1和S2分別為

(10)

查詢N矩陣,確定S1中節(jié)點與S2中節(jié)點存在的所有支路,即節(jié)點1和2構(gòu)成樹支①,節(jié)點1和3構(gòu)成連支⑤,節(jié)點4和1構(gòu)成連支④,因此樹支①對應的基本割集為{①,④,⑤}。以此類推,最終可以得到所有樹支對應的基本割集,將切割曲面以半球面的形式形象地顯示,該非平面電路所對應的基本割集(含方向)如圖8所示。

(a) 樹支①基本割集

(c) 樹支⑦基本割集

(d) 樹支⑧基本割集

(e) 樹支⑨基本割集圖8 非平面電路的基本割集

以圖8 (a)所示樹支①的基本割集為例,線段1-2表示電路中由電路節(jié)點1和2所連接的樹支①,線段1-3表示由電路節(jié)點1和3所連接的連支⑤,線段1-4表示由電路節(jié)點1和4所連接的連支④。基本割集的方向與樹支①的方向一致,樹支④的方向與樹支①的方向相反,樹支⑤的方向與樹支①的方向相同,因此可以寫出基本割集矩陣中樹支①對應的一行為:

(11)

以此類推,可以寫出圖8 (b)～ (e)各樹支對應的基本割集及方向,最終得到該非平面電路的基本割集矩陣為:

(12)

對于非平面電路,基本割集矩陣可以通過節(jié)點關(guān)聯(lián)矩陣間接轉(zhuǎn)換得到,其與該程序直接得到的結(jié)果(12)一致,請讀者自行驗證。

4 結(jié)語

本文提出、實現(xiàn)并驗證了一種基于閉合球面的通用的電路基本割集直接確定方法,適用于平面電路和非平面電路。基于自行定義的節(jié)點-節(jié)點關(guān)系矩陣和節(jié)點平面坐標矩陣,依據(jù)一定的支路分配規(guī)則,將電路有向圖進行三維空間的改畫,依據(jù)該方法撰寫的程序運行得到的各樹支對應的基本割集可在三維空間形象地顯示,此外,基本割集矩陣也可從三維圖中直觀地得到,用于列寫電路方程和求解電路。

該方法彌補了教材中已有方法的不足,有利于豐富非平面電網(wǎng)絡的教學內(nèi)容,加深學生對相關(guān)知識的理解和應用,對教學具有良好的助益。