1、1,Email: ,圖論及其應(yīng)用,任課教師：楊春,數(shù)學(xué)科學(xué)學(xué)院,2,本次課主要內(nèi)容,(一)、生成樹的概念與性質(zhì),(二)、生成樹的計(jì)數(shù),(三)、回路系統(tǒng)簡介,3,1、生成樹的概念,(一)、生成樹的概念與性質(zhì),定義1 圖G的一個(gè)生成子圖T如果是樹，稱它為G的一棵生成樹；若T為森林，稱它為G的一個(gè)生成森林。,生成樹的邊稱為樹枝，G中非生成樹的邊稱為弦。,例如：,粗邊構(gòu)成的子圖為G的生成樹。,4,2、生成樹的性質(zhì),定理1 每個(gè)連通圖至少包含一棵生成樹。,證明：如果連通圖G是樹，則其本身是一棵生成樹；,若連通圖G中有圈C，則去掉C中一條邊后得到的圖仍然是連通的，這樣不斷去掉G中圈，最后得到一個(gè)G的無圈連

2、通子圖T，它為G的一棵生成樹。,定理1的證明實(shí)際上給出了連通圖G的生成樹的求法，該方法稱為破圈法。,利用破圈法，顯然也可以求出任意圖的一個(gè)生成森林。,5,推論 若G是(n, m)連通圖，則mn-1,連通圖G的生成樹一般不唯一！,(二)、生成樹的計(jì)數(shù),1、凱萊遞推計(jì)數(shù)法,凱萊(Cayley 18211895): 劍橋大學(xué)數(shù)學(xué)教授，著名代數(shù)學(xué)家，發(fā)表論文數(shù)僅次于Erdos ,Euler, Cauchy. 著名成果是1854年定義了抽象群，并且得到著名定理：任意一個(gè)群都和一個(gè)變換群同構(gòu)。同時(shí)，他也是一名出色的律師，作律師14年期間，發(fā)表200多篇數(shù)學(xué)論文，著名定理也是在該期間發(fā)表的。,凱萊生成樹遞推

3、計(jì)數(shù)公式是他在1889年建立的。,6,定義2 圖G的邊e稱為被收縮，是指刪掉e后，把e的兩個(gè)端點(diǎn)重合，如此得到的圖記為G.e,用(G)表示G的生成樹棵數(shù)。,定理2(Cayley) 設(shè)e是G的一條邊，則有：,證明：對于G的一條邊e來說，G的生成樹中包含邊e的棵數(shù)為(G.e )，而不包含e的棵數(shù)為 (G-e).,7,例1，利用凱萊遞推法求下圖生成樹的棵數(shù)。,共8棵生成樹。,8,凱萊公式的缺點(diǎn)之一是計(jì)算量很大，其次是不能具體指出每棵生成樹。,2、關(guān)聯(lián)矩陣計(jì)數(shù)法,定義3 ：nm矩陣的一個(gè)階數(shù)為minn, m的子方陣，稱為它的一個(gè)主子陣；主子陣的行列式稱為主子行列式。,顯然，當(dāng)nm時(shí)，nm矩陣 個(gè)主子陣

4、。,定理3 設(shè)Am是連通圖G的基本關(guān)聯(lián)矩陣的主子陣，則Am非奇異的充分必要條件是相應(yīng)于Am的列的那些邊構(gòu)成G的一棵生成樹。,證明：略。,9,該定理給出了求連通圖G的所有生成樹的方法：,(1) 寫出G的關(guān)聯(lián)矩陣，進(jìn)一步寫出基本關(guān)聯(lián)矩陣，記住參考點(diǎn)；,(2) 找出基本關(guān)聯(lián)矩陣的非奇異主子陣，對每個(gè)這樣的主子陣，畫出相應(yīng)的生成樹。,10,例2，畫出下圖G的所有不同的生成樹。,解：取4為參考點(diǎn)，G的基本關(guān)聯(lián)矩陣為：,11,共有10個(gè)主子陣，非奇異主子陣8個(gè)，它們是：,12,13,14,注：該方法的優(yōu)點(diǎn)是不僅指出生成樹棵數(shù)，而且能繪出所有不同生成樹；缺點(diǎn)是找所有非奇異主子陣計(jì)算量太大！,15,定理3 (

5、矩陣樹定理) 設(shè)G是頂點(diǎn)集合為V(G)=v1,v2,vn,的圖，設(shè)A=(aij)是G的鄰接矩陣，C=(cij)是n階方陣，其中：,3、矩陣樹定理,則G的生成樹棵數(shù)為C的任意一個(gè)余子式的值。,說明：(1) 該定理是由物理學(xué)家克希荷夫提出的。他于1824年出生于普魯士的哥尼斯堡。1845年因宣布著名的克希荷夫電流電壓定律而聞名，1847年大學(xué)畢業(yè)時(shí)發(fā)表了生成樹計(jì)數(shù)文章，給出了矩陣樹定理。他的一生主要花在實(shí)驗(yàn)物理上。擔(dān)任過德國柏林?jǐn)?shù)學(xué)物理會(huì)主席職務(wù)。,16,(2) 矩陣樹定理的證明很復(fù)雜，在此略去證明；,(3) 定理中的矩陣C又稱為圖的拉普拉斯矩陣，又可定義為：,其中，D(G)是圖的度對角矩陣，即主

6、對角元為對應(yīng)頂點(diǎn)度數(shù)，其余元素為0。A(G)是圖的鄰接矩陣。,圖的拉普拉斯矩陣特征值問題是代數(shù)圖論或組合矩陣?yán)碚摰闹饕芯繉ο笾弧Ｔ搯栴}因?yàn)樵趫D論、計(jì)算機(jī)科學(xué)、流體力學(xué)、量子化學(xué)和生物醫(yī)學(xué)中的重要應(yīng)用而受到學(xué)者們的高度重視。研究方法大致有3種：代數(shù)方法、幾何方法和概率方法。,17,例3 利用矩陣樹定理求下圖生成樹的棵數(shù)。,解：圖的拉氏矩陣為：,一行一列對應(yīng)的余子式為：,18,例4 證明(Kn)=nn-2(教材上定理7）,證明：容易寫出Kn的拉氏矩陣為：,一行一列對應(yīng)的余子式為：,所以：,19,注：例4的證明有好幾種不同方法。用矩陣樹定理證明是最簡單的方法。1967年，加拿大的Moon用了10

7、種不同方法證明，之后有人給出了更多證明方法。,Moon的學(xué)術(shù)生涯主要是對樹和有向圖問題進(jìn)行研究。同時(shí)，正如大多數(shù)科學(xué)家一樣，他對音樂也很感興趣。他還認(rèn)為：當(dāng)一個(gè)人發(fā)現(xiàn)了新事物，而且很難對非數(shù)學(xué)工作者解釋該發(fā)現(xiàn)時(shí)，他就會(huì)產(chǎn)生一種滿足喜悅感。,例5 證明：若e為Kn的一條邊，則：,證法一：若e為Kn的一條邊，由Kn中的邊的對稱性以及每棵生成樹的邊數(shù)為n-1，Kn的所有生成樹的總邊數(shù)為：,20,所以，每條邊所對應(yīng)的生成樹的棵數(shù)為：,所以，K n - e 對應(yīng)的生成樹的棵數(shù)為：,證法二：假設(shè)在Kn中去掉的邊e=v1vn, 則Kn-e的拉氏矩陣為：,21,于是由矩陣樹定理：,22,(三)、回路系統(tǒng)簡介,

8、定義4 設(shè)T是連通圖G的一棵生成樹，把屬于G但不屬于T的邊稱為G關(guān)于T的連枝，T中的邊稱為G關(guān)于T的樹枝。,在上圖中，紅色邊導(dǎo)出圖的一棵生成樹。則紅色邊為G對應(yīng)于該生成樹的樹枝，白色邊為G對應(yīng)于該生成樹的連枝。,23,定義5 設(shè)T是連通圖G的一棵生成樹，由G的對應(yīng)于T一條連枝與T中樹枝構(gòu)成的唯一圈C，稱為G關(guān)于T的一個(gè)基本圈或基本回路。若G是(n, m)連通圖，把G對應(yīng)于T的m-n+1個(gè)基本回路稱為G對應(yīng)于T的基本回路組。記為C f .,基本回路為：,24,基本回路的性質(zhì):,定理4 設(shè)T是連通圖G=(n, m) 的一棵生成樹,C1, C2,Cm-n+1是G對應(yīng)于T的基本回路組。定義：1.Gi=Gi , 0.Gi=,Gi是G的回路。則G的回路組作成的集合對于該乘法和圖的對稱差運(yùn)算來說作成數(shù)域F=0,1上的m-n+1維向量空間?；净芈方M是該空間的一組基。,證明: 略。,定理4說明，連通圖G的所有回路作成子圖空間的一個(gè)子空間，該空間稱為回路空