第十章圖論及LTI電路的矩陣分析法

1、本章內(nèi)容第10章 圖論及LTI電路系統(tǒng)的矩陣分析法 圖論的基本概念 電路系統(tǒng)的圖矩陣表示方法、 支路方程和網(wǎng)絡(luò)圖矩陣間的相互關(guān)系 電路與系統(tǒng)方程的圖矩陣分析法(自學）10.1 圖論基礎(chǔ) 電路分析中的分析模型都是用具有特定元件特性的二端元件所組成的網(wǎng)絡(luò)，要完整的描述這樣的網(wǎng)絡(luò)，就必須知道支路間的連接特性、支路電壓和電流的參考方向以及網(wǎng)絡(luò)中元件的特性。而任何集中參數(shù)的電網(wǎng)絡(luò)都可用基爾霍夫電壓和電流定律（KVL和KCL）以及支路特性方程(VCR)來描述，因此只要著重討論電路中各元件之間的連接關(guān)系，而不管支路元件的性質(zhì)，則每一條支路都可以用一條有向的線段(線段的方向代表支路的電壓、電流參考方向)來表示

2、，這樣就可把一個復雜的電路抽象轉(zhuǎn)換為一個由點和線段集合成的圖形(拓樸圖)。例如圖8-1(a)所示網(wǎng)絡(luò)，就可抽象為8-1(b)、(c)那樣的拓樸圖。1. 圖論的基本概念l節(jié)點：一條線段的端點，或者一個孤立的點稱之為節(jié)點，如右圖中n1，n2，n3，n4均稱之為節(jié)點，通常我們用ni表示第i個節(jié)點。l支路：與兩個節(jié)點ni、nj相關(guān)聯(lián)的線段，稱為支路，圖中b1，b2，b3，b4，b5，b6均稱之為支路，通常用bi表示第i支路。 圖8-1(b)l圖：就是由有限個節(jié)點(節(jié)點集)和有限條支路(支路集)組成的集合，在該集合中每條支路恰好連接著兩個節(jié)點，而支路僅在節(jié)點上相交。 ),(G 通常我們用G表示圖。在一個

3、圖里所有的支路構(gòu)成支路集，用表示，即b1，b2，bB；而所有的節(jié)點構(gòu)成節(jié)點集合，用表示， n1，n2，nN。這里B是支路數(shù)，N是節(jié)點數(shù)，因此一個圖G可以用 表示。 無向圖與有向圖：如果圖G中每條支路都不指明支路方向，則稱之為無向圖，用Gn表示，如圖8-1(b)所示；如果圖G中每條支路都規(guī)定一定的方向，則稱之為有向圖，用Gd表示，如下圖所示。 ),(sssG子圖：如果圖 的節(jié)點集s是圖G的節(jié)點集的子集，支路集s是支路集的子集，則稱圖Gs是圖G的子圖。例如圖中，由s =n1，n2，n3和s =b1，b3，b5構(gòu)成的圖就是該圖的子集，若子集僅由一個孤立的節(jié)點組成，則稱蛻化子圖。n1n2n3b5b1b

4、3子圖l節(jié)點的維數(shù)：與一個節(jié)點相關(guān)聯(lián)的支路的數(shù)目稱為該節(jié)點的維數(shù)。例如上圖中，節(jié)點n1，n2，n5，n6都是三維的，而節(jié)點n3，n4是四維的。而零維節(jié)點稱為孤立點。l通路：長度為m的通路是m條不同支路與m+1個不同節(jié)點依次連接而成的一條路徑，在這條路徑中除始點與終點兩個節(jié)點為一維外，其余各節(jié)點都是二維的。 如圖中，支路集b4，b8，b9，b2在節(jié)點n1和n2之間構(gòu)成通路，其相應(yīng)節(jié)點為n1，n5，n4，n6，n2，其中n1和n2分別為始端節(jié)點與終端節(jié)點；而支路b5，b7，b10，b6就不能構(gòu)成n1與n2之間的一條通路，因為在該支路集中節(jié)點n3的維數(shù)超過了二維。由此可以通俗地說：“通路就是兩個節(jié)點

5、之間一條無叉道的路徑?！眑連通圖與非連通圖： 如果一個圖，在它的任意兩個節(jié)點之間，至少存在一條通路，那樣這樣的圖為連通圖。例如上圖(a)是連通圖，而圖(b)是非連通圖。l 回路：構(gòu)成閉合路徑的支路集，就是回路?；芈肥且粋€連通圖。長度為m而始端節(jié)點與終端節(jié)點相重合的通路稱為長度為m的回路，長度為1的回路稱為自回路。 對于有向圖給定的回路，常指定一順時針方向，或逆時針方向作為回路的參考方向。l網(wǎng)孔：精確的定義為：若連通平面線圖的一個回路內(nèi)部不存在任何支路，則此回路稱為網(wǎng)孔。 樹：在一個連通圖Gn中取一個子圖Gs，當且僅當Gs滿足下列三個條件時，則稱子圖Gs為Gn的樹，記為T，這三個條件是： Gs是

6、連通圖； Gs包含原圖Gn中的全部節(jié)點； Gs中不包含任何回路。 如圖8-4(a)所示的圖Gn，它的兩個樹分別如圖8-4(b)、(c)，但是8-4(d)和(e)則不是它的一個樹，因為(d)中包含一個回路，而(e)是不連通的。同一連通圖G具有許多不同的樹l 樹支、樹余和連支：構(gòu)成樹的各條支路稱為樹支，圖Gn中除去樹以外的所有支路形成Gn的另一個子圖，稱為樹余(反樹)，屬于反樹的各條支路稱為連支。例如圖8-5中圖Gn的樹支如圖8-5(b)實線所示，而(b)中虛線為連支。l樹支數(shù)目和連支數(shù)目：一個連通圖具N個節(jié)點和B條支路，則樹T每兩個節(jié)點之間至少有一條支路方能連在一起，如果要連通N個節(jié)點，要有N-

7、1條支路，又由于樹T不能包含回路，所以N個節(jié)點間支路數(shù)也不可能多于N-1條，因此對于一個具有N個節(jié)點和B條支路的連通圖，它的樹T含有N-1條樹支和B-(N-1)條連支。l割集：割集是連通圖G的一個支路集合，把這些支路移去將使圖G分離成二個部分，但是如果少移去其中一條支路，則圖仍將是連通的。這就是說割集是把一個連通圖G分成兩個分裂的子圖所需割斷數(shù)量最少的一組支路。通常用Ci表示i第個割集。例如圖8-6中，b1，b5，b6，b3構(gòu)成一個割集，如圖中虛線所示。但支路集b1，b5，b6和b2，b5，b1，b3則不是割集。l基本回路：若在選定的連通圖G的樹T加入一條連支則可得到一個且僅僅一個回路，若依次

8、加入所有的連支，則得到相應(yīng)的各個回路Li，所有的這些回路稱為基本回路；或者更簡單地說基本回路就是單連支回路，例如圖 (b)中的l1、l2、l3、l4就是基本回路。l基本割集：若選定連通圖G的樹T，每次割斷T中一條樹支和若干條連支可以得到一個且僅僅一個割集，依此方式，割斷T中所有的樹支，就得到相應(yīng)的各個割集Ci，所有這些割集稱為基本割集，或叫單樹支割集。例如圖(c)的c1，c2，c3，c4，c5均為基本割集。 因為對應(yīng)于樹T的每一條樹支有一個基本割集、對應(yīng)于每一條連支有一個基本回路，因此一個具有N個節(jié)點和B條支路的連通圖Gn有N-1個基本割集、B-(N-1)個基本回路。10.2 電路系統(tǒng)的圖矩陣

9、表示1.關(guān)聯(lián)矩陣 (1) 增廣關(guān)聯(lián)矩陣。 如果一個由N個節(jié)點和B條支路組成的有向連通圖Gd，其中增廣關(guān)聯(lián)矩陣是一個NB維的矩陣，用Aa表示，即BNkiaaA其中各元素aki的值為 不相連時與節(jié)點當支路時且支路方向指向節(jié)點連接節(jié)點當支路時且支路方向背離節(jié)點連接節(jié)點當支路kjkkjkkjkjnbnnbnnba 0,1,1 例如圖8-8有向拓樸圖GD，它的增廣關(guān)聯(lián)矩陣Aa為 111100000000101010000001110100010001000110000010100000000111 A65432110987654321annnnnnbbbbbbbbbb 有向圖Gd的增廣關(guān)聯(lián)矩陣是反映圖中

10、各節(jié)點與支路間相互聯(lián)接關(guān)系的矩陣，它完整地把節(jié)點與支路的聯(lián)結(jié)方式和支路參考方向表示了出來，其特點為 Aa的每一列向量僅有兩個非零元素，一個是 “1”，另一個是“-1”，其余的元素全部是零， 矩陣Aa的任一行向量等其余各行向量之和，但 符號相反。(2) 關(guān)聯(lián)矩陣 對于增廣關(guān)聯(lián)矩陣，如果將矩陣中所有的行相加到最后一行上，則得到一個元素全部為零的行，這意味著Aa中N行不是線性獨立的，即Aa的秩小于N，Aa是一個奇異矩陣，但是Aa中去掉任一行(即把這一行對應(yīng)的節(jié)點視為參考點)，Aa中的其余N行是線性獨立的，秩rank(Aa)=N-1；因此在Aa中刪去任一根據(jù)這些特點，任意給定一個增廣關(guān)聯(lián)矩陣，我們也就

11、可以畫出它的有向拓樸圖。行后得到一個(N-1)行的矩陣A，這就是關(guān)聯(lián)矩陣，顯然 A是一個非奇異矩陣，秩為rank(Aa)=N-1。 (3) 基爾霍夫電流定律(KCL)的矩陣形式1 考慮一個具有B條支路，N個節(jié)點的網(wǎng)絡(luò)，選第N個節(jié)點作為參考點，用箭頭指示每條支路中電流的方向，并且這樣來規(guī)定電流的符號：對于一個節(jié)點，當電流指向它時為負，當電流離開它時為正。若支路bi中的電流用Ii表示，那么我們在第k個節(jié)點上應(yīng)用KCL定律得) 1, 2, 1(01NkIaniiki 這里aki和前面Aa中定義的相同，對于其余節(jié)點的KCL方程也可以用同樣的方法寫出；現(xiàn)在我們將上式寫成矩陣形式，則基爾霍夫電流定律(KC

12、L)的矩陣形式0bAI這個方程的右邊是一個N-1維列矢量，它的元素全為零，而關(guān)聯(lián)矩陣AB)(Nkia1AIb是一個B維列矢量，即 T21bbi ,i ,iI(4) 關(guān)聯(lián)矩陣的分塊形式 在有向拓樸圖Gd中選取一個樹T，用AT表示各列對應(yīng)于該樹的樹支陣AT，用AL表示各列對應(yīng)于樹余L的連支陣，則關(guān)聯(lián)矩陣A還可以表示為分塊形式LTAAA 100010101011110100 AAA321321654LTnnnb b b b bb如圖，其關(guān)聯(lián)矩陣A可寫為(選b4,b5,b6為樹，n4為參考點)2. 基本割集矩陣(1) 增廣割集矩陣 一個割集將一連通圖分成兩個不相連的子圖，把其中一個子圖流向另一個子圖的

13、電流方向取作割集方向，用虛線上的箭頭標志它，規(guī)定支路方向和割集方向一致時取正號，支路方向與割集方向相反時取負號，若有向圖Gd的B條支路用b1，b2，bB表示，它的割集用c1，c2，cc表示，則有向圖Gd的增廣割集矩陣為CB的矩陣，即 BGkjqaQ中不在割集當支路反向中而與在割集當支路同向中并與在割集當支路kjkkjkkjkjcbccbccbq011如圖的增廣割集矩陣為01101101101100010101011100001165432154321 Qaccccccbbbbb (2) 基本割集矩陣 具有N個節(jié)點的有向圖的增廣割集矩陣的秩是N-1，與增廣關(guān)聯(lián)矩陣相比，任意地選取N-1個線性獨立

14、的行是不可能的。但是如果在有向圖中任意選定一個樹T之后，用樹T中的一條樹支結(jié)合樹余中的連支構(gòu)成一個割集，且規(guī)定割集的方向與樹支的方向相同，這就是前面定義過的基本割集，或單樹支割集，則這時的基本割集矩陣是一個（N-1）B維的矩陣。它的各行就是線性獨立的，稱之為基本割集矩陣QfBNkjq)1(fQ式中qkj與Qa元素定義相同。 0bfIQ(3) 廣義基爾霍夫電流定律(KCL)的矩陣形式 廣義的KCL表明對于任何集中參數(shù)元件所組成的網(wǎng)絡(luò)，通過一個割集的所有支路電流的代數(shù)和應(yīng)該等于零，因此用基本割集矩陣也可以將其表成矩陣形式，即0101000110010010100100010001432176543

15、21ccccbbbbbbb00007654321IIIIIII如下圖，其基本割集的KCL為 (4) 基本割集矩陣Qf的分塊形式 對有向拓樸圖Gd任意選定了一個樹T之后，則基本割集矩陣Qf也可以表為分塊形式 FIQQQLTf式中Qf為(N-1) B維，QT是一個單位矩陣，由于樹T有N-1條樹支，所以QT是一個(N-1)(N-1)方陣，而QL=F是連支的(N-1)B-(N-1)的矩陣。3. 基本回路矩陣(1) 增廣回路矩陣。 設(shè)一個有向拓樸圖Gd，它具有B條支路和L個回路，用b1，b2，bB標記支路，用l1，l2，lL標記回路，并且給每個回路任意規(guī)定一個繞行方向（順時針方向或逆時針方向），那么增廣

16、回路矩陣Ba是一個LB的矩陣BLkjbaB中不在回路當支路反向中而與在回路當支路同向中并與在回路當支路kjkkjkkjkjlbllbllbb011 如圖的增廣回路矩陣為10111011101100132154321lllbbbbbaBl1l2(2) 基本回路矩陣 若有向圖Gd具有N個節(jié)點B條支路，那么它的增廣回路矩陣Ba的秩是B-(N-1)，在有向拓樸圖中任意選定一個樹T后，用樹余中的一條連支結(jié)合樹T中的一組樹支構(gòu)成一個回路，且規(guī)定回路的方向與連支的方向相同，則這時可以得到一個B-(N-1)B維的矩陣，它的各行就均是線性獨立的，稱這個矩陣為基本回路矩陣Bf，即 BNBkjb)1(fB式中qkj

17、與Qa元素定義相同。 (3) 基爾霍夫電壓定律(KVL)的矩陣形式KVL表明：對于任一集中參數(shù)網(wǎng)絡(luò)中的任一回路，在任一時刻，沿著該回路的所有支路電壓的代數(shù)和為零。 如圖的網(wǎng)絡(luò)拓撲圖中，選b1，b2，b3，b4，b5為樹，則其基本回路的KVL方程寫成矩陣方程的形式為 1000101010100000110010011100001110004321987654321llllbbbbbbbbb 0000987654321UUUUUUUUU于是網(wǎng)絡(luò)的基本回路基爾霍夫電壓定律KVL可表示為 0bfUB(4) 基本回路矩陣Bf的分塊形式 對有向拓樸圖Gd任意選定了一個樹T之后，基本回路矩陣Bf也可以表為分

18、塊形式 I-FBBBTLTf Bf為B-(N-1) B維，BL=I是 B-(N-1)B-(N-1)的方陣。4. 圖矩陣間的關(guān)系A(chǔ)、Bf 、Qf 之間存在如下重要關(guān)系 00TTfABABf00TffTffBQQB5. 支路變量間的基本關(guān)系 設(shè)同一個連通圖Gd具有N個節(jié)點、B條支路，選定樹為T，按先樹支后連支次序排列的A、Bf、Qf陣為 F IQIQI FIBB AAA|LfTTfLT而支路電流、電壓為 LTbIIILTbUUU 上式中IT為樹支電流，IL為連支電流；UL為連支電壓，UT為樹支電壓。 對于一個具有N個節(jié)點、B條支路的連通網(wǎng)絡(luò)，當選定參考節(jié)點后，則可以寫出其余(N-1)個節(jié)點與參考節(jié)點的電位差，即(N-1)個節(jié)點的節(jié)點電壓用向量表示為 )1(21NnUUUU0bAInTbUAUfB0bf