電子科大 圖論上課及復習總結(jié) 楊春17

Email:

圖論及其應用任課教師：楊春數(shù)學科學學院1本次課主要內(nèi)容(一)、生成樹的概念與性質(zhì)(二)、生成樹的計數(shù)(三)、回路系統(tǒng)簡介21、生成樹的概念(一)、生成樹的概念與性質(zhì)定義1圖G的一個生成子圖T如果是樹，稱它為G的一棵生成樹；若T為森林，稱它為G的一個生成森林。生成樹的邊稱為樹枝，G中非生成樹的邊稱為弦。例如：粗邊構(gòu)成的子圖為G的生成樹。圖G32、生成樹的性質(zhì)定理1每個連通圖至少包含一棵生成樹。證明：如果連通圖G是樹，則其本身是一棵生成樹；若連通圖G中有圈C，則去掉C中一條邊后得到的圖仍然是連通的，這樣不斷去掉G中圈，最后得到一個G的無圈連通子圖T，它為G的一棵生成樹。定理1的證明實際上給出了連通圖G的生成樹的求法，該方法稱為破圈法。利用破圈法，顯然也可以求出任意圖的一個生成森林。4推論若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定義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例1，利用凱萊遞推法求下圖生成樹的棵數(shù)。共8棵生成樹。7凱萊公式的缺點之一是計算量很大，其次是不能具體指出每棵生成樹。2、關(guān)聯(lián)矩陣計數(shù)法定義3：n×m矩陣的一個階數(shù)為min｛n,m｝的子方陣，稱為它的一個主子陣；主子陣的行列式稱為主子行列式。顯然，當n<m時，n×m矩陣個主子陣。定理3設(shè)Am是連通圖G的基本關(guān)聯(lián)矩陣的主子陣，則Am非奇異的充分必要條件是相應于Am的列的那些邊構(gòu)成G的一棵生成樹。證明：略。8該定理給出了求連通圖G的所有生成樹的方法：

(1)寫出G的關(guān)聯(lián)矩陣，進一步寫出基本關(guān)聯(lián)矩陣，記住參考點；

(2)找出基本關(guān)聯(lián)矩陣的非奇異主子陣，對每個這樣的主子陣，畫出相應的生成樹。9例2，畫坐出下存圖G的所澡有不曠同的擊生成沖樹。1234abcdeG解：汪取4為參糖考點蕉，G的基大本關(guān)吃聯(lián)矩緣瑞陣為吃：abcde12310共有10個主鞠子陣深，非麻奇異芳主子疊陣8個，燦它們嗽是：1234abdabd123abe1231234abe11acd123ace1231234acd1234ace12ade123bcd1233124ade1234bcd13bce123bde1231234bce1234bde注：顛該方足法的霜優(yōu)點楊是不洪僅指栽出生箱成樹巴棵數(shù)糕，而符且能伙繪出液所有臂不同歷生成到樹；巾缺點存是找顆所有建非奇臉異主虹子陣冷計算服量太莫大！14定理3撿(矩陣銜樹定約理)設(shè)G是頂仍點集裹合為V(可G)堆=｛v1,v2,…驗,vn｝,的圖以，設(shè)A=頁(aij)是G的鄰吐接矩漫陣，C=奇(cij)是n階方顆陣，傘其中質(zhì)：3、矩揚陣樹你定理則G的生干成樹奴棵數(shù)森為C的任稻意一晴個余漏子式拐的值識。說明艘：(1掛)該定初理是逮由物斤理學珠家克旗希荷呈夫提姥出的農(nóng)。他忍于18遷24年出底生于乞普魯擱士的窯哥尼疾斯堡因。18胡45年因弓宣布遙著名閉的克催希荷倦夫電膽流電靜壓定客律而掛聞名繁，18功47年大席學畢絹業(yè)時著發(fā)表深了生膛成樹窄計數(shù)鉛文章孤，給都出了葵矩陣構(gòu)樹定響理。諷他的熊一生濁主要嗎花在獲實驗熟物理盟上。透擔任五過德遭國柏勺林數(shù)胡學物踏理會梳主席云職務怒。15(2功)矩陣半樹定開理的且證明鹿很復漁雜，啟在此貿(mào)略去冷證明覆；(3樓)定理津中的少矩陣C又稱捎為圖咬的拉堂普拉疫斯矩怪陣，乎又可芽定義襯為：其中聾，D(際G)是圖訪的度站對角托矩陣排，即景主對墻角元摟為對快應頂置點度南數(shù)，僚其余痛元素餅為0。A(沸G)是圖瘡的鄰喘接矩汗陣。圖的首拉普鈔拉斯樣矩陣步特征淡值問扯題是釣代數(shù)傳圖論若或組雪合矩晝陣理屑論的妙主要歡研究蹲對象厘之一頑。該戚問題親因為蔥在圖浮論、爺計算噸機科恨學、摸流體慌力學睛、量害子化余學和資生物襲醫(yī)學錫中的給重要挨應用思而受炒到學算者們旋的高書度重挎視。丟研究益方法擺大致天有3種：開代數(shù)桃方法醋、幾塑何方允法和危概率歲方法淋。16例3利用喇矩陣桿樹定北理求吐下圖寺生成謎樹的柿棵數(shù)疏。v4v1v2v3解：辦圖的續(xù)拉氏往矩陣塊為：一行竊一列蛙對應眠的余業(yè)子式圾為：17例4證明τ(Kn)=黃nn-勝2(教材離上定衛(wèi)理7）證明御：容屠易寫餐出Kn的拉著氏矩割陣為擾：一行液一列白對應頭的余耳子式機為：所以由：18注：卻例4的證殲明有堅好幾孟種不押同方避法。確用矩姨陣樹局定理避證明職是最樣簡單淚的方份法。19永67年，話加拿常大的Mo熱on用了10種不糧同方虹法證碰明，感之后驚有人散給出飽了更租多證喇明方桐法。Mo蜓on的學原術(shù)生和涯主脾要是寨對樹唐和有徒向圖膝問題春進行看研究敢。同蟻時，壓正如觸大多桑數(shù)科賤學家旋一樣裁，他炎對音惡樂也碑很感朋興趣乳。他擁還認利為：狐當一片個人炎發(fā)現(xiàn)爆了新暢事物欄，而銅且很柏難對兼非數(shù)怨學工蠢作者維解釋摧該發(fā)翅現(xiàn)時究，他墨就會擊產(chǎn)生浸一種爆滿足逼喜悅馬感。例5證明驕：若e為Kn的一馬條邊叼，則纖：證法釣一：雙若e為Kn的一畏條邊類，由Kn中的捕邊的咽對稱墻性以絞及每竹棵生雙成樹斃的邊明數(shù)為n-仁1，Kn的所勤有生兄成樹館的總仰邊數(shù)久為：19所以餅，每嚷條邊拋所對今應的字生成稀樹的鉛棵數(shù)艷為：所以予，Kn-捕e對應鋤的生座成樹哲的棵輸數(shù)為豈：證法映二：因假設(shè)下在Kn中去餡掉的怨邊e=浸v1vn,則Kn-e的拉傍氏矩敢陣為怒：20于是逢由矩質(zhì)陣樹霉定理修：21(三)、回描路系丸統(tǒng)簡慢介定義4設(shè)T是連巧通圖G的一軍棵生暢成樹驢，把鑼屬于G但不問屬于T的邊增稱為G關(guān)于T的連天枝，T中的滑邊稱記為G關(guān)于T的樹織枝。在上翅圖中離，紅打色邊碗導出周圖的故一棵勢生成演樹。扔則紅原色邊嗓為G對應池于該提生成障樹的乒樹枝饒，白超色邊宇為G對應傳于該終生成異樹的掘連枝披。G22定義5設(shè)T是連扯通圖G的一丘棵生紫成樹胃，由G的對椒應于T一條趟連枝伍與T中樹刃枝構(gòu)題成的崗唯一膽圈C，稱環(huán)為G關(guān)于T的一豆個基找本圈冬或基泛本回幣路。計若G是(n耽,濫m)連通糠圖，呈把G對應歡于T的m-已n+洗1個基根本回端路稱脖為G對應謊于T的基壩本回弓路組仇。記蓬為Cf.abcdeGaceT基本蠢回路批為：abcC1cdeC223基本娘回路坡的性抗質(zhì):定理4設(shè)T是連蝕通圖G=嚇(n社,沿m)的一該棵生顧成樹,C1,錄C2,…撫,Cm-艙n+般1是G對應奧于T的基算本回鵲路組斗。定設(shè)義：1.Gi=Gi,憲0.捕Gi=Φ,Gi是G的回性路。澤則G的回駐路組血作成裕的集棉合對渡于該納乘法已和圖領(lǐng)的對怠稱差哨運算者來說搏作成線數(shù)域F=｛0,掠1｝上的m-見n+涉1維向息量空魔間。齊基本笑回路布組是披該空礦間的雷一組棒基。證明:略。定理4說明衛(wèi)，連繁通圖G的所濕有回暢路作皇成子晚圖空喚間的紡一個聞子空各間，艱該空血間稱脾為回慎路空統(tǒng)間或華回路淘系統(tǒng)吉。24解：豎取G的一罰棵生屠成樹T為：GabcdefghabdgTG對于待生成島樹T的基不本回爽路為犁：例6求下徒圖G的回荷路空鴉間的魂一個師基底濱和它突的全俗部元呈素。25C1abc圖形銅為：C2abdeC