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

(1)寫出G的關(guān)聯(lián)矩陣，進一步寫出基本關(guān)聯(lián)矩陣，記住參考點；9第九頁，共三十二頁，編輯于2023年，星期二

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