支撑树的计数

3.3支撑树的计数Th3.2.1有向图G的关联矩阵B的秩<n证明由于矩阵B的每列表示每边的起点与终点,起点处为1,终点为-1.

将所有行加起来填到n行,则第n行为0,即最后一行=-(前n-1行和).故独立行数即B的秩<n.

Th3.2.2设S是有向图的关联矩阵B任一k阶方阵,则Det(S)=0,1或-1.Th3.2.3n点连通图G之关联矩阵的秩为n-1。

证:假设线性相关的最少行数为L<n出错

定理3.2.4

连通图基本关联矩阵Bk的秩n-1。定理3.2.5

C是连通图G的一个回路,Bk是G的一个基本关联矩阵,那么回路C中各点与各边对应Bk的列线性相关.

定理3.2.6

令Bk是有向连通图G的基本关联矩阵,那么Bk的某n-1阶子阵行列式非0的是其各列所对应的边构成G的支撑树.证明.

某个N-1阶子阵Bk(GT)的行列式非0这n-1列线性无关这n-1边线性无关，由推理3.2.2可知这n-1条边中不含回路(若有回路则线性相关)，由树的定义可知不成回路的n-1条边构成一棵树，即为支撑树。3.3.1有向连通图的树计数定理3.3.1(Binet-Cauchy)已知两个矩阵Am×n，Bn×m，满足mn，

则|AB|=∑|Ai||Bi|

其Ai与Bi都是m阶子式，Ai是从A中取m列，Bi是B中的相应m行即Ai的原列号=Bi的原行号，然后再对全部组合求和。画示意图可较好解决树的计数1234e1e2e3e4e5B4与BT4乘积及比-柯定理验证如下等式。|BkBTk

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

123124125134135145234235245345××√√√√√√√√

定理3.3.2

设Bk是有向连通图G的基本关联矩阵,则G的生成树棵数为|BkBkT|,|Bi|≠0子式数.

证明:Bk行数为n-1,列数=边数=m,由G是连通图，其边数至少为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为生成树的棵数故|BkBkT

|为生成树的棵数1234e1e2e3e4e5B4是去掉关联矩阵第4行后得到的,n-1=3,它共有C(5,3)=C(5,2)=10个3阶方阵,分别是123124125134135145234235245345××√√√√√√√√1234e1e2e3e4e5子式难数，直接求|B4B4T

|=8,知它有8棵树,哪8棵呢？抽出e4还有几棵树？就是B4少了第4列。

123列124列134列234列1234e1e2e3e4e5必含有e3的树是：12312412513413514523423524534501√√√√√1234e1e2e3e4e5必须含有e3的树：共有8棵树,先从关联矩阵中抽出e3边(不含e3边的树),然后8-该数123124125134135145234235245345××√√√√√√√√总结:计算|BkBTk|，先算BkBTk

计算C=BkBkT的简便方法:

当i=j(主对角线),Cij=d(i)该点度数=Bk第Vi行中非零元的数目;

当i≠j,Cij=若图中有形如(Vi,Vj)或(Vj,Vi)形式的边，则为-1。1234e1e2e3e4e5V1V2V3V1V2V31234e1e2e3e4e5少了e4总结:BkBkT中主对角线c(i,i)=Bk的i行BTk的i列=Bk的i行

i行=i行非0元素的个数=度数。1234e1e2e3e4e5123123e1e2e3e5e1e5123ijC(i,j)=Bki行BTkj列=Bk的i行j行=2行对应位置1,-1=-1,点i与j之间最多1条边。3.3.2无向连通图的树计数

注意:

无向连通图同样有其支撑树，但是它的关联矩阵B中不存在-1元素，因此不能直接采用比-柯定理进行树的计算。解决方法:

给无向连通图G的每边任给一方向，得到一个连通有向图G’,G’与G具有相同的生成树，故对G’的所得到的生成树与G相同。例3.3.5求完全图Kn中不同树的数目解:

完全图是任何两点之间均有边,给每边一个方向后便成有向图,按照前述计算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中不同树的数目=n-1-(n-2)=nn-2(n-1)(n-1)试n=3,43.3.3有向连通图G根树的计数定义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

反过来，若将某个基本关联矩阵中的1变成0，其行列式的值仍保持不变，则它肯定为某个根树的关联矩阵。根树基本关联行列值不变！V2V0V1V3V4e2e1e3e4下面的B0，|B0|=1B0中的1全换成0，则|B00|=1，V4V0V1V2V3e2e1e3e4

Th3.3.3有向连通图G中以Vk为根的根树数目是|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|=根树数|B0kBkT|=根树的棵数。例3.3.6求下图以V1为根的根树数目V1V2V4V3e1e2e3e4e5e6例3.3.7求以V1为根不含e5的根树数V1V2V4V3e1e2e3e4e5e6例3.3.8求以V1为根必含e5的根树数V1V2V4V3e1e2e3e4e5e6因为以V1为根的根树有6棵，不含e5的有4