[生成树计数]

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的最后一行和最后一列。然后用高斯消元求出这个新矩阵的上三角矩阵。将上三角矩阵对角线的点相乘所得到的绝对值就是这个图所能形成的树的个数。

全部评论

相关推荐

03-15 00:45
已编辑
中国科学院大学 Java
问的很简单都秒了,但是面试官没开摄像头,疑似kpi,无后续。--------------------3/14更新,3/12通知给了口头offer,3/13发了意向书,已拒。一面(35min)(25/3/6)(无后续)    1、自我介绍    2、介绍一下你的那个Python相关项目(本科毕设,web系统+算法模型提供部分接口)    3、Java面向对象有哪些特点呢?详细说一下。    4、介绍一下hashmap;为什么要把链表转换为红黑树呢?红黑树查找的时间复杂度?1.7和1.8的区别。    5、介绍一下concurrentHashmap。    6、synchronized锁和Lock锁有什么区别?    7、公平锁的一个底层是怎么实现的呢?    8、线程池的核心参数、拒绝策略、提交一个任务执行流程?    9、spring有哪些特点?(ioc/aop)    10、spring中对于循环依赖是怎么解决的?    11、MySQL和redis的区别?    12、MySQL的索引结构是什么?    13、MySQL的事务有哪些特性?怎么保证?    14、MySQL的默认隔离级别?可重复读是怎么做到的呢?    15、介绍一下MVCC和快照读readview。    16、一般在什么场景下会使用redis?    17、对于大量的请求,如果此时缓存中还没有写入数据怎么办?    18、介绍一下redis实现的分布式锁。    19、有用过es和mongo DB吗?(知道,没用过)    20、消息中间件用过吗?说一下你的使用场景?    21、一个场景,如果说有一个接口响应的比较慢,如果说让你排查,你会怎么去排查?(上下游接口、大key问题,只答了两,后面试官补充)    无手撕,反问业务。
胖墩墩的查理在学c语言:哥们我是五号面的 流程差不多
查看21道真题和解析
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务