支撐樹的計數(shù)

3.3支撐樹的計數(shù)Th3.2.1有向圖G的關聯(lián)矩陣B的秩<n證明由于矩陣B的每列表示每邊的起點與終點,起點處為1,終點為-1.

將所有行加起來填到n行,則第n行為0,即最后一行=-(前n-1行和).故獨立行數(shù)即B的秩<n.

Th3.2.2設S是有向圖的關聯(lián)矩陣B任一k階方陣,則Det(S)=0,1或-1.Th3.2.3n點連通圖G之關聯(lián)矩陣的秩為n-1。

證:假設線性相關的最少行數(shù)為L<n出錯

定理3.2.4

連通圖基本關聯(lián)矩陣Bk的秩n-1。定理3.2.5

C是連通圖G的一個回路,Bk是G的一個基本關聯(lián)矩陣,那么回路C中各點與各邊對應Bk的列線性相關.

定理3.2.6

令Bk是有向連通圖G的基本關聯(lián)矩陣,那么Bk的某n-1階子陣行列式非0的是其各列所對應的邊構成G的支撐樹.證明.

某個N-1階子陣Bk(GT)的行列式非0這n-1列線性無關這n-1邊線性無關，由推理3.2.2可知這n-1條邊中不含回路(若有回路則線性相關)，由樹的定義可知不成回路的n-1條邊構成一棵樹，即為支撐樹。3.3.1有向連通圖的樹計數(shù)定理3.3.1(Binet-Cauchy)已知兩個矩陣Am×n，Bn×m，滿足mn，

則|AB|=∑|Ai||Bi|

其Ai與Bi都是m階子式，Ai是從A中取m列，Bi是B中的相應m行即Ai的原列號=Bi的原行號，然后再對全部組合求和。畫示意圖可較好解決樹的計數(shù)1234e1e2e3e4e5B4與BT4乘積及比-柯定理驗證如下等式。|BkBTk

|=∑|Bi||BTi|=∑|Bi|2。

123124125134135145234235245345××√√√√√√√√

定理3.3.2

設Bk是有向連通圖G的基本關聯(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|

因為|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各列對應一棵生成樹故∑|Bi|2為生成樹的棵數(shù)故|BkBkT

|為生成樹的棵數(shù)1234e1e2e3e4e5B4是去掉關聯(lián)矩陣第4行后得到的,n-1=3,它共有C(5,3)=C(5,2)=10個3階方陣,分別是123124125134135145234235245345××√√√√√√√√1234e1e2e3e4e5子式難數(shù)，直接求|B4B4T

|=8,知它有8棵樹,哪8棵呢？抽出e4還有幾棵樹？就是B4少了第4列。

123列124列134列234列1234e1e2e3e4e5必含有e3的樹是：12312412513413514523423524534501√√√√√1234e1e2e3e4e5必須含有e3的樹：共有8棵樹,先從關聯(lián)矩陣中抽出e3邊(不含e3邊的樹),然后8-該數(shù)123124125134135145234235245345××√√√√√√√√總結:計算|BkBTk|，先算BkBTk

計算C=BkBkT的簡便方法:

當i=j(主對角線),Cij=d(i)該點度數(shù)=Bk第Vi行中非零元的數(shù)目;

當i≠j,Cij=若圖中有形如(Vi,Vj)或(Vj,Vi)形式的邊，則為-1。1234e1e2e3e4e5V1V2V3V1V2V31234e1e2e3e4e5少了e4總結:BkBkT中主對角線c(i,i)=Bk的i行BTk的i列=Bk的i行

i行=i行非0元素的個數(shù)=度數(shù)。1234e1e2e3e4e5123123e1e2e3e5e1e5123ijC(i,j)=Bki行BTkj列=Bk的i行j行=2行對應位置1,-1=-1,點i與j之間最多1條邊。3.3.2無向連通圖的樹計數(shù)

注意:

無向連通圖同樣有其支撐樹，但是它的關聯(lián)矩陣B中不存在-1元素，因此不能直接采用比-柯定理進行樹的計算。解決方法:

給無向連通圖G的每邊任給一方向，得到一個連通有向圖G’,G’與G具有相同的生成樹，故對G’的所得到的生成樹與G相同。例3.3.5求完全圖Kn中不同樹的數(shù)目解:

完全圖是任何兩點之間均有邊,給每邊一個方向后便成有向圖,按照前述計算C=det(BkBkT)的簡便方法,C(1,1)=C(2,2)=…=C(n-1,n-1)=n-1,因為每個點與其它n-1鄰接.C(1,2)=C(2,1)….C(i,j)=…=-1(i≠j),這些點之間的邊只有一條,故:(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根樹的計數(shù)定義3.3.1T有向樹,若T中存在某結點V0的入度(負度)為0,其余結點的負度(入度)為1,則稱T是以V0為根的外向樹,或稱根樹.

V4V0V1V2V3e2e1e3e4去掉樹根所在行得B0性質:10后|B0|仍為1總結:

由于入度(負度)為0的根所在行被去掉了,而其它點的入度均為1。故B0的每一行只有一個-1(作為終點),但可能有多個+1(該點作為起點指向子結點).

而每邊只有一個終點與起點,故B0每列最多只有一個+1.V4V0V1V2V3e2e1e3e4v1v2e4v3v4e1e2e3重新對結點編號:

起點編號<終點編號，并且每邊的終點編號與該邊號相同,如e1的終點V1,

e2的終點是V2,…，這樣B0的左下角全為0，|B0|=(-1)n-1=V2V0V1V3V4e2e1e3e4e1e2e3e4V1V2V3V4即使將頂行的1全變成0或其它元素，行列式的值保持不變,這是根樹的性質。|B0i|=|BiT|0

反過來，若將某個基本關聯(lián)矩陣中的1變成0，其行列式的值仍保持不變，則它肯定為某個根樹的關聯(liá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條邊構成一棵樹

|B0i|=|BiT|0這n-1條邊構成1棵根樹，

|B0i|=|BiT|0|B0i||BiT|=1|B0i||BiT|=1這n-1條邊構成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因為以V1為根的根樹有6棵，不含e5的有4