網(wǎng)絡(luò)圖論和網(wǎng)絡(luò)方程

網(wǎng)絡(luò)圖論和網(wǎng)絡(luò)方程第一頁，共二十四頁，2022年，8月28日本章要求

一、重點(diǎn)掌握有關(guān)網(wǎng)絡(luò)的拓?fù)鋱D中的基本知識(shí)。

二、熟練掌握節(jié)點(diǎn)關(guān)聯(lián)矩陣，基本回路矩陣和基本割集矩陣以及網(wǎng)孔矩陣的列寫方法。

三、著重掌握網(wǎng)絡(luò)圖論中的節(jié)點(diǎn)分析法。

四、簡介網(wǎng)絡(luò)圖論中的網(wǎng)孔分析法，回路分析法和割集分析法。

說明：補(bǔ)充教材中的§11-6

含受控源電路的節(jié)點(diǎn)分析法和§11-8靈敏度分析，不作要求。第二頁，共二十四頁，2022年，8月28日概述圖論的起源與發(fā)展1．哥尼斯堡七橋難題問題：能否從任一陸地出發(fā)，走遍七橋，且每橋只走一次，又回到原出發(fā)點(diǎn)。歐拉結(jié)論：實(shí)現(xiàn)一筆畫的充要條件，奇次點(diǎn)數(shù)等于0或2。歐拉圈：奇次點(diǎn)數(shù)=0，從任一點(diǎn)出發(fā)，一筆畫回到原出發(fā)點(diǎn)。歐拉路：奇次點(diǎn)數(shù)=2，一筆能畫出來的路。

第三頁，共二十四頁，2022年，8月28日2．哈密爾頓環(huán)球旅行問題1857年英國數(shù)學(xué)家哈密爾頓發(fā)明了一個(gè)玩具。一個(gè)木制的正12面體，每面是個(gè)五角星，三面交于一角，共20個(gè)角，每個(gè)角標(biāo)注世界上一個(gè)重要城市。

問題：旅行者沿著12面體的邊，找一條經(jīng)過所有城市恰好一次而最后返回原來的出發(fā)城市的閉合回路。該回路稱為哈密爾頓圈。第四頁，共二十四頁，2022年，8月28日3．四色問題問題：一張畫在球面或平面上的地圖，相鄰國家如果涂以不同的顏色，只用四種顏色是否足夠？4．求電路的拓?fù)浣鈫栴}

1845年，基爾霍夫提出了電路中兩個(gè)最重要的定律KVL和KCL。第五頁，共二十四頁，2022年，8月28日11-1網(wǎng)絡(luò)的圖一、網(wǎng)絡(luò)的拓?fù)鋱D

1.拓?fù)潢P(guān)系式實(shí)例設(shè)一電路如圖uS1-+iS2R3R4L5C6i1abcd12i2i3i4i5i63結(jié)構(gòu)數(shù)據(jù)：網(wǎng)孔數(shù)m=3；節(jié)點(diǎn)數(shù)n=4

；支路數(shù)b=6

。元件編號(hào)即為支路編號(hào)。2b法方程理論KCLKVLVCR｛｝取決于電路結(jié)構(gòu)－取決于支路元件

選支路電壓和支路電流為電路變量，設(shè)其為關(guān)聯(lián)方向，沿網(wǎng)孔方向巡行有i1+i3-i2=0i4+i5-i3=0i6-i4-i1=0u1-u4-u3=0u2+u3+u5=0u4+u6-u5=0

此方程組只取決于電路結(jié)構(gòu)。

將此方程組稱為電網(wǎng)絡(luò)的一組“拓?fù)洹标P(guān)系式。topology“拓?fù)洹?/p>

漢譯有“結(jié)構(gòu)”之意。

結(jié)論：若已知電網(wǎng)絡(luò)的結(jié)構(gòu)，即可列出各支路電壓和電流的一組拓?fù)潢P(guān)系式，此組關(guān)系式與各支路元件的種類和性質(zhì)無關(guān)。第六頁，共二十四頁，2022年，8月28日2.網(wǎng)絡(luò)的拓?fù)鋱D定義：

對一個(gè)電網(wǎng)絡(luò)，為突出其結(jié)構(gòu)特點(diǎn)，將電網(wǎng)絡(luò)中的每個(gè)元件用一條線段代替后所得到的聯(lián)接圖形稱為該電網(wǎng)絡(luò)的拓?fù)鋱D，簡稱網(wǎng)絡(luò)的圖，一般用G表示。123456G123456G123456G123456G

圖的特點(diǎn)：

(1)圖只保留原電網(wǎng)絡(luò)的聯(lián)接關(guān)系；

(2)圖中的線段長短和曲直無關(guān)緊要。如uS1-+iS2R3R4L5C6i1acdi2i3i4i5i6b第七頁，共二十四頁，2022年，8月28日也可以這樣定義：由有限個(gè)點(diǎn)的集合以及連接兩點(diǎn)的若干條線段所組成的圖形。

—頂點(diǎn)集（節(jié)點(diǎn)）

—邊集（支路）V={a,b,c,d}E={1,2,3,4,5,6}|V|=N頂（節(jié)）點(diǎn)數(shù)邊數(shù)|E|=B

說明：

（1）關(guān)聯(lián)相鄰；

（2）幾個(gè)元件可算作一個(gè)支路；（3）電路與拓?fù)鋱D中的編號(hào)一致；（4）圖的形狀；（5）點(diǎn)和邊的刪除。第八頁，共二十四頁，2022年，8月28日二、圖的邊(支路)、頂點(diǎn)(節(jié)點(diǎn))

1.邊(支路)：

圖中所替代每個(gè)元件的線段稱為圖的邊，或稱圖的支路。用B表示邊數(shù)(支路數(shù))

2.頂點(diǎn)(節(jié)點(diǎn))：

圖中每邊的兩個(gè)端點(diǎn)，或兩個(gè)和兩個(gè)以上邊的聯(lián)接點(diǎn)稱為圖的頂點(diǎn)，或稱圖的節(jié)點(diǎn)。用N表示頂點(diǎn)數(shù)(節(jié)點(diǎn)數(shù))

。

注意：圖中的節(jié)點(diǎn)與原基礎(chǔ)理論中的節(jié)點(diǎn)不同，兩個(gè)元件串聯(lián)線段的聯(lián)接點(diǎn)就是圖中的一個(gè)節(jié)點(diǎn)(頂點(diǎn))。

注意：圖中的支路與原基礎(chǔ)理論中的支路不同，代表每個(gè)元件的線段就是圖中的一個(gè)支路(邊)。第九頁，共二十四頁，2022年，8月28日三、連通圖、有向圖和子圖

1.連通圖和非連通圖

在圖中的任兩個(gè)節(jié)點(diǎn)(頂點(diǎn))之間至少存在一條沿著支路(邊)相連通的圖稱為連通圖，否則稱為非連通圖。非連通圖今后凡不特別指明時(shí)，皆為研究連通圖。連通圖·abcd第十頁，共二十四頁，2022年，8月28日

2.有向圖

所有支路都指定了方向的圖，則稱為有向圖，在有向圖中，支路方向用于表示電路中電壓與電流的關(guān)聯(lián)參考方向。uS1-+iS2R3R4L5C6i1abcdi2i3i4i5i6123456G有向圖acbd兩條規(guī)定：

(1)圖中各邊的方向與所對應(yīng)電路中各元件上的電流方向一致；

(2)取各支路的電壓與電流方向?yàn)殛P(guān)聯(lián)方向。如ab3i3+-u3第十一頁，共二十四頁，2022年，8月28日

3.子圖和補(bǔ)圖實(shí)例123456acbdG=+c213abdG1456cbdG2

G1和G2的總和包括了G的全部支路和節(jié)點(diǎn)。

子圖：如果圖G1

是圖G

的一部分，即G1中的每個(gè)支路和節(jié)點(diǎn)都是圖G中的支路和節(jié)點(diǎn)，則稱圖G1為圖G的一個(gè)子圖。

G1和G2都是G的子圖。第十二頁，共二十四頁，2022年，8月28日

補(bǔ)圖：123456acbdGc213abd子圖G1互為補(bǔ)圖

如果把一個(gè)圖G

分成兩個(gè)子圖，而且兩個(gè)子圖中沒有相同的支路，但它們共同包括了原圖G

中的全部支路，則稱此兩個(gè)子圖互為補(bǔ)圖。456cbd子圖G2如補(bǔ)圖特點(diǎn)：(1)互補(bǔ)性只對支路而言；(2)互補(bǔ)的子圖之間必有共同的節(jié)點(diǎn)。第十三頁，共二十四頁，2022年，8月28日四、圖的樹

1.樹的定義：

一個(gè)圖G

的樹是指具備下述3個(gè)條件的子圖。

條件(1)：該子圖包括原圖G中的全部節(jié)點(diǎn)。

條件(2)：該子圖是一個(gè)連通圖。

條件(3)：該子圖不含有回路。

包括原圖中的全部節(jié)點(diǎn)，但不含有回路的一個(gè)連通子圖稱為原圖的一個(gè)樹，用T

表示。123456acbdG256acbdT1:{2,5,6}356acbd如集合寫法36acbd4T3:{3,4,6}，T2:{3,5,6}，第十四頁，共二十四頁，2022年，8月28日

2.樹支、連支和樹余(連支集)

(1)樹支：組成樹的每個(gè)支路稱為樹支，用T支表示。

(2)連支：對一個(gè)圖G除去所選樹的樹支以外的每個(gè)支路稱為連支，用L支表示。T支為2,5和6T支為3,5和6L支為1,3和4L2:{1,2,4}L支為1,2和4

(3)樹余(連支集)：與樹互補(bǔ)的子圖稱為樹余，又稱連支集，用L表示。L1:{1,3,4}樹支：連支：樹余：256acbdT1:{2,5,6}356acbdT2:{3,5,6}123456acbdG如第十五頁，共二十四頁，2022年，8月28日316c

3.找樹的方法

先選取一個(gè)支路為樹支，然后每次增加一個(gè)支路，直到再增加新的樹支就要構(gòu)成回路為止。123456acbdG如5b2ad

為此，樹也可定義為：構(gòu)成一個(gè)不含回路的連通子圖的最多支路集。

4.樹數(shù)、樹支數(shù)和連支數(shù)

(1)樹數(shù)：是指一個(gè)圖中所含樹的數(shù)目，用T數(shù)表示。對任意兩個(gè)頂點(diǎn)都有邊的完全圖，可有N為節(jié)點(diǎn)(頂點(diǎn))數(shù)如圖G為完全圖，N=4N-2T數(shù)=N則T數(shù)=44-2=16即，對圖G可有16個(gè)樹。4第十六頁，共二十四頁，2022年，8月28日

(2)樹支數(shù)：是指一個(gè)樹中所含支路的數(shù)目，用T支數(shù)表示。T支數(shù)=N-1123456acbdG如N=4每個(gè)樹中的支路數(shù)為

T支數(shù)=4-1=3256acbdT1:{2,5,6}356acbdT2:{3,5,6}36acbd4T2:{3,4,6}

(3)連支數(shù)：是指構(gòu)成樹余中所含支路的數(shù)目用L支數(shù)表示。L支數(shù)=B-(N-1)=B-N+1如圖G中B=6,N=4L支數(shù)=6-4+1=3第十七頁，共二十四頁，2022年，8月28日c3a2

例題已知：電路結(jié)構(gòu)和各支路電流如圖。求:(1)畫出該電路的有向圖。

(2)找出該圖的4個(gè)樹和相應(yīng)的樹余(連支集)。

(3)

寫出該圖的樹數(shù)T數(shù)。解：(1)有向圖abcd123456(2)找4個(gè)樹和相應(yīng)樹余b1d

T支數(shù)=4-1=3

T1:{1,2,3}

L1:{4,5,6}連支集d5c3a2b

T2:{2,3,5}

L2:{1,4,6}連支集c45b1da

T4:{1,5,4}

L4:{2,3,6}樹余d5c3a4b

T3:{3,4,5}

L3:{1,2,6}樹余(3)樹數(shù)N-2T數(shù)=N=44-2=16R2R3R5R6R4bdac+-uSi1i2i3i4i5i6第十八頁，共二十四頁，2022年，8月28日回路：

從圖中的某一個(gè)頂點(diǎn)出發(fā)，沿著邊和頂點(diǎn)不重復(fù)地巡行一周回到原出發(fā)的頂點(diǎn)所得到的閉合路徑稱為回路?；芈窋?shù)用M表示。練習(xí)題電網(wǎng)絡(luò)為下圖，各元件下標(biāo)按序編號(hào)。IS1L3L2R4R6R5C7C8abcdgefM**(1)畫出該電網(wǎng)絡(luò)的圖(2)支路(邊)數(shù)B=8。(3)節(jié)點(diǎn)(頂點(diǎn))數(shù)N=7。(4)回路數(shù)M=4。23678abcdefg145五、回路和基本回路第十九頁，共二十四頁，2022年，8月28日從圖中任一節(jié)點(diǎn)出發(fā)，沿支路循行一周，又回到原出發(fā)點(diǎn)的閉合路徑。也可定義為：

…

環(huán)加（求和）：兩個(gè)集合相加去掉公共部分。

獨(dú)立回路

｛自然網(wǎng)孔

每選一個(gè)新回路，至少包含一個(gè)新支路基本回路

第二十頁，共二十四頁，2022年，8月28日基本回路：一個(gè)連支+若干樹支組成的回路

基本回路數(shù)=連支數(shù)=b-n+1

基本回路方向與連支方向一致

基本回路環(huán)加可以求得一個(gè)圖的全部回路

（

100

010

001

110

011

101

111

0000無效回路L個(gè)基本回路

有效回路數(shù)為

第二十一頁，共二十四頁，2022年，8月28日六、割集和基本割集割集：可將一連通圖分割為兩個(gè)連通部分的極小邊集

Q1=｛