生成树总结

生成树

一个无向图的生成树指的是从图中选若干边构成边集，全部点构成点集，使得这个边集加上点集恰好是一棵树。

生成树计数

一个无向无权图(允许重边不允许自环)的邻接矩阵为g，显然这是一个对称矩阵，g[u][v]代表边(u,v)的重数，即若存在一条边(u,v)则g[u][v]的值为1，若存在k条，则g[u][v]的值为k。
一个无向无权图(允许重边不允许自环)的度数矩阵为deg，显然这是一个对角矩阵，deg[u][u]代表点u的度数。
一个无向无权图(允许重边不允许自环)的基尔霍夫矩阵(拉普拉斯矩阵)为hoff，是度数矩阵减去邻接矩阵。
矩阵树定理说一个无向图的生成树的个数刚好等于基尔霍夫矩阵的行列式的任意n-1阶主子式(代数余子式)的行列式的绝对值。
生成树计数复杂度$O(V^3+E)=O(V^3)$
黑暗前的幻想乡
我们利用矩阵树定理就能轻松解决

最小生成树

有一个无向带权图，每条边有权$x_i$，需要求出一个生成树T，并最小化$\begin{aligned}\sum_{i\in T}x_i\end{aligned}$
kruskal算法：贪心从小到大枚举边合并森林即可。这里就不证明此算法了。
最小生成树复杂度$O(V+ElgE)=O(ElgE)$
最小生成树

最小生成树计数

由于最小生成树各自边权构成的多重集合是一样的，并且易证不同的边权对最小生成树的影响是独立的，所以我们可以通过将边按照边权分类，分别求出每一种边权各自对联通块的贡献，然后利用计数的乘法原理合并即可。我们需要先求出任意一个最小生成树，当我们对某一种边权进行讨论的时候，我们需要将这个生成树中这一边权的边全删掉，然后对剩余联通块进行缩点并重新编号，将待选集合中的边映射到联通块间的边，并去掉自环。这样以后待选集合中的边的边权就相等了。这时我们可以借助矩阵树定理来求解。
最小生成树计数复杂度$O(ElgE+V^3)=O(V^3)$
最小生成树计数

严格次小生成树

严格次小生成树和最小生成树的边权多重集合中只有一个边权不一样，这样我们就有了一个简单的算法，先求出任意一个最小生成树，然后枚举没有被选中为构建最小生成树的边，假设这个边为$(u,v,w_1)$，我们在最小生成树上求出点$u$到点$v$这条路径上的最大边权$w_2$和严格次大边权$w_3$，若$w_1=w_2$则我们用此边换掉次大边，若$w_1>w_2$则我们用此边换掉最大边，这样我们最终能得到很多非最小生成树，从中选出最小的那个，他就是次小生成树,这个过程需要维护树上的路径信息，有算法都可以树剖、树上倍增、lct等等，我们这里使用树上倍增的办法来解决。
严格次小生成树时间复杂度$O(ElgE+ElnV)=O(ElgE)$
严格次小生成树

最小乘积生成树

有一个无向带权图(权为正数)，每条边有权$x_i$和权$y_i$，需要求出一个生成树T，记$\begin{aligned}X=\sum_{i\in T}x_i,Y=\sum_{i\in T}y_i\end{aligned}$,要求最小化乘积$XY$
我们假设已经求出了所有生成树，他们的权为$(X_i,Y_i)$我们把这个二元组看做二维平面上的点，则最小乘积生成树一定在凸包上。进一步分析，整个凸包都在第一象限，那么我们可以锁定出两个点了，他们一定在凸包上。分别求出最小的$X_i$对映点$A$，和最小的$Y_i$对映点$B$，那么答案就在$AB$左下方，我们求出一个点$C$，若能让叉积$AC*AB$最大且为正数，则$C$一定也在凸包上。我们递归处理$AC$和$CB$即可。凸包上的点期望为lg级别。
最小乘积生成树复杂度$O(ElgElg(V!))=O(ElgElgV)$
最小乘积生成树

最小差值生成树

有一个无向带权图，每条边有权$x_i$，需要求出一个生成树T，让T的最大边权和最小边权的差值尽可能小。
我们对边集排序后，等价于求最短的一段区间，这个区间内部的边能够生成一棵树，这种连通性维护的问题，直接使用lct就可以了，
最小差值生成树时间复杂度$O(ElgE+Elg(E+V))=O(ElgE)$
最小差值生成树

k度限制最小生成树

在最小生成树的要求下，多一个条件: 有一个定点的度数不能超过k。
k度限制最小生成树与k-1度限制最小生成树最多有一条边的区别。
时间复杂度$O(ElgE+kV)$
k度限制最小生成树

最小直径生成树

给无向连通图，求一个直径最小的生成树。
以图的绝对中心为根的最短路树，是一个最小直径生成树。先用floyd求多源最短路，然后对每一条边，假设绝对中心在此边上，求出该绝对中心的偏心率，可以考虑从大到小枚举最短路闭包来实现，汇总得到绝对中心，最终以绝对中心为根，求最短路树。
时间复杂度$O(n^3)$

最小比值生成树

有一个无向带权图(权为正数)，每条边有权$x_i$和权$y_i$，需要求出一个生成树T，记$\begin{aligned}X=\sum_{i\in T}x_i,Y=\sum_{i\in T}y_i\end{aligned}$,要求最小化比值$\frac{X}{Y}$.
我们设$r=\frac{X}{Y}$则有$rY-X=0$我们定义函数$f(r)=rY-X$，为当以$ry_i-x_i$作为权值的时候的最大生成树的值，这里显然f(r)关于r单调增，当我们找到一个r使得f(r)等于0的时候，r就是我们分数规划要的答案。
时间复杂度$O(lgn)*O(MST)$