圖論生成樹(shù)的概念與性質(zhì)課件

圖論及其應(yīng)用應(yīng)用數(shù)學(xué)學(xué)院1圖論及其應(yīng)用應(yīng)用數(shù)學(xué)學(xué)院1本次課主要內(nèi)容(一)、生成樹(shù)的概念與性質(zhì)(二)、生成樹(shù)的計(jì)數(shù)(三)、回路系統(tǒng)簡(jiǎn)介2本次課主要內(nèi)容(一)、生成樹(shù)的概念與性質(zhì)(二)、生成樹(shù)的計(jì)數(shù)1、生成樹(shù)的概念(一)、生成樹(shù)的概念與性質(zhì)定義1圖G的一個(gè)生成子圖T如果是樹(shù)，稱它為G的一棵生成樹(shù)；若T為森林，稱它為G的一個(gè)生成森林。生成樹(shù)的邊稱為樹(shù)枝，G中非生成樹(shù)的邊稱為弦。例如：粗邊構(gòu)成的子圖為G的生成樹(shù)。圖G31、生成樹(shù)的概念(一)、生成樹(shù)的概念與性質(zhì)定義1圖G的一個(gè)2、生成樹(shù)的性質(zhì)定理1每個(gè)連通圖至少包含一棵生成樹(shù)。證明：如果連通圖G是樹(shù)，則其本身是一棵生成樹(shù)；若連通圖G中有圈C，則去掉C中一條邊后得到的圖仍然是連通的，這樣不斷去掉G中圈，最后得到一個(gè)G的無(wú)圈連通子圖T，它為G的一棵生成樹(shù)。定理1的證明實(shí)際上給出了連通圖G的生成樹(shù)的求法，該方法稱為破圈法。利用破圈法，顯然也可以求出任意圖的一個(gè)生成森林。42、生成樹(shù)的性質(zhì)定理1每個(gè)連通圖至少包含一棵生成樹(shù)。證明：推論若G是(n,m)連通圖，則m≧n-1連通圖G的生成樹(shù)一般不唯一！(二)、生成樹(shù)的計(jì)數(shù)1、凱萊遞推計(jì)數(shù)法凱萊(Cayley1821—1895):劍橋大學(xué)數(shù)學(xué)教授，著名代數(shù)學(xué)家，發(fā)表論文數(shù)僅次于Erdos,Euler,Cauchy.著名成果是1854年定義了抽象群，并且得到著名定理：任意一個(gè)群都和一個(gè)變換群同構(gòu)。同時(shí)，他也是一名出色的律師，作律師14年期間，發(fā)表200多篇數(shù)學(xué)論文，著名定理也是在該期間發(fā)表的。凱萊生成樹(shù)遞推計(jì)數(shù)公式是他在1889年建立的。5推論若G是(n,m)連通圖，則m≧n-1連通圖G的生成樹(shù)定義2圖G的邊e稱為被收縮，是指刪掉e后，把e的兩個(gè)端點(diǎn)重合，如此得到的圖記為G.ee1e5e2e4e3用τ(G)表示G的生成樹(shù)棵數(shù)。定理2(Cayley)設(shè)e是G的一條邊，則有：證明：對(duì)于G的一條邊e來(lái)說(shuō)，G的生成樹(shù)中包含邊e的棵數(shù)為G.e，而不包含e的棵數(shù)為G-e.6定義2圖G的邊e稱為被收縮，是指刪掉e后，把e的兩個(gè)端點(diǎn)重例1，利用凱萊遞推法求下圖生成樹(shù)的棵數(shù)。共8棵生成樹(shù)。7例1，利用凱萊遞推法求下圖生成樹(shù)的棵數(shù)。共8棵生成樹(shù)。7凱萊公式的缺點(diǎn)之一是計(jì)算量很大，其次是不能具體指出每棵生成樹(shù)。2、關(guān)聯(lián)矩陣計(jì)數(shù)法定義3：n×m矩陣的一個(gè)階數(shù)為min｛n,m｝的子方陣，稱為它的一個(gè)主子陣；主子陣的行列式稱為主子行列式。顯然，n×m矩陣共有個(gè)主子陣。定理3設(shè)Am是連通圖G的基本關(guān)聯(lián)矩陣的主子陣，則Am非奇異的充分必要條件是相應(yīng)于Am的列的那些邊構(gòu)成G的一棵生成樹(shù)。證明：必要性8凱萊公式的缺點(diǎn)之一是計(jì)算量很大，其次是不能具體指設(shè)Am是Af的一個(gè)非奇異主子陣，并設(shè)與Am的列相對(duì)應(yīng)的邊構(gòu)成G的子圖Gm.由于Am有n-1行，故Gm應(yīng)該有n-1個(gè)頂點(diǎn)(包括參考點(diǎn));又Am有n-1列,所以Gm有n-1條邊。而Am非奇異，故Am的秩為n-1,即Gm連通。這說(shuō)明Gm是n個(gè)點(diǎn)，n-1條邊的連通圖，所以，它是樹(shù)。充分性如果Am的列對(duì)應(yīng)的邊作成G的一棵生成樹(shù)，因樹(shù)是連通的，所以，它對(duì)應(yīng)的基本關(guān)聯(lián)矩陣Am非奇異。該定理給出了求連通圖G的所有生成樹(shù)的方法：

(1)寫出G的關(guān)聯(lián)矩陣，進(jìn)一步寫出基本關(guān)聯(lián)矩陣，記住參考點(diǎn)；9設(shè)Am是Af的一個(gè)非奇異主子陣，并設(shè)與Am的列相對(duì)應(yīng)

(2)找出基本關(guān)聯(lián)矩陣的非奇異主子陣，對(duì)每個(gè)這樣的主子陣，畫出相應(yīng)的生成樹(shù)。例2，畫出下圖G的所有不同的生成樹(shù)。1234abcdeG解：取4為參考點(diǎn)，G的基本關(guān)聯(lián)矩陣為：abcde12310(2)找出基本關(guān)聯(lián)矩陣的非奇異主子陣，對(duì)每個(gè)這樣的共有10個(gè)主子陣，非奇異主子陣8個(gè)，它們是：1234abdabd123abe1231234abe11共有10個(gè)主子陣，非奇異主子陣8個(gè)，它們是：1234abdaacd123ace1231234acd1234ace12acd123ace1231234acd1234ace12ade123bcd1233124ade1234bcd13ade123bcd1233124ade1234bcd13ade123bde1231234bce1234bde注：該方法的優(yōu)點(diǎn)是不僅指出生成樹(shù)棵數(shù)，而且能繪出所有不同生成樹(shù)；缺點(diǎn)是找所有非奇異主子陣計(jì)算量太大！14ade123bde1231234bce1234bde注：該方定理3(矩陣樹(shù)定理)設(shè)G是頂點(diǎn)集合為V(G)=｛v1,v2,…,vn｝,的圖，設(shè)A=(aij)是G的鄰接矩陣，C=(cij)是n階方陣，其中：3、矩陣樹(shù)定理則G的生成樹(shù)棵數(shù)為C的任意一個(gè)余子式的值。說(shuō)明：(1)該定理是由物理學(xué)家克希荷夫提出的。他于1824年出生于普魯士的哥尼斯堡。1845年因宣布著名的克希荷夫電流電壓定律而聞名，1847年大學(xué)畢業(yè)時(shí)發(fā)表了生成樹(shù)計(jì)數(shù)文章，給出了矩陣樹(shù)定理。他的一生主要花在實(shí)驗(yàn)物理上。擔(dān)任過(guò)德國(guó)柏林?jǐn)?shù)學(xué)物理會(huì)主席職務(wù)。15定理3(矩陣樹(shù)定理)設(shè)G是頂點(diǎn)集合為V(G)=｛v1,v(2)矩陣樹(shù)定理的證明很復(fù)雜，在此略去證明；(3)定理中的矩陣C又稱為圖的拉普拉斯矩陣，又可定義為：其中，D(G)是圖的度對(duì)角矩陣，即主對(duì)角元為對(duì)應(yīng)頂點(diǎn)度數(shù)，其余元素為0。A(G)是圖的鄰接矩陣。圖的拉普拉斯矩陣特征值問(wèn)題是代數(shù)圖論或組合矩陣?yán)碚摰闹饕芯繉?duì)象之一。該問(wèn)題因?yàn)樵趫D論、計(jì)算機(jī)科學(xué)、流體力學(xué)、量子化學(xué)和生物醫(yī)學(xué)中的重要應(yīng)用而受到學(xué)者們的高度重視。研究方法大致有3種：代數(shù)方法、幾何方法和概率方法。16(2)矩陣樹(shù)定理的證明很復(fù)雜，在此略去證明；(3)定理例3利用矩陣樹(shù)定理求下圖生成樹(shù)的棵數(shù)。v4v1v2v3解：圖的拉氏矩陣為：一行一列對(duì)應(yīng)的余子式為：17例3利用矩陣樹(shù)定理求下圖生成樹(shù)的棵數(shù)。v4v1v2v3解：例4證明τ(Kn)=nn-2(教材上定理7）證明：容易寫出Kn的拉氏矩陣為：一行一列對(duì)應(yīng)的余子式為：所以：18例4證明τ(Kn)=nn-2(教材上定理7）證明：容易寫出注：例4的證明有好幾種不同方法。用矩陣樹(shù)定理證明是最簡(jiǎn)單的方法。1967年，加拿大的Moon用了10種不同方法證明，之后有人給出了更多證明方法。Moon的學(xué)術(shù)生涯主要是對(duì)樹(shù)和有向圖問(wèn)題進(jìn)行研究。同時(shí)，正如大多數(shù)科學(xué)家一樣，他對(duì)音樂(lè)也很感興趣。他還認(rèn)為：當(dāng)一個(gè)人發(fā)現(xiàn)了新事物，而且很難對(duì)非數(shù)學(xué)工作者解釋該發(fā)現(xiàn)時(shí)，他就會(huì)產(chǎn)生一種滿足喜悅感。例5證明：若e為Kn的一條邊，則：證法一：若e為Kn的一條邊，由Kn中的邊的對(duì)稱性以及每棵生成樹(shù)的邊數(shù)為n-1，Kn的所有生成樹(shù)的總邊數(shù)為：19注：例4的證明有好幾種不同方法。用矩陣樹(shù)定理證明是最簡(jiǎn)單的方所以，每條邊所對(duì)應(yīng)的生成樹(shù)的棵數(shù)為：所以，Kn-e對(duì)應(yīng)的生成樹(shù)的棵數(shù)為：證法二：假設(shè)在Kn中去掉的邊e=v1vn,則Kn-e的拉氏矩陣為：20所以，每條邊所對(duì)應(yīng)的生成樹(shù)的棵數(shù)為：所以，Kn-e對(duì)于是由矩陣樹(shù)定理：21于是由矩陣樹(shù)定理：21(三)、回路系統(tǒng)簡(jiǎn)介定義4設(shè)T是連通圖G的一棵生成樹(shù)，把屬于G但不屬于T的邊稱為G關(guān)于T的連枝，T中的邊稱為G關(guān)于T的樹(shù)枝。在上圖中，紅色邊導(dǎo)出圖的一棵生成樹(shù)。則紅色邊為G對(duì)應(yīng)于該生成樹(shù)的樹(shù)枝，白色邊為G對(duì)應(yīng)于該生成樹(shù)的連枝。G22(三)、回路系統(tǒng)簡(jiǎn)介定義4設(shè)T是連通圖G的一棵生成樹(shù)，把屬定義5設(shè)T是連通圖G的一棵生成樹(shù)，由G的對(duì)應(yīng)于T一條連枝與T中樹(shù)枝構(gòu)成的唯一圈C，稱為G關(guān)于T的一個(gè)基本圈或基本回路。若G是(n,m)連通圖，把G對(duì)應(yīng)于T的n-m+1個(gè)基本回路稱為G對(duì)應(yīng)于T的基本回路組。記為Cf.abcdeGaceT基本回路為：abcC1cdeC223定義5設(shè)T是連通圖G的一棵生成樹(shù)，由G的對(duì)應(yīng)于T一條連枝與基本回路的性質(zhì):定理4設(shè)T是連通圖G=(n,m)的一棵生成樹(shù),C1,C2,…,Cn-m+1是G對(duì)應(yīng)于T的基本回路組。定義：1.Gi=Gi,0.Gi=Φ,Gi是G的回路。則G的回路組作成的集合對(duì)于該乘法和圖的對(duì)稱差運(yùn)算來(lái)說(shuō)作成數(shù)域F=｛0,1｝上的n-m+1維向量空間。證明:(1)非空、兩閉、8條容易證明。(2)首先證明C1,C2,…,Cn-m+1線性無(wú)關(guān)。若不然，設(shè)C1,C2,…,Cn-m+1線性相關(guān)，那么存在一組不全為零的數(shù)a1,a2,…,an-m+1,使得：24基本回路的性質(zhì):定理4設(shè)T是連通圖G=(n,m)的一棵但是，任意兩個(gè)基本回路包含兩條不同連枝，所以，若某個(gè)ak≠0,則矛盾！其次證明G的任意一個(gè)回路均可由C1,C2,…,Cn-m+1線性表出。設(shè)B是G的任一回路，顯然，它至少含一條連枝，不失一般性，令：其中：25但是，任意兩個(gè)基本回路包含兩條不同連枝，所以，若某個(gè)ak≠0令：顯然，B1中只含有B中連枝，于是BΔB1只含樹(shù)枝不含回路。但是，兩個(gè)回路的環(huán)和一定是回路，這就導(dǎo)出矛盾！定理4說(shuō)明，連通圖G的所有回路作成子圖空間的一個(gè)子空間，該空間稱為回路空間或回路系統(tǒng)。例6求下圖G的回路空間的一個(gè)基底和它的全部元素。26令：顯然，B1中只含有B中連枝，于是BΔB1只含樹(shù)枝不含回路解：取G的一棵生成樹(shù)T為：GabcdefghabdgTG對(duì)于生成樹(shù)T的基本回路為：27解：取G的一棵生成樹(shù)T為：GabcdefghabdgTG對(duì)于C1abc圖形為：C2abdeC4dfgabdghC3所有可能的環(huán)和為：28C1abc圖形為：C2abdeC4dfgabdghC3所有可B1cdeB2cdghB3abcdfgB4eghB5abefg29B1cdeB2cdghB3abcdfgB4eghB5abefB6abfhB2abcdefhB2cefgB7abceghB2cfhB2defh30B6abfhB2abcdefhB2cefgB7abceghB

作業(yè)

P43習(xí)題2：12,14,1531作業(yè)P43習(xí)題2：12,14,1531ThankYou!32ThankYou!32

圖論及其應(yīng)用應(yīng)用數(shù)學(xué)學(xué)院33圖論及其應(yīng)用應(yīng)用數(shù)學(xué)學(xué)院1本次課主要內(nèi)容(一)、生成樹(shù)的概念與性質(zhì)(二)、生成樹(shù)的計(jì)數(shù)(三)、回路系統(tǒng)簡(jiǎn)介34本次課主要內(nèi)容(一)、生成樹(shù)的概念與性質(zhì)(二)、生成樹(shù)的計(jì)數(shù)1、生成樹(shù)的概念(一)、生成樹(shù)的概念與性質(zhì)定義1圖G的一個(gè)生成子圖T如果是樹(shù)，稱它為G的一棵生成樹(shù)；若T為森林，稱它為G的一個(gè)生成森林。生成樹(shù)的邊稱為樹(shù)枝，G中非生成樹(shù)的邊稱為弦。例如：粗邊構(gòu)成的子圖為G的生成樹(shù)。圖G351、生成樹(shù)的概念(一)、生成樹(shù)的概念與性質(zhì)定義1圖G的一個(gè)2、生成樹(shù)的性質(zhì)定理1每個(gè)連通圖至少包含一棵生成樹(shù)。證明：如果連通圖G是樹(shù)，則其本身是一棵生成樹(shù)；若連通圖G中有圈C，則去掉C中一條邊后得到的圖仍然是連通的，這樣不斷去掉G中圈，最后得到一個(gè)G的無(wú)圈連通子圖T，它為G的一棵生成樹(shù)。定理1的證明實(shí)際上給出了連通圖G的生成樹(shù)的求法，該方法稱為破圈法。利用破圈法，顯然也可以求出任意圖的一個(gè)生成森林。362、生成樹(shù)的性質(zhì)定理1每個(gè)連通圖至少包含一棵生成樹(shù)。證明：推論若G是(n,m)連通圖，則m≧n-1連通圖G的生成樹(shù)一般不唯一！(二)、生成樹(shù)的計(jì)數(shù)1、凱萊遞推計(jì)數(shù)法凱萊(Cayley1821—1895):劍橋大學(xué)數(shù)學(xué)教授，著名代數(shù)學(xué)家，發(fā)表論文數(shù)僅次于Erdos,Euler,Cauchy.著名成果是1854年定義了抽象群，并且得到著名定理：任意一個(gè)群都和一個(gè)變換群同構(gòu)。同時(shí)，他也是一名出色的律師，作律師14年期間，發(fā)表200多篇數(shù)學(xué)論文，著名定理也是在該期間發(fā)表的。凱萊生成樹(shù)遞推計(jì)數(shù)公式是他在1889年建立的。37推論若G是(n,m)連通圖，則m≧n-1連通圖G的生成樹(shù)定義2圖G的邊e稱為被收縮，是指刪掉e后，把e的兩個(gè)端點(diǎn)重合，如此得到的圖記為G.ee1e5e2e4e3用τ(G)表示G的生成樹(shù)棵數(shù)。定理2(Cayley)設(shè)e是G的一條邊，則有：證明：對(duì)于G的一條邊e來(lái)說(shuō)，G的生成樹(shù)中包含邊e的棵數(shù)為G.e，而不包含e的棵數(shù)為G-e.38定義2圖G的邊e稱為被收縮，是指刪掉e后，把e的兩個(gè)端點(diǎn)重例1，利用凱萊遞推法求下圖生成樹(shù)的棵數(shù)。共8棵生成樹(shù)。39例1，利用凱萊遞推法求下圖生成樹(shù)的棵數(shù)。共8棵生成樹(shù)。7凱萊公式的缺點(diǎn)之一是計(jì)算量很大，其次是不能具體指出每棵生成樹(shù)。2、關(guān)聯(lián)矩陣計(jì)數(shù)法定義3：n×m矩陣的一個(gè)階數(shù)為min｛n,m｝的子方陣，稱為它的一個(gè)主子陣；主子陣的行列式稱為主子行列式。顯然，n×m矩陣共有個(gè)主子陣。定理3設(shè)Am是連通圖G的基本關(guān)聯(lián)矩陣的主子陣，則Am非奇異的充分必要條件是相應(yīng)于Am的列的那些邊構(gòu)成G的一棵生成樹(shù)。證明：必要性40凱萊公式的缺點(diǎn)之一是計(jì)算量很大，其次是不能具體指設(shè)Am是Af的一個(gè)非奇異主子陣，并設(shè)與Am的列相對(duì)應(yīng)的邊構(gòu)成G的子圖Gm.由于Am有n-1行，故Gm應(yīng)該有n-1個(gè)頂點(diǎn)(包括參考點(diǎn));又Am有n-1列,所以Gm有n-1條邊。而Am非奇異，故Am的秩為n-1,即Gm連通。這說(shuō)明Gm是n個(gè)點(diǎn)，n-1條邊的連通圖，所以，它是樹(shù)。充分性如果Am的列對(duì)應(yīng)的邊作成G的一棵生成樹(shù)，因樹(shù)是連通的，所以，它對(duì)應(yīng)的基本關(guān)聯(lián)矩陣Am非奇異。該定理給出了求連通圖G的所有生成樹(shù)的方法：

(1)寫出G的關(guān)聯(lián)矩陣，進(jìn)一步寫出基本關(guān)聯(lián)矩陣，記住參考點(diǎn)；41設(shè)Am是Af的一個(gè)非奇異主子陣，并設(shè)與Am的列相對(duì)應(yīng)

(2)找出基本關(guān)聯(lián)矩陣的非奇異主子陣，對(duì)每個(gè)這樣的主子陣，畫出相應(yīng)的生成樹(shù)。例2，畫出下圖G的所有不同的生成樹(shù)。1234abcdeG解：取4為參考點(diǎn)，G的基本關(guān)聯(lián)矩陣為：abcde12342(2)找出基本關(guān)聯(lián)矩陣的非奇異主子陣，對(duì)每個(gè)這樣的共有10個(gè)主子陣，非奇異主子陣8個(gè)，它們是：1234abdabd123abe1231234abe43共有10個(gè)主子陣，非奇異主子陣8個(gè)，它們是：1234abdaacd123ace1231234acd1234ace44acd123ace1231234acd1234ace12ade123bcd1233124ade1234bcd45ade123bcd1233124ade1234bcd13ade123bde1231234bce1234bde注：該方法的優(yōu)點(diǎn)是不僅指出生成樹(shù)棵數(shù)，而且能繪出所有不同生成樹(shù)；缺點(diǎn)是找所有非奇異主子陣計(jì)算量太大！46ade123bde1231234bce1234bde注：該方定理3(矩陣樹(shù)定理)設(shè)G是頂點(diǎn)集合為V(G)=｛v1,v2,…,vn｝,的圖，設(shè)A=(aij)是G的鄰接矩陣，C=(cij)是n階方陣，其中：3、矩陣樹(shù)定理則G的生成樹(shù)棵數(shù)為C的任意一個(gè)余子式的值。說(shuō)明：(1)該定理是由物理學(xué)家克希荷夫提出的。他于1824年出生于普魯士的哥尼斯堡。1845年因宣布著名的克希荷夫電流電壓定律而聞名，1847年大學(xué)畢業(yè)時(shí)發(fā)表了生成樹(shù)計(jì)數(shù)文章，給出了矩陣樹(shù)定理。他的一生主要花在實(shí)驗(yàn)物理上。擔(dān)任過(guò)德國(guó)柏林?jǐn)?shù)學(xué)物理會(huì)主席職務(wù)。47定理3(矩陣樹(shù)定理)設(shè)G是頂點(diǎn)集合為V(G)=｛v1,v(2)矩陣樹(shù)定理的證明很復(fù)雜，在此略去證明；(3)定理中的矩陣C又稱為圖的拉普拉斯矩陣，又可定義為：其中，D(G)是圖的度對(duì)角矩陣，即主對(duì)角元為對(duì)應(yīng)頂點(diǎn)度數(shù)，其余元素為0。A(G)是圖的鄰接矩陣。圖的拉普拉斯矩陣特征值問(wèn)題是代數(shù)圖論或組合矩陣?yán)碚摰闹饕芯繉?duì)象之一。該問(wèn)題因?yàn)樵趫D論、計(jì)算機(jī)科學(xué)、流體力學(xué)、量子化學(xué)和生物醫(yī)學(xué)中的重要應(yīng)用而受到學(xué)者們的高度重視。研究方法大致有3種：代數(shù)方法、幾何方法和概率方法。48(2)矩陣樹(shù)定理的證明很復(fù)雜，在此略去證明；(3)定理例3利用矩陣樹(shù)定理求下圖生成樹(shù)的棵數(shù)。v4v1v2v3解：圖的拉氏矩陣為：一行一列對(duì)應(yīng)的余子式為：49例3利用矩陣樹(shù)定理求下圖生成樹(shù)的棵數(shù)。v4v1v2v3解：例4證明τ(Kn)=nn-2(教材上定理7）證明：容易寫出Kn的拉氏矩陣為：一行一列對(duì)應(yīng)的余子式為：所以：50例4證明τ(Kn)=nn-2(教材上定理7）證明：容易寫出注：例4的證明有好幾種不同方法。用矩陣樹(shù)定理證明是最簡(jiǎn)單的方法。1967年，加拿大的Moon用了10種不同方法證明，之后有人給出了更多證明方法。Moon的學(xué)術(shù)生涯主要是對(duì)樹(shù)和有向圖問(wèn)題進(jìn)行研究。同時(shí)，正如大多數(shù)科學(xué)家一樣，他對(duì)音樂(lè)也很感興趣。他還認(rèn)為：當(dāng)一個(gè)人發(fā)現(xiàn)了新事物，而且很難對(duì)非數(shù)學(xué)工作者解釋該發(fā)現(xiàn)時(shí)，他就會(huì)產(chǎn)生一種滿足喜悅感。例5證明：若e為Kn的一條邊，則：證法一：若e為Kn的一條邊，由Kn中的邊的對(duì)稱性以及每棵生成樹(shù)的邊數(shù)為n-1，Kn的所有生成樹(shù)的總邊數(shù)為：51注：例4的證明有好幾種不同方法。用矩陣樹(shù)定理證明是最簡(jiǎn)單的方所以，每條邊所對(duì)應(yīng)的生成樹(shù)的棵數(shù)為：所以，Kn-e對(duì)應(yīng)的生成樹(shù)的棵數(shù)為：證法二：假設(shè)在Kn中去掉的邊e=v1vn,則Kn-e的拉氏矩陣為：52所以，每條邊所對(duì)應(yīng)的生成樹(shù)的棵數(shù)為：所以，Kn-e對(duì)于是由矩陣樹(shù)定理：53于是由矩陣樹(shù)定理：21(三)、回路系統(tǒng)簡(jiǎn)介定義4設(shè)T是連通圖G的一棵生成樹(shù)，把屬于G但不屬于T的邊稱為G關(guān)于T的連枝，T中的邊稱為G關(guān)于T的樹(shù)枝。在上圖中，紅色邊導(dǎo)出圖的一棵生成樹(shù)。則紅色邊為G對(duì)應(yīng)于該生成樹(shù)的樹(shù)枝，白色邊為G對(duì)應(yīng)于該生成樹(shù)的連枝。G54(三)、回路系統(tǒng)簡(jiǎn)介定義4設(shè)T是連通圖G的一棵生成樹(shù)，把屬定義5設(shè)T是連通圖G的一棵生成樹(shù)，由G的對(duì)應(yīng)于T一條連枝與T中樹(shù)枝構(gòu)成的唯一圈C，稱為G關(guān)于T的一個(gè)基本圈或基本回路。若G是(n,m)連通圖，把G對(duì)應(yīng)于T的n-m+1個(gè)基本回路稱為G對(duì)應(yīng)于T的基本回路組。記為Cf.abcdeGaceT基本回路為：abcC1cdeC255定義5設(shè)T是連通圖G的一棵生成樹(shù)，由G的對(duì)應(yīng)于T一條連枝與基本回路的性質(zhì):定理4設(shè)T是連通圖G=(n,m)的一棵生成樹(shù),C1,C2,…,Cn-m+1是G對(duì)應(yīng)于T的基本回路組。定義：1.Gi=Gi,0.Gi=Φ,Gi是G的回路。則G的回路組作成的集合對(duì)于該乘法和圖的對(duì)稱差運(yùn)算來(lái)說(shuō)作成數(shù)域F=｛