[生成树计数]
prufer序列
每个prufer序列对应一棵唯一的树。
生成：得到一棵树的prufer序列的方法是依次去掉编号最小的叶子节点(也就是度数为1的点)，然后将这个点的父亲加入队列。直到剩下最后两个点。这样就可以得到一个长度为n的prufer序列。
根据prufer序列的生成方式可以得到：每个节点会在prufer序列中出现他的度数-1次
还原:找到一个包含编号为1-n这n个节点的集合S,然后每次在S中从小到大找到第一个不在prufer序列中的数，将这个数与序列的第一个节点连一条边，并且将序列中的节点作为父亲。然后将这两个节点同时从各自所在的序列或集合中删除，重复上面的操作n-2次。最后集合S中会剩下两个节点，将这两个节点连接起来。就可以将prufer序列还原了。
Cayley定理
完全图的生成树个数为\(n^{n-2}\)。利用prufer序列考虑，因为每个序列和一棵生成树是对应的，所以序列的个数其实就是生成树的个数。prufer序列有n-2个节点，每个节点都有n种选择。利用乘法原理就可以知道完全图的不同的prufer序列有\(n^{n-2}\)个。
计数
如果给定n个点并且限制这n个点的度数必须分别是\(d_1,d_2,d_3......d_n\),那么所能形成的生成树的个数是\(\frac{(n-2)!}{\prod\limits_{i=1}^n{(d_i-1)!}}\)。这个结论也可以根据prufer证明。因为每个节点在prufer中出现的次数是它的度数减一次。分母上(n-2)!的是全部的排列方式。因为对于节点i有\((d_i-1)!\)中排列方式是相同的，所以再去除以这些排列方式。
matrix-tree定理
不大会证明，所以直接写结论和做法吧。
首先要得到一个基尔霍夫矩阵(K)。然后还需要一个度数矩阵(D)和邻接矩阵(A),具体意义如下
度数矩阵，\(D_{i,i}\)为第i个点的度数，其他位置全部为0
邻接矩阵，\(A_{i,j}\)=\(A_{j,i}\)=i与j之间的边数
基尔霍夫矩阵，由D-A得到，就是\(K_{i,j}=D_{i,j}-A_{i,j}\)
上面三个矩阵都是N*N的矩阵，N表示点数
然后去掉K的最后一行和最后一列。然后用高斯消元求出这个新矩阵的上三角矩阵。将上三角矩阵对角线的点相乘所得到的绝对值就是这个图所能形成的树的个数。
合合信息公司福利 236人发布
查看21道真题和解析
