




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
3.3支撐樹的計(jì)數(shù)Th3.2.1有向圖G的關(guān)聯(lián)矩陣B的秩<n證明由于矩陣B的每列表示每邊的起點(diǎn)與終點(diǎn),起點(diǎn)處為1,終點(diǎn)為-1.
將所有行加起來填到n行,則第n行為0,即最后一行=-(前n-1行和).故獨(dú)立行數(shù)即B的秩<n.
Th3.2.2設(shè)S是有向圖的關(guān)聯(lián)矩陣B任一k階方陣,則Det(S)=0,1或-1.Th3.2.3n點(diǎn)連通圖G之關(guān)聯(lián)矩陣的秩為n-1。
證:假設(shè)線性相關(guān)的最少行數(shù)為L(zhǎng)<n出錯(cuò)
定理3.2.4
連通圖基本關(guān)聯(lián)矩陣Bk的秩n-1。定理3.2.5
C是連通圖G的一個(gè)回路,Bk是G的一個(gè)基本關(guān)聯(lián)矩陣,那么回路C中各點(diǎn)與各邊對(duì)應(yīng)Bk的列線性相關(guān).
定理3.2.6
令Bk是有向連通圖G的基本關(guān)聯(lián)矩陣,那么Bk的某n-1階子陣行列式非0的是其各列所對(duì)應(yīng)的邊構(gòu)成G的支撐樹.證明.
某個(gè)N-1階子陣Bk(GT)的行列式非0這n-1列線性無關(guān)這n-1邊線性無關(guān),由推理3.2.2可知這n-1條邊中不含回路(若有回路則線性相關(guān)),由樹的定義可知不成回路的n-1條邊構(gòu)成一棵樹,即為支撐樹。3.3.1有向連通圖的樹計(jì)數(shù)定理3.3.1(Binet-Cauchy)已知兩個(gè)矩陣Am×n,Bn×m,滿足mn,
則|AB|=∑|Ai||Bi|
其Ai與Bi都是m階子式,Ai是從A中取m列,Bi是B中的相應(yīng)m行即Ai的原列號(hào)=Bi的原行號(hào),然后再對(duì)全部組合求和。畫示意圖可較好解決樹的計(jì)數(shù)1234e1e2e3e4e5B4與BT4乘積及比-柯定理驗(yàn)證如下等式。|BkBTk
|=∑|Bi||BTi|=∑|Bi|2。
123124125134135145234235245345××√√√√√√√√
定理3.3.2
設(shè)Bk是有向連通圖G的基本關(guān)聯(lián)矩陣,則G的生成樹棵數(shù)為|BkBkT|,|Bi|≠0子式數(shù).
證明:Bk行數(shù)為n-1,列數(shù)=邊數(shù)=m,由G是連通圖,其邊數(shù)至少為n-1(最摳的連通圖樹的邊為n-1)
故n-1m,而BTk為m(n-1),滿足比-柯條件
由比-柯定理可知|BkBkT
|=∑|Bi||BiT|
因?yàn)閨BiT
|=|Bi|,故|Bi||BiT|=|Bi|2,故|BkBkT
|=∑|Bi|2
由Th3.2.6可知|Bi|≠0Bi各列為生成樹,
由Th3.2.2可知|Bi|的值為1或-1,因此|Bi|2=1
故|Bi|2=1Bi各列對(duì)應(yīng)一棵生成樹故∑|Bi|2為生成樹的棵數(shù)故|BkBkT
|為生成樹的棵數(shù)1234e1e2e3e4e5B4是去掉關(guān)聯(lián)矩陣第4行后得到的,n-1=3,它共有C(5,3)=C(5,2)=10個(gè)3階方陣,分別是123124125134135145234235245345××√√√√√√√√1234e1e2e3e4e5子式難數(shù),直接求|B4B4T
|=8,知它有8棵樹,哪8棵呢?抽出e4還有幾棵樹?就是B4少了第4列。
123列124列134列234列1234e1e2e3e4e5必含有e3的樹是:12312412513413514523423524534501√√√√√1234e1e2e3e4e5必須含有e3的樹:共有8棵樹,先從關(guān)聯(lián)矩陣中抽出e3邊(不含e3邊的樹),然后8-該數(shù)123124125134135145234235245345××√√√√√√√√總結(jié):計(jì)算|BkBTk|,先算BkBTk
計(jì)算C=BkBkT的簡(jiǎn)便方法:
當(dāng)i=j(主對(duì)角線),Cij=d(i)該點(diǎn)度數(shù)=Bk第Vi行中非零元的數(shù)目;
當(dāng)i≠j,Cij=若圖中有形如(Vi,Vj)或(Vj,Vi)形式的邊,則為-1。1234e1e2e3e4e5V1V2V3V1V2V31234e1e2e3e4e5少了e4總結(jié):BkBkT中主對(duì)角線c(i,i)=Bk的i行BTk的i列=Bk的i行
i行=i行非0元素的個(gè)數(shù)=度數(shù)。1234e1e2e3e4e5123123e1e2e3e5e1e5123ijC(i,j)=Bki行BTkj列=Bk的i行j行=2行對(duì)應(yīng)位置1,-1=-1,點(diǎn)i與j之間最多1條邊。3.3.2無向連通圖的樹計(jì)數(shù)
注意:
無向連通圖同樣有其支撐樹,但是它的關(guān)聯(lián)矩陣B中不存在-1元素,因此不能直接采用比-柯定理進(jìn)行樹的計(jì)算。解決方法:
給無向連通圖G的每邊任給一方向,得到一個(gè)連通有向圖G’,G’與G具有相同的生成樹,故對(duì)G’的所得到的生成樹與G相同。例3.3.5求完全圖Kn中不同樹的數(shù)目解:
完全圖是任何兩點(diǎn)之間均有邊,給每邊一個(gè)方向后便成有向圖,按照前述計(jì)算C=det(BkBkT)的簡(jiǎn)便方法,C(1,1)=C(2,2)=…=C(n-1,n-1)=n-1,因?yàn)槊總€(gè)點(diǎn)與其它n-1鄰接.C(1,2)=C(2,1)….C(i,j)=…=-1(i≠j),這些點(diǎn)之間的邊只有一條,故:(n-1)(n-1)例3.3.5求完全圖Kn中不同樹的數(shù)目=n-1-(n-2)=nn-2(n-1)(n-1)試n=3,43.3.3有向連通圖G根樹的計(jì)數(shù)定義3.3.1T有向樹,若T中存在某結(jié)點(diǎn)V0的入度(負(fù)度)為0,其余結(jié)點(diǎn)的負(fù)度(入度)為1,則稱T是以V0為根的外向樹,或稱根樹.
V4V0V1V2V3e2e1e3e4去掉樹根所在行得B0性質(zhì):10后|B0|仍為1總結(jié):
由于入度(負(fù)度)為0的根所在行被去掉了,而其它點(diǎn)的入度均為1。故B0的每一行只有一個(gè)-1(作為終點(diǎn)),但可能有多個(gè)+1(該點(diǎn)作為起點(diǎn)指向子結(jié)點(diǎn)).
而每邊只有一個(gè)終點(diǎn)與起點(diǎn),故B0每列最多只有一個(gè)+1.V4V0V1V2V3e2e1e3e4v1v2e4v3v4e1e2e3重新對(duì)結(jié)點(diǎn)編號(hào):
起點(diǎn)編號(hào)<終點(diǎn)編號(hào),并且每邊的終點(diǎn)編號(hào)與該邊號(hào)相同,如e1的終點(diǎn)V1,
e2的終點(diǎn)是V2,…,這樣B0的左下角全為0,|B0|=(-1)n-1=V2V0V1V3V4e2e1e3e4e1e2e3e4V1V2V3V4即使將頂行的1全變成0或其它元素,行列式的值保持不變,這是根樹的性質(zhì)。|B0i|=|BiT|0
反過來,若將某個(gè)基本關(guān)聯(lián)矩陣中的1變成0,其行列式的值仍保持不變,則它肯定為某個(gè)根樹的關(guān)聯(lián)矩陣。根樹基本關(guān)聯(lián)行列值不變!V2V0V1V3V4e2e1e3e4下面的B0,|B0|=1B0中的1全換成0,則|B00|=1,V4V0V1V2V3e2e1e3e4
Th3.3.3有向連通圖G中以Vk為根的根樹數(shù)目是|B0kBkT|.
證明:B0k是將Bk的所有1換成0而得到,由比-柯定理可知:|B0kBkT|=∑|B0i||BiT||BiT|0這n-1條邊構(gòu)成一棵樹
|B0i|=|BiT|0這n-1條邊構(gòu)成1棵根樹,
|B0i|=|BiT|0|B0i||BiT|=1|B0i||BiT|=1這n-1條邊構(gòu)成1棵根樹∑|B0i||BiT|=根樹數(shù)|B0kBkT|=根樹的棵數(shù)。例3.3.6求下圖以V1為根的根樹數(shù)目V1V2V4V3e1e2e3e4e5e6例3.3.7求以V1為根不含e5的根樹數(shù)V1V2V4V3e1e2e3e4e5e6例3.3.8求以V1為根必含e5的根樹數(shù)V1V2V4V3e1e2e3e4e5e6因?yàn)橐訴1為根的根樹有6棵,不含e5的有4
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 臺(tái)州市中醫(yī)院景福公司招聘真題2024
- 平安銀行佛山分行招聘真題2024
- 化學(xué)部門:挑戰(zhàn)與突破
- 孩子們的快樂課堂
- 2025至2030年中國(guó)鱉甲煎丸市場(chǎng)分析及競(jìng)爭(zhēng)策略研究報(bào)告
- 2025至2030年中國(guó)真空銀杯市場(chǎng)調(diào)查研究報(bào)告
- 2025至2030年中國(guó)溶劑綠數(shù)據(jù)監(jiān)測(cè)研究報(bào)告
- 2025至2030年中國(guó)柔白亮澤面膜霜數(shù)據(jù)監(jiān)測(cè)研究報(bào)告
- 2025至2030年中國(guó)接線端子陶瓷市場(chǎng)分析及競(jìng)爭(zhēng)策略研究報(bào)告
- 2025至2030年中國(guó)變徑管件市場(chǎng)調(diào)查研究報(bào)告
- 有機(jī)合成中的合成子課件
- 混凝土澆筑技術(shù)交底全
- 數(shù)學(xué)建模的介紹教學(xué)課件
- 邏輯代數(shù)的基本定律和規(guī)則課件
- 【短視頻質(zhì)量對(duì)消費(fèi)者購(gòu)買行為的影響研究4300字(論文)】
- 茄子課件完整版
- 戰(zhàn)地衛(wèi)生與救護(hù)教案-模板
- 《中華民族大團(tuán)結(jié)》(初中) 第1課 愛我中華 教案
- 蘇科版五年級(jí)下冊(cè)勞動(dòng)第10課《便攜衣架》課件
- 2023年浙江農(nóng)林大學(xué)博士入學(xué)考試英語
- 沖孔灌注樁澆注砼技術(shù)交底記錄
評(píng)論
0/150
提交評(píng)論