圖論及其應(yīng)用8ppt課件

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 : yc517922126 圖論及其運(yùn)用任課教師：楊春任課教師：楊春數(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 本次課主要內(nèi)容本次課主要內(nèi)容(一一)、生成樹的概念與性質(zhì)、生成樹的概念與性質(zhì)(二二)、生成樹的計(jì)數(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 1、生成樹的概念、生成樹的概念

2、(一一)、生成樹的概念與性質(zhì)、生成樹的概念與性質(zhì)定義定義1 圖圖G的一個(gè)生成子圖的一個(gè)生成子圖T假設(shè)是樹，稱它為假設(shè)是樹，稱它為G的一棵的一棵生成樹；假設(shè)生成樹；假設(shè)T為森林，稱它為為森林，稱它為G的一個(gè)生成森林。的一個(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 2、生成樹的性質(zhì)、生成樹的性質(zhì)定理定理1 每個(gè)連通圖至少包含一棵生成樹。每個(gè)連通圖至少包含一棵生成樹。

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

4、 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 推論推論 假設(shè)假設(shè)G是是(n, m)連通圖，那么連通圖，那么mn-1連通圖連通圖G的生成樹普通不獨(dú)一！的生成樹普通不獨(dú)一！(二二)、生成樹的計(jì)數(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年定義了籠統(tǒng)群，并且得到著名定理：恣年定義了籠統(tǒng)群，并且得到著名定理：恣意一個(gè)群都和一個(gè)變換群同構(gòu)。同

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

6、G的生成樹棵數(shù)。的生成樹棵數(shù)。定理定理2(Cayley) 設(shè)設(shè)e是是G的一條邊，那么有：的一條邊，那么有：()()()GGeG e證明：對(duì)于證明：對(duì)于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 例例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.5 0

7、0.5 1 n 凱萊公式的缺陷之一是計(jì)算量很大，其次是不能詳凱萊公式的缺陷之一是計(jì)算量很大，其次是不能詳細(xì)指出每棵生成樹。細(xì)指出每棵生成樹。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的列的那些的列

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 設(shè)設(shè)Am是是Af的一個(gè)非奇特主子陣，并設(shè)與的一個(gè)非奇特主子陣，并設(shè)與Am的列相的列相對(duì)應(yīng)的邊構(gòu)成對(duì)應(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連通。這闡明連通。這闡明Gm是是n個(gè)點(diǎn)，個(gè)點(diǎn)，n-1條邊的條邊的連通圖，所以

9、，它是樹。連通圖，所以，它是樹。充分性充分性 假設(shè)假設(shè)Am的列對(duì)應(yīng)的邊作成的列對(duì)應(yīng)的邊作成G的一棵生成樹，因樹是連通的一棵生成樹，因樹是連通的，所以，它對(duì)應(yīng)的根本關(guān)聯(lián)矩陣的，所以，它對(duì)應(yīng)的根本關(guān)聯(lián)矩陣Am非奇特。非奇特。 該定理給出了求連通圖該定理給出了求連通圖G的一切生成樹的方法：的一切生成樹的方法： (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 (2) 找出根本關(guān)聯(lián)矩陣的非奇特主子陣，對(duì)每個(gè)這樣找出根本關(guān)聯(lián)矩陣的非

10、奇特主子陣，對(duì)每個(gè)這樣的主子陣，畫出相應(yīng)的生成樹。的主子陣，畫出相應(yīng)的生成樹。例例2，畫出以下圖，畫出以下圖G的一切不同的生成樹。的一切不同的生成樹。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 共有共有10個(gè)主子陣，非奇特主子陣個(gè)主子陣，非奇特主子陣8個(gè)，它們是：個(gè)，它們是：1234abd1110011001Aabd1232110010001Aabe1231234abe 0.8 1 0.6

11、 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 3100011001Aacd1234100010001Aace1231234acd1234ace 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 5100010011Aade1236100111001Abcd1233124ade1234bcd 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 7100110001Abce1238100110011Abde1231234bce1234bde注

12、：該方法的優(yōu)點(diǎn)是不僅指出生成樹棵數(shù)，而且能繪注：該方法的優(yōu)點(diǎn)是不僅指出生成樹棵數(shù)，而且能繪出一切不同生成樹；缺陷是找一切非奇特主子陣計(jì)算出一切不同生成樹；缺陷是找一切非奇特主子陣計(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 定理定理3 (矩陣樹定理矩陣樹定理) 設(shè)設(shè)G是頂點(diǎn)集合為是頂點(diǎn)集合為V(G)=v1,v2,vn,的圖，設(shè)的圖，設(shè)A=(aij)是是G的鄰接矩陣，的鄰接矩陣，C=(cij)是是n階方陣，其中：階方陣，其中：3、矩陣樹定理、矩陣樹定理(),iijijd vijcaij那么那么G的生成樹棵數(shù)為的生

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

14、 1 1.5 2 1 0.5 0 0.5 1 n (2) 矩陣樹定理的證明很復(fù)雜，在此略去證明；矩陣樹定理的證明很復(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)是圖的鄰接矩陣。是圖的鄰接矩陣。 圖的拉普拉斯矩陣特征值問題是代數(shù)圖論或組合矩圖的拉普拉斯矩陣特征值問題是代數(shù)圖論或組合矩陣實(shí)際的主要研討對(duì)象之一。該問題由于在圖論、計(jì)算陣實(shí)際的主要研討對(duì)象之一。該

15、問題由于在圖論、計(jì)算機(jī)科學(xué)、流膂力學(xué)、量子化學(xué)和生物醫(yī)學(xué)中的重要運(yùn)用機(jī)科學(xué)、流膂力學(xué)、量子化學(xué)和生物醫(yī)學(xué)中的重要運(yùn)用而遭到學(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 例例3 利用矩陣樹定理求以下圖生成樹的棵數(shù)。利用矩陣樹定理求以下圖生成樹的棵數(shù)。v4v1v2v3解：圖的拉氏矩陣為：解：圖的拉氏矩陣為：2110121011310011C一行一列對(duì)應(yīng)的余子式為：一行一列對(duì)應(yīng)的余子式為：1 121

16、0( 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 例例4 證明證明(Kn)=nn-2(教材上定理教材上定理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 注：例注：例4的證明有好幾種不同方法。用矩陣樹定理證明是的證明有好幾種不同方法。用矩陣樹定

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

18、，那么：的一條邊，那么：3()(2)nnKenn證法一：假設(shè)證法一：假設(shè)e為為Kn的一條邊，由的一條邊，由Kn中的邊的對(duì)稱性以中的邊的對(duì)稱性以及每棵生成樹的邊數(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 所以，每條邊所對(duì)應(yīng)的生成樹的棵數(shù)為：所以，每條邊所對(duì)應(yīng)的生成樹的棵數(shù)為：2(1)nnn所以，所以，K n - e 對(duì)應(yīng)的生成樹的棵數(shù)為：對(duì)應(yīng)的生成樹的棵數(shù)為：23(1)21(1)2nnnnnn n233()2(2)nnnnKennnn證法二：假設(shè)在

19、證法二：假設(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 于是由矩陣樹定理：于是由矩陣樹定理：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 232nnnn32nnn(三三)、回路系統(tǒng)簡(jiǎn)介、回路系統(tǒng)簡(jiǎn)介定義定義4 設(shè)設(shè)T是連通圖是連

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

21、獨(dú)一圈中樹枝構(gòu)成的獨(dú)一圈C，稱為，稱為G關(guān)于關(guān)于T的一個(gè)根本圈或的一個(gè)根本圈或根本回路。假設(shè)根本回路。假設(shè)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 根本回路的性質(zhì)根本回路的性質(zhì):定理定理4 設(shè)設(shè)T是連通圖是連通圖G=(n, m) 的一棵生成樹的一棵生成樹,C1, C2,Cm-n+1是是G對(duì)應(yīng)于對(duì)應(yīng)于T的根本回

22、路組。定義：的根本回路組。定義：1.Gi=Gi , 0.Gi=,Gi是是G的回路。那么的回路。那么G的回路組作成的集合對(duì)于該乘法和圖的對(duì)稱差的回路組作成的集合對(duì)于該乘法和圖的對(duì)稱差運(yùn)算來說作成數(shù)域運(yùn)算來說作成數(shù)域F=0,1上的上的m-n+1維向量空間。維向量空間。證明證明: (1) 非空、兩閉、非空、兩閉、8條容易證明。條容易證明。(2) 首先證明首先證明C1, C2,Cm-n+1線性無關(guān)。線性無關(guān)。假設(shè)不然，設(shè)假設(shè)不然，設(shè)C1, C2,Cm-n+1線性相關(guān)，那么存在一組不線性相關(guān)，那么存在一組不全為零的數(shù)全為零的數(shù)a1,a2,am-n+1,使得：使得：112211m nm na Ca CaC

23、 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 但是，恣意兩個(gè)根本回路包含兩條不同連枝，所以，假設(shè)某但是，恣意兩個(gè)根本回路包含兩條不同連枝，所以，假設(shè)某個(gè)個(gè)ak0, 那么那么112211mnm na Ca CaC 矛盾！矛盾！其次證明其次證明G的恣意一個(gè)回路均可由的恣意一個(gè)回路均可由C1, C2,Cm-n+1線性表線性表出。出。設(shè)設(shè)B是是G的任一回路，顯然，它至少含一條連枝，不失普通性，的任一回路，顯然，它至少含一條連枝，不失普通性，令：令：121,jjkiiiiiBeeeee其中：其中：121,jjkiiiiieeeee為連枝，為

24、樹枝 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 令：令：1212,jjiiiiiieeeCCC又設(shè)包含連枝的基本回路為121jiiiBCCC顯然，顯然，B1中只含有中只含有B中連枝，于是中連枝，于是BB1只含樹枝不含連枝。只含樹枝不含連枝。但是，可以證明：兩個(gè)回路的環(huán)和一定是回路。因此但是，可以證明：兩個(gè)回路的環(huán)和一定是回路。因此BB1中中只含樹枝不含連枝是不能夠的。只含樹枝不含連枝是不能夠的。定理定理4闡明，連通圖闡明，連通圖G的一切回路作成子圖空間的一個(gè)子空間，的一切回路作成子圖空間的一個(gè)子空間，該空間稱為回路空間或回路系統(tǒng)。該空間稱為回路空間或回路系統(tǒng)。例例6 求以下圖求以下圖G的回路空間的一個(gè)基底和它的全部元素。的回路空間的一個(gè)基底和它的全部元素。所以：所以： ，得，得 。