算法合集之生成树的计数及其应用PPT学习教案.pptx

会计学
1
算法合集之生成树的计数及其应用
引入
最小（大）生成树
最小（大）度限制生成树
最优比率生成树
……
生成树
生成树的计数
第1页/共31页
[例一]高速公路
一个国家需要在n座城市之间建立通信网络。
某些城市之间可以铺设通信线路。
要求任意两座城市之间恰好有一条通讯路线，试求方案个数。
满足：1≤n ≤12。
第2页/共31页
分析
首先将问题抽象成图论模型
点：城市
边：通讯线路
任意两点之间恰好只有一条路径
这是一颗树！
问题转化为：给定一个n个点的无向图，其中无重边和自环，试求其生成树的个数。
第3页/共31页
分析
由于原题规模较小，因此我们可以使用一些复杂度较高的算法来解决它，如指数级的动态规划算法。
但是，如果规模更 一些呢？
预备知识
关联矩阵、Kirchhoff矩阵
大
第4页/共31页
图的关联矩阵
对于无向图G，我们定义它的关联矩阵B是一个n*m的矩阵，并且满足：
如果ek=(vi，vj)，那么Bik和Bjk一个为1，另一个为-1，而第k列的其他元素均为0。
图G的关联矩阵如右下角所示：
v1
v2
v3
图G
e1
e2
e3
v1
v2
v3
e1 e2 e3
第5页/共31页
图的关联矩阵
图的关联矩阵有什么特殊的性质呢？我们不妨来考察一下B和它的转置矩阵BT的乘积。
第6页/共31页
图的关联矩阵
根据矩阵乘法的定义，我们可以得到：
也就是说，BBTij是B第i行和第j行的内积。
因此，当i=j时， BBTij=vi的度数；而当i≠j时，如果存在边(vi，vj)，那么BBTij=-1，否则BBTij=0。
我们通常将BBT称为图的Kirchhoff矩阵。
第7页/共31页
图的Kirchhoff矩阵
对于无向图G，它的Kirchhoff矩阵C定义为它的度数矩阵D减去它的邻接矩阵A。显然，这样的定义满足刚才描述的性质。
有了Kirchhoff矩阵这个工具，我们可以引入Matrix-Tree定理：
对于一个无向图G，它的生成树个数等于其Kirchhoff矩阵任何一个n-1阶主子式的行列式的绝对值。
所谓n-1阶主子式，就是对于任意一个r，将C的第r行和第r列同时删去后的新矩阵，用Cr表示。
第8页/共31页
Matrix-Tree定理
让我们通过一个例子来解释一下定理。如图所示，G是一个由5个点组成的无向图。
它的Kirchhoff矩阵C为
第9页/共31页