ppt8電子科大圖論上課ppt及復習總結楊春.ppt

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

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

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

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

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

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

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

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