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

曹 磊 甘志龍 賈姍姍

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

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

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

1 方法描述和程序設(shè)計(jì)

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

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

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

圖1 基本割集的確定流程

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

(1)

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

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

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

(2)

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

圖2描述了Find_CutSet函數(shù)確定節(jié)點(diǎn)編號(hào)向量S1和S2的具體過程。假設(shè)有向圖含n個(gè)節(jié)點(diǎn),則電路連接矩陣為方陣Nn×n,若有向圖的一種樹按照a12、a23、a34、…、a(n-1)n元素所對(duì)應(yīng)的支路順序構(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中。例如,搜索到的第一個(gè)樹支a12信息保存在矩陣T(n-1)×n的第一行,該樹支包含節(jié)點(diǎn)1和2,所以第一行中節(jié)點(diǎn)n1和n2所在列的元素值為1,該行其余元素值均為0。剩余樹支的連接情況以此類推,可以得到完整的樹支-節(jié)點(diǎn)關(guān)系矩陣T(n-1)×n。最后,以樹支a23為例說明獲取其對(duì)應(yīng)的節(jié)點(diǎn)編號(hào)向量S1和S2以及基本割集的具體過程。第一步,確定樹支a23在矩陣T(n-1)×n中對(duì)應(yīng)的行(第二行),并將該樹支的兩個(gè)節(jié)點(diǎn)n2和n3的編號(hào)分別臨時(shí)存儲(chǔ)在向量S1和S2中,因此有S1=[2],S2=[3]。第二步,先從矩陣T(n-1)×n中節(jié)點(diǎn)n2所在位置開始,沿著該列(第二列)搜索,查詢是否存在除自身(T22)以外值為1的元素,有T12=1,然后在該元素所對(duì)應(yīng)的行(第一行)內(nèi)繼續(xù)搜索除T12之外值為1的元素,有T11=1,并將節(jié)點(diǎn)n1的編號(hào)補(bǔ)充到向量S1中。繼續(xù)從T11所在的列搜索,若該列僅存在一個(gè)值為1元素(即T11自身),則結(jié)束該循環(huán)過程,得到最終的節(jié)點(diǎn)編號(hào)向量S1=[2, 1]。需要指出的是,如果T22所在的列存在多個(gè)值為1的元素,則需要采用同樣的規(guī)則并行獨(dú)立尋找,并將全部符合條件的節(jié)點(diǎn)編號(hào)都存儲(chǔ)在向量S1中,且節(jié)點(diǎn)編號(hào)的位置順序可以是任意的。同理,沿著節(jié)點(diǎn)n3所在的列搜索可以得到S2=[3, 4, …,n-1,n]。第三步,查詢矩陣Nn×n,按照原有向圖獲取S1和S2中各節(jié)點(diǎn)之間的連接支路關(guān)系(樹支、連支),從而得到樹支a23對(duì)應(yīng)的基本割集。

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

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

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

圖3 平面電路有向圖

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

(3)

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

(4)

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

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

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

(5)

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

按照?qǐng)D2描述的邏輯和流程,可以得到電路每個(gè)樹支所對(duì)應(yīng)的兩個(gè)存儲(chǔ)半空間中電路節(jié)點(diǎn)編號(hào)的向量S1和S2,以T矩陣中第一行的樹支①為例,得到的行向量S1和S2分別為:

(6)

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

(a) 樹支①基本割集

(b) 樹支②基本割集

(c) 樹支⑥基本割集

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

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

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

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

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

圖6 非平面電路有向圖

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

(7)

電路中6個(gè)節(jié)點(diǎn)(均位于同一平面z=0)的節(jié)點(diǎn)平面坐標(biāo)矩陣為:

(8)

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

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

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

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

(9)

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

(10)

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

(a) 樹支①基本割集

(c) 樹支⑦基本割集

(d) 樹支⑧基本割集

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

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

(11)

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

(12)

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

4 結(jié)語

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

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