圖論ppt8電子科大楊春

1、 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 1Email: 圖論及其應(yīng)用圖論及其應(yīng)用任課教師：楊春任課教師：楊春數(shù)學(xué)科學(xué)學(xué)院數(shù)學(xué)科學(xué)學(xué)院 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 2本次課主要內(nèi)容本次課主要內(nèi)容(一一)、生成樹(shù)的概念與性質(zhì)、生成樹(shù)的概念與性質(zhì)(二二)、生成樹(shù)的計(jì)數(shù)、生成樹(shù)的計(jì)數(shù)(三三)、回路系統(tǒng)簡(jiǎn)介、回路系統(tǒng)簡(jiǎn)介 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 31、生成樹(shù)的概念、生成樹(shù)的

2、概念(一一)、生成樹(shù)的概念與性質(zhì)、生成樹(shù)的概念與性質(zhì)定義定義1 圖圖G的一個(gè)生成子圖的一個(gè)生成子圖T如果是樹(shù)，稱它為如果是樹(shù)，稱它為G的一棵的一棵生成樹(shù)；若生成樹(shù)；若T為森林，稱它為為森林，稱它為G的一個(gè)生成森林。的一個(gè)生成森林。生成樹(shù)的邊稱為樹(shù)枝，生成樹(shù)的邊稱為樹(shù)枝，G中非生成樹(shù)的邊稱為弦。中非生成樹(shù)的邊稱為弦。例如：例如：粗邊構(gòu)成的子圖為粗邊構(gòu)成的子圖為G的生成樹(shù)。的生成樹(shù)。圖圖G 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 42、生成樹(shù)的性質(zhì)、生成樹(shù)的性質(zhì)定理定理1 每個(gè)連通圖至少包含一棵生成樹(shù)。每個(gè)連通圖至少包含一棵生成樹(shù)

3、。證明：如果連通圖證明：如果連通圖G是樹(shù)，則其本身是一棵生成樹(shù)；是樹(shù)，則其本身是一棵生成樹(shù)；若連通圖若連通圖G中有圈中有圈C，則去掉，則去掉C中一條邊后得到的圖仍中一條邊后得到的圖仍然是連通的，這樣不斷去掉然是連通的，這樣不斷去掉G中圈，最后得到一個(gè)中圈，最后得到一個(gè)G的的無(wú)圈連通子圖無(wú)圈連通子圖T，它為，它為G的一棵生成樹(shù)。的一棵生成樹(shù)。 定理定理1的證明實(shí)際上給出了連通圖的證明實(shí)際上給出了連通圖G的生成樹(shù)的求法，的生成樹(shù)的求法，該方法稱為破圈法。該方法稱為破圈法。 利用破圈法，顯然也可以求出任意圖的一個(gè)生成森林。利用破圈法，顯然也可以求出任意圖的一個(gè)生成森林。 0.8 1 0.6 0.4

4、0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 5推論推論 若若G是是(n, m)連通圖，則連通圖，則mn-1n-1連通圖連通圖G的生成樹(shù)一般不唯一！的生成樹(shù)一般不唯一！(二二)、生成樹(shù)的計(jì)數(shù)、生成樹(shù)的計(jì)數(shù)1、凱萊遞推計(jì)數(shù)法、凱萊遞推計(jì)數(shù)法 凱萊凱萊(Cayley 18211895): 劍橋大學(xué)數(shù)學(xué)教授，著名劍橋大學(xué)數(shù)學(xué)教授，著名代數(shù)學(xué)家，發(fā)表論文數(shù)僅次于代數(shù)學(xué)家，發(fā)表論文數(shù)僅次于Erdos ,Euler, Cauchy. 著著名成果是名成果是1854年定義了抽象群，并且得到著名定理：任年定義了抽象群，并且得到著名定理：任意一個(gè)群都和一個(gè)變換群同構(gòu)。同時(shí)，他也是

5、一名出色意一個(gè)群都和一個(gè)變換群同構(gòu)。同時(shí)，他也是一名出色的律師，作律師的律師，作律師14年期間，發(fā)表年期間，發(fā)表200多篇數(shù)學(xué)論文，著多篇數(shù)學(xué)論文，著名定理也是在該期間發(fā)表的。名定理也是在該期間發(fā)表的。 凱萊生成樹(shù)遞推計(jì)數(shù)公式是他在凱萊生成樹(shù)遞推計(jì)數(shù)公式是他在1889年建立的。年建立的。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 6定義定義2 圖圖G的邊的邊e稱為被收縮，是指刪掉稱為被收縮，是指刪掉e后，把后，把e的兩的兩個(gè)端點(diǎn)重合，如此得到的圖記為個(gè)端點(diǎn)重合，如此得到的圖記為G.ee1e5e2e4e3用用(G)(G)表示表示G

6、 G的生成樹(shù)棵數(shù)。的生成樹(shù)棵數(shù)。定理定理2(Cayley) 設(shè)設(shè)e是是G的一條邊，則有：的一條邊，則有：()()()GGeG e證明：對(duì)于證明：對(duì)于G的一條邊的一條邊e來(lái)說(shuō)，來(lái)說(shuō)，G的生成樹(shù)中包含邊的生成樹(shù)中包含邊e的的棵數(shù)為棵數(shù)為G.e ，而不包含，而不包含e的棵數(shù)為的棵數(shù)為G-e. 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 7例例1，利用凱萊遞推法求下圖生成樹(shù)的棵數(shù)。，利用凱萊遞推法求下圖生成樹(shù)的棵數(shù)。共共8棵生成樹(shù)。棵生成樹(shù)。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.

7、5 1 n 8 凱萊公式的缺點(diǎn)之一是計(jì)算量很大，其次是不能具凱萊公式的缺點(diǎn)之一是計(jì)算量很大，其次是不能具體指出每棵生成樹(shù)。體指出每棵生成樹(shù)。2、關(guān)聯(lián)矩陣計(jì)數(shù)法、關(guān)聯(lián)矩陣計(jì)數(shù)法定義定義3 ：nm矩陣的一個(gè)階數(shù)為矩陣的一個(gè)階數(shù)為minn, m的子方陣，的子方陣，稱為它的一個(gè)主子陣；主子陣的行列式稱為主子行列式。稱為它的一個(gè)主子陣；主子陣的行列式稱為主子行列式。 顯然，當(dāng)顯然，當(dāng)nm時(shí)，時(shí)，nm矩陣矩陣 個(gè)主子陣。個(gè)主子陣。nmC定理定理3 設(shè)設(shè)Am是連通圖是連通圖G的基本關(guān)聯(lián)矩陣的主子陣，則的基本關(guān)聯(lián)矩陣的主子陣，則Am非奇異的充分必要條件是相應(yīng)于非奇異的充分必要條件是相應(yīng)于Am的列的那些邊構(gòu)的列

8、的那些邊構(gòu)成成G的一棵生成樹(shù)。的一棵生成樹(shù)。證明：必要性證明：必要性 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 9 設(shè)設(shè)Am是是Af的一個(gè)非奇異主子陣，并設(shè)與的一個(gè)非奇異主子陣，并設(shè)與Am的列相對(duì)的列相對(duì)應(yīng)的邊構(gòu)成應(yīng)的邊構(gòu)成G的子圖的子圖Gm. 由于由于Am有有n-1行，故行，故Gm應(yīng)該有應(yīng)該有n個(gè)頂點(diǎn)個(gè)頂點(diǎn)(包括參考點(diǎn)包括參考點(diǎn)); 又又Am有有n-1列列,所以所以Gm有有n-1條邊。而條邊。而Am非奇異，故非奇異，故Am的的秩為秩為n-1 ,即即Gm連通。這說(shuō)明連通。這說(shuō)明Gm是是n個(gè)點(diǎn)，個(gè)點(diǎn)，n-1條邊的連通條邊的連通圖，

9、所以，它是樹(shù)。圖，所以，它是樹(shù)。充分性充分性 如果如果Am的列對(duì)應(yīng)的邊作成的列對(duì)應(yīng)的邊作成G的一棵生成樹(shù)，因樹(shù)是連通的一棵生成樹(shù)，因樹(shù)是連通的，所以，它對(duì)應(yīng)的基本關(guān)聯(lián)矩陣的，所以，它對(duì)應(yīng)的基本關(guān)聯(lián)矩陣Am非奇異。非奇異。 該定理給出了求連通圖該定理給出了求連通圖G的所有生成樹(shù)的方法：的所有生成樹(shù)的方法： (1) 寫出寫出G的關(guān)聯(lián)矩陣，進(jìn)一步寫出基本關(guān)聯(lián)矩陣，的關(guān)聯(lián)矩陣，進(jìn)一步寫出基本關(guān)聯(lián)矩陣，記住參考點(diǎn)；記住參考點(diǎn)； 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 10 (2) 找出基本關(guān)聯(lián)矩陣的非奇異主子陣，對(duì)每個(gè)這樣找出基本關(guān)聯(lián)矩

10、陣的非奇異主子陣，對(duì)每個(gè)這樣的主子陣，畫(huà)出相應(yīng)的生成樹(shù)。的主子陣，畫(huà)出相應(yīng)的生成樹(shù)。例例2，畫(huà)出下圖，畫(huà)出下圖G的所有不同的生成樹(shù)。的所有不同的生成樹(shù)。1234abcdeG解：取解：取4為參考點(diǎn)，為參考點(diǎn)，G的基本關(guān)聯(lián)矩陣為：的基本關(guān)聯(lián)矩陣為：110000111000011fAabcde123 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 11共有共有10個(gè)主子陣，非奇異主子陣個(gè)主子陣，非奇異主子陣8個(gè)，它們是：個(gè)，它們是：1234abd1110011001Aabd1232110010001Aabe1231234abe 0.8 1

11、0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 123100011001Aacd1234100010001Aace1231234acd1234ace 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 135100010011Aade1236100111001Abcd1233124ade1234bcd 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 147100110001Abce1238100110011Abde1231234bc

12、e1234bde注：該方法的優(yōu)點(diǎn)是不僅指出生成樹(shù)棵數(shù)，而且能繪注：該方法的優(yōu)點(diǎn)是不僅指出生成樹(shù)棵數(shù)，而且能繪出所有不同生成樹(shù)；缺點(diǎn)是找所有非奇異主子陣計(jì)算出所有不同生成樹(shù)；缺點(diǎn)是找所有非奇異主子陣計(jì)算量太大！量太大！ 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 15定理定理3 (矩陣樹(shù)定理矩陣樹(shù)定理) 設(shè)設(shè)G是頂點(diǎn)集合為是頂點(diǎn)集合為V(G)=v1,v2,vn,的圖，設(shè)的圖，設(shè)A=(aij)是是G的鄰接矩陣，的鄰接矩陣，C=(cij)是是n階方陣，其中：階方陣，其中：3、矩陣樹(shù)定理、矩陣樹(shù)定理(),iijijd vijcaij則則G

13、的生成樹(shù)棵數(shù)為的生成樹(shù)棵數(shù)為C的任意一個(gè)余子式的值。的任意一個(gè)余子式的值。說(shuō)明：說(shuō)明：(1) 該定理是由物理學(xué)家克希荷夫提出的。他于該定理是由物理學(xué)家克希荷夫提出的。他于1824年出生于普魯士的哥尼斯堡。年出生于普魯士的哥尼斯堡。1845年因宣布著名的克年因宣布著名的克希荷夫電流電壓定律而聞名，希荷夫電流電壓定律而聞名，1847年大學(xué)畢業(yè)時(shí)發(fā)表了生年大學(xué)畢業(yè)時(shí)發(fā)表了生成樹(shù)計(jì)數(shù)文章，給出了矩陣樹(shù)定理。他的一生主要花在實(shí)成樹(shù)計(jì)數(shù)文章，給出了矩陣樹(shù)定理。他的一生主要花在實(shí)驗(yàn)物理上。擔(dān)任過(guò)德國(guó)柏林?jǐn)?shù)學(xué)物理會(huì)主席職務(wù)。驗(yàn)物理上。擔(dān)任過(guò)德國(guó)柏林?jǐn)?shù)學(xué)物理會(huì)主席職務(wù)。 0.8 1 0.6 0.4 0.2 0

14、x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 16(2) 矩陣樹(shù)定理的證明很復(fù)雜，在此略去證明；矩陣樹(shù)定理的證明很復(fù)雜，在此略去證明；(3) 定理中的矩陣定理中的矩陣C又稱為圖的拉普拉斯矩陣，又可定又稱為圖的拉普拉斯矩陣，又可定義為：義為：()()CD GA G其中，其中，D(G)是圖的度對(duì)角矩陣，即主對(duì)角元為對(duì)應(yīng)頂是圖的度對(duì)角矩陣，即主對(duì)角元為對(duì)應(yīng)頂點(diǎn)度數(shù)，其余元素為點(diǎn)度數(shù)，其余元素為0。A(G)是圖的鄰接矩陣。是圖的鄰接矩陣。 圖的拉普拉斯矩陣特征值問(wèn)題是代數(shù)圖論或組合矩圖的拉普拉斯矩陣特征值問(wèn)題是代數(shù)圖論或組合矩陣?yán)碚摰闹饕芯繉?duì)象之一。該問(wèn)題因?yàn)樵趫D論、計(jì)算陣?yán)碚?/p>

15、的主要研究對(duì)象之一。該問(wèn)題因?yàn)樵趫D論、計(jì)算機(jī)科學(xué)、流體力學(xué)、量子化學(xué)和生物醫(yī)學(xué)中的重要應(yīng)用機(jī)科學(xué)、流體力學(xué)、量子化學(xué)和生物醫(yī)學(xué)中的重要應(yīng)用而受到學(xué)者們的高度重視。研究方法大致有而受到學(xué)者們的高度重視。研究方法大致有3種：代數(shù)種：代數(shù)方法、幾何方法和概率方法。方法、幾何方法和概率方法。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 17例例3 利用矩陣樹(shù)定理求下圖生成樹(shù)的棵數(shù)。利用矩陣樹(shù)定理求下圖生成樹(shù)的棵數(shù)。v4v1v2v3解：圖的拉氏矩陣為：解：圖的拉氏矩陣為：2110121011310011C一行一列對(duì)應(yīng)的余子式為：一行一列對(duì)應(yīng)

16、的余子式為：1 1210( 1)1310113 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 18例例4 證明證明(K(Kn n)=n)=nn-2n-2( (教材上定理教材上定理7 7）證明：容易寫出證明：容易寫出Kn的拉氏矩陣為：的拉氏矩陣為：一行一列對(duì)應(yīng)的余子式為：一行一列對(duì)應(yīng)的余子式為：111111()111nnnC Kn1 1111111( 1)111nnn所以：所以：2()nnKn 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 19注：例注：例4的證明有好幾種不

17、同方法。用矩陣樹(shù)定理證明是的證明有好幾種不同方法。用矩陣樹(shù)定理證明是最簡(jiǎn)單的方法。最簡(jiǎn)單的方法。1967年，加拿大的年，加拿大的Moon用了用了10種不同方種不同方法證明，之后有人給出了更多證明方法。法證明，之后有人給出了更多證明方法。 Moon的學(xué)術(shù)生涯主要是對(duì)樹(shù)和有向圖問(wèn)題進(jìn)行研究。的學(xué)術(shù)生涯主要是對(duì)樹(shù)和有向圖問(wèn)題進(jìn)行研究。同時(shí)，正如大多數(shù)科學(xué)家一樣，他對(duì)音樂(lè)也很感興趣。他同時(shí)，正如大多數(shù)科學(xué)家一樣，他對(duì)音樂(lè)也很感興趣。他還認(rèn)為：當(dāng)一個(gè)人發(fā)現(xiàn)了新事物，而且很難對(duì)非數(shù)學(xué)工作還認(rèn)為：當(dāng)一個(gè)人發(fā)現(xiàn)了新事物，而且很難對(duì)非數(shù)學(xué)工作者解釋該發(fā)現(xiàn)時(shí)，他就會(huì)產(chǎn)生一種滿足喜悅感。者解釋該發(fā)現(xiàn)時(shí)，他就會(huì)產(chǎn)生一

18、種滿足喜悅感。例例5 證明：若證明：若e為為Kn的一條邊，則：的一條邊，則：3()(2)nnKenn證法一：若證法一：若e為為Kn的一條邊，由的一條邊，由Kn中的邊的對(duì)稱性以及中的邊的對(duì)稱性以及每棵生成樹(shù)的邊數(shù)為每棵生成樹(shù)的邊數(shù)為n-1，由例，由例4，Kn的所有生成樹(shù)的總的所有生成樹(shù)的總邊數(shù)為：邊數(shù)為： 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 20所以，每條邊所對(duì)應(yīng)的生成樹(shù)的棵數(shù)為：所以，每條邊所對(duì)應(yīng)的生成樹(shù)的棵數(shù)為：2(1)nnn所以，所以，K n - e 對(duì)應(yīng)的生成樹(shù)的棵數(shù)為：對(duì)應(yīng)的生成樹(shù)的棵數(shù)為：23(1)21(1)2n

19、nnnnn n233()2(2)nnnnKennnn證法二：假設(shè)在證法二：假設(shè)在Kn中去掉的邊中去掉的邊e=v1vn, 則則Kn-e的拉氏矩陣的拉氏矩陣為：為： 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 21于是由矩陣樹(shù)定理：于是由矩陣樹(shù)定理：210111012nnCn11111111()11111112nnnKenn11111110111111101111111 011111111nnnnnnn 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 22232nnnn32n

20、nn(三三)、環(huán)路系統(tǒng)簡(jiǎn)介、環(huán)路系統(tǒng)簡(jiǎn)介定義定義4 設(shè)設(shè)T是連通圖是連通圖G的一棵生成樹(shù)，把屬于的一棵生成樹(shù)，把屬于G但不屬于但不屬于T的邊稱為的邊稱為G關(guān)于關(guān)于T的連枝，的連枝，T中的邊稱為中的邊稱為G關(guān)于關(guān)于T的樹(shù)枝。的樹(shù)枝。 在上圖中，紅色邊導(dǎo)出圖的一棵生成樹(shù)。則紅色邊為在上圖中，紅色邊導(dǎo)出圖的一棵生成樹(shù)。則紅色邊為G對(duì)對(duì)應(yīng)于該生成樹(shù)的樹(shù)枝，白色邊為應(yīng)于該生成樹(shù)的樹(shù)枝，白色邊為G對(duì)應(yīng)于該生成樹(shù)的連枝。對(duì)應(yīng)于該生成樹(shù)的連枝。G 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 23定義定義5 設(shè)設(shè)T是連通圖是連通圖G的一棵生成樹(shù)，由

21、的一棵生成樹(shù)，由G的對(duì)應(yīng)于的對(duì)應(yīng)于T一條連一條連枝與枝與T中樹(shù)枝構(gòu)成的唯一圈中樹(shù)枝構(gòu)成的唯一圈C，稱為，稱為G關(guān)于關(guān)于T的一個(gè)基本圈或的一個(gè)基本圈或基本回路。若基本回路。若G是是(n, m)連通圖，把連通圖，把G對(duì)應(yīng)于對(duì)應(yīng)于T的的m-n+1個(gè)基本個(gè)基本回路稱為回路稱為G對(duì)應(yīng)于對(duì)應(yīng)于T的基本回路組。記為的基本回路組。記為C f .abcdeGaceT基本回路為：基本回路為：abcC1cdeC2 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 24基本回路的性質(zhì)基本回路的性質(zhì):定理定理4 設(shè)設(shè)T是連通圖是連通圖G=(n, m) 的一棵生成

22、樹(shù)的一棵生成樹(shù),C1, C2,Cm-n+1是是G對(duì)應(yīng)于對(duì)應(yīng)于T的基本回路組。定義：的基本回路組。定義：1.Gi=Gi , 0.Gi=,G,Gi i是是G G的回的回路。則路。則G G的環(huán)路組的環(huán)路組( (閉跡閉跡) )作成的集合對(duì)于該乘法和圖的對(duì)稱差作成的集合對(duì)于該乘法和圖的對(duì)稱差運(yùn)算來(lái)說(shuō)作成數(shù)域運(yùn)算來(lái)說(shuō)作成數(shù)域F=F=0,1上的上的m-n+1維向量空間。維向量空間。證明證明: (1) 非空、兩閉、非空、兩閉、8條容易證明。條容易證明。(2) 首先證明首先證明C1, C2,Cm-n+1線性無(wú)關(guān)。線性無(wú)關(guān)。若不然，設(shè)若不然，設(shè)C1, C2,Cm-n+1線性相關(guān)，那么存在一組不全為線性相關(guān)，那么存

23、在一組不全為零的數(shù)零的數(shù)a1,a2,am-n+1,使得：使得：112211mnmna Ca CaC 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 25但是，任意兩個(gè)基本回路包含兩條不同連枝，所以，若某個(gè)但是，任意兩個(gè)基本回路包含兩條不同連枝，所以，若某個(gè)ak0, 則則112211mnm na Ca CaC 矛盾！矛盾！其次證明其次證明G的任意一個(gè)環(huán)路均可由的任意一個(gè)環(huán)路均可由C1, C2,Cm-n+1線性表出。線性表出。設(shè)設(shè)B是是G的任一環(huán)路，顯然，它至少含一條連枝，不失一般性，的任一環(huán)路，顯然，它至少含一條連枝，不失一般性，令：令

24、：121,jjkiiiiiBeeeee其中：其中：121,jjkiiiiieeeee為連枝，為樹(shù)枝 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 26令：令：1212,jjiiiiiieeeCCC又設(shè)包含連枝的基本回路為121jiiiBCCC顯然，顯然，B1中只含有中只含有B中連枝，于是中連枝，于是BB B1 1只含樹(shù)枝不含連枝。只含樹(shù)枝不含連枝。但是，可以證明：兩個(gè)不同環(huán)路的環(huán)和一定是回路。因此但是，可以證明：兩個(gè)不同環(huán)路的環(huán)和一定是回路。因此BB1中只含樹(shù)枝不含連枝是不可能的。中只含樹(shù)枝不含連枝是不可能的。定理定理4說(shuō)明，連通圖說(shuō)明，連通圖G的所有環(huán)路作成子圖空間的一個(gè)子空間，的所有環(huán)路作成子圖空間的一個(gè)子空間，該空間稱為環(huán)路空間或環(huán)路系統(tǒng)。該空間稱為環(huán)路空間或環(huán)路系統(tǒng)。例例6 求下圖求下圖G的環(huán)路空間的一個(gè)基底和它的全部元素。的環(huán)路空間的一個(gè)基底和它的全部元素。所以：所以： ，得，得 。 1BB 1