電子科大圖論 楊春8

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)容(一一)、生成樹的概念與性質(zhì)、生成樹的概念與性質(zhì)(二二)、生成樹的計數(shù)、生成樹的計數(shù)(三三)、回路系統(tǒng)簡介、回路系統(tǒng)簡介 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、生成樹的概念、生成樹的

2、概念(一一)、生成樹的概念與性質(zhì)、生成樹的概念與性質(zhì)定義定義1 圖圖G的一個生成子圖的一個生成子圖T如果是樹，稱它為如果是樹，稱它為G的一棵的一棵生成樹；若生成樹；若T為森林，稱它為為森林，稱它為G的一個生成森林。的一個生成森林。生成樹的邊稱為樹枝，生成樹的邊稱為樹枝，G中非生成樹的邊稱為弦。中非生成樹的邊稱為弦。例如：例如：粗邊構(gòu)成的子圖為粗邊構(gòu)成的子圖為G的生成樹。的生成樹。圖圖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、生成樹的性質(zhì)、生成樹的性質(zhì)定理定理1 每個連通圖至少包含一棵生成樹。每個連通圖至少包含一棵生成樹

3、。證明：如果連通圖證明：如果連通圖G是樹，則其本身是一棵生成樹；是樹，則其本身是一棵生成樹；若連通圖若連通圖G中有圈中有圈C，則去掉，則去掉C中一條邊后得到的圖仍中一條邊后得到的圖仍然是連通的，這樣不斷去掉然是連通的，這樣不斷去掉G中圈，最后得到一個中圈，最后得到一個G的的無圈連通子圖無圈連通子圖T，它為，它為G的一棵生成樹。的一棵生成樹。 定理定理1的證明實際上給出了連通圖的證明實際上給出了連通圖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ù)1、凱萊遞推計數(shù)法、凱萊遞推計數(shù)法 凱萊凱萊(Cayley 18211895): 劍橋大學(xué)數(shù)學(xué)教授，著名劍橋大學(xué)數(shù)學(xué)教授，著名代數(shù)學(xué)家，發(fā)表論文數(shù)僅次于代數(shù)學(xué)家，發(fā)表論文數(shù)僅次于Erdos ,Euler, Cauchy. 著著名成果是名成果是1854年定義了抽象群，并且得到著名定理：任年定義了抽象群，并且得到著名定理：任意一個群都和一個變換群同構(gòu)。同時，他也是

5、一名出色意一個群都和一個變換群同構(gòu)。同時，他也是一名出色的律師，作律師的律師，作律師14年期間，發(fā)表年期間，發(fā)表200多篇數(shù)學(xué)論文，著多篇數(shù)學(xué)論文，著名定理也是在該期間發(fā)表的。名定理也是在該期間發(fā)表的。 凱萊生成樹遞推計數(shù)公式是他在凱萊生成樹遞推計數(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.ee1e5e2e4e3用用(G)(G)表示表示G

6、 G的生成樹棵數(shù)。的生成樹棵數(shù)。定理定理2(Cayley) 設(shè)設(shè)e是是G的一條邊，則有：的一條邊，則有：()()()GGeG e證明：對于證明：對于G的一條邊的一條邊e來說，來說，G的生成樹中包含邊的生成樹中包含邊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ù)。共共8棵生成樹?？蒙蓸洹?0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0

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

8、的那些邊構(gòu)的列的那些邊構(gòu)成成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 9 該定理給出了求連通圖該定理給出了求連通圖G的所有生成樹的方法：的所有生成樹的方法： (1) 寫出寫出G的關(guān)聯(lián)矩陣，進一步寫出基本關(guān)聯(lián)矩陣，的關(guān)聯(lián)矩陣，進一步寫出基本關(guān)聯(lián)矩陣，記住參考點；記住參考點； (2) 找出基本關(guān)聯(lián)矩陣的非奇異主子陣，對每個這樣找出基本關(guān)聯(lián)矩陣的非奇異主子陣，對每個這樣的主子陣，畫出相應(yīng)的生成樹。的主子陣，畫出相應(yīng)的生成樹。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5

9、 1 1.5 2 1 0.5 0 0.5 1 n 10例例2，畫出下圖，畫出下圖G的所有不同的生成樹。的所有不同的生成樹。1234abcdeG解：取解：取4為參考點，為參考點，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個主子陣，非奇異主子陣個主子陣，非奇異主子陣8個，它們是：個，它們是：1234abd1110011001Aabd1232110010001Aabe1231234abe 0.8 1 0.6 0.4 0.2 0 x

10、 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 147100110001Abce1238100110011Abde1231234bce1234bde注：該方法的優(yōu)

11、點是不僅指出生成樹棵數(shù)，而且能繪注：該方法的優(yōu)點是不僅指出生成樹棵數(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 15定理定理3 (矩陣樹定理矩陣樹定理) 設(shè)設(shè)G是頂點集合為是頂點集合為V(G)=v1,v2,vn,的圖，設(shè)的圖，設(shè)A=(aij)是是G的鄰接矩陣，的鄰接矩陣，C=(cij)是是n階方陣，其中：階方陣，其中：3、矩陣樹定理、矩陣樹定理(),iijijd vijcaij則則G的生成樹棵數(shù)為的生成樹棵數(shù)為C

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

13、 2 1 0.5 0 0.5 1 n 16(2) 矩陣樹定理的證明很復(fù)雜，在此略去證明；矩陣樹定理的證明很復(fù)雜，在此略去證明；(3) 定理中的矩陣定理中的矩陣C又稱為圖的拉普拉斯矩陣，又可定又稱為圖的拉普拉斯矩陣，又可定義為：義為：()()CD GA G其中，其中，D(G)是圖的度對角矩陣，即主對角元為對應(yīng)頂是圖的度對角矩陣，即主對角元為對應(yīng)頂點度數(shù)，其余元素為點度數(shù)，其余元素為0。A(G)是圖的鄰接矩陣。是圖的鄰接矩陣。 圖的拉普拉斯矩陣特征值問題是代數(shù)圖論或組合矩圖的拉普拉斯矩陣特征值問題是代數(shù)圖論或組合矩陣理論的主要研究對象之一。該問題因為在圖論、計算陣理論的主要研究對象之一。該問題因為

14、在圖論、計算機科學(xué)、流體力學(xué)、量子化學(xué)和生物醫(yī)學(xué)中的重要應(yīng)用機科學(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ù)。v4v1v2v3解：圖的拉氏矩陣為：解：圖的拉氏矩陣為：2110121011310011C一行一列對應(yīng)的余子式為：一行一列對應(yīng)的余子式為：1 1210( 1

15、)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的拉氏矩陣為：的拉氏矩陣為：一行一列對應(yīng)的余子式為：一行一列對應(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的證明有好幾種不同方法。用矩陣樹定理證明是的證

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

17、證明：若e為為Kn的一條邊，則：的一條邊，則：3()(2)nnKenn證法一：若證法一：若e為為Kn的一條邊，由的一條邊，由Kn中的邊的對稱性以及每中的邊的對稱性以及每棵生成樹的邊數(shù)為棵生成樹的邊數(shù)為n-1，Kn的所有生成樹的總邊數(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所以，每條邊所對應(yīng)的生成樹的棵數(shù)為：所以，每條邊所對應(yīng)的生成樹的棵數(shù)為：2(1)nnn所以，所以，K n - e 對應(yīng)的生成樹的棵數(shù)為：對應(yīng)的生成樹的棵數(shù)為：23(1)21(1)2nnnnnn n233()2(2)nnnnKe

18、nnnn證法二：假設(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于是由矩陣樹定理：于是由矩陣樹定理：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 22232nnnn32nnn(三三)、回路系統(tǒng)簡介、回路系統(tǒng)簡介定義

19、定義4 設(shè)設(shè)T是連通圖是連通圖G的一棵生成樹，把屬于的一棵生成樹，把屬于G但不屬于但不屬于T的邊稱為的邊稱為G關(guān)于關(guān)于T的連枝，的連枝，T中的邊稱為中的邊稱為G關(guān)于關(guān)于T的樹枝。的樹枝。 在上圖中，紅色邊導(dǎo)出圖的一棵生成樹。則紅色邊為在上圖中，紅色邊導(dǎo)出圖的一棵生成樹。則紅色邊為G對對應(yīng)于該生成樹的樹枝，白色邊為應(yīng)于該生成樹的樹枝，白色邊為G對應(yīng)于該生成樹的連枝。對應(yīng)于該生成樹的連枝。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的一棵生成樹，由的一棵生成樹，由G的對應(yīng)于的對應(yīng)于T一條連一

20、條連枝與枝與T中樹枝構(gòu)成的唯一圈中樹枝構(gòu)成的唯一圈C，稱為，稱為G關(guān)于關(guān)于T的一個基本圈或的一個基本圈或基本回路。若基本回路。若G是是(n, m)連通圖，把連通圖，把G對應(yīng)于對應(yīng)于T的的m-n+1個基本個基本回路稱為回路稱為G對應(yīng)于對應(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) 的一棵生成樹的一棵生成樹,C1, C2,Cm-n+1是

21、是G對應(yīng)于對應(yīng)于T的基本回路組。定義：的基本回路組。定義：1.Gi=Gi , 0.Gi=,G,Gi i是是G G的回的回路。則路。則G G的回路組作成的集合對于該乘法和圖的對稱差運算來的回路組作成的集合對于該乘法和圖的對稱差運算來說作成數(shù)域說作成數(shù)域F=F=0,1上的上的m-n+1維向量空間。基本回路組是維向量空間?；净芈方M是該空間的一組基。該空間的一組基。證明證明: 略。略。定理定理4說明，連通圖說明，連通圖G的所有回路作成子圖空間的一個子空間，的所有回路作成子圖空間的一個子空間，該空間稱為回路空間或回路系統(tǒng)。該空間稱為回路空間或回路系統(tǒng)。 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的一棵生成樹的一棵生成樹T為：為：GabcdefghabdgTG對于生成樹對于生成樹T的基本回路為：的基本回路為：1, ,Ca b c2, ,Ca b d e3, ,