关于生成树的两个性质：
（1）切割性质。假定所有边权均不相同。设$S$为既非空集也非全集的$V$的子集，边$e$是满足一个端点在$S$内，另一个端点在$V setminus S$内所有边权最小的一个，则图$G$的所有最小生成树均包含$e$。
说明：设$T=Vsetminus S$，则图$G$的任一生成树包含$S-T$割中的一条边（连通性）。考虑$e$作为$S-T$中唯一权值最小的边，则$MST（V）= MST(T) + MST(S) + e$，这是显然的。
（2）回路性质。假定所有边权均不相同。设$C$是图$G$中的任意回路，边$e$是$C$上权值最大的边，则图$G$的所有最小生成树均不包含$e$。
说明：设由$e$连接的端点分别为$s$和$t$，并且令$S$ + $T$ = $V$，且$s in S$，$t in T$，则显然$e in S-T$，且$C$上存在$f eq e$：$f in S-T$，于是对于任意的$S-T$割，$e$的权值都不是最小的，因此$e$不在任一MST中。
————————————————————————————————————
以下是生成树的相关问题。
$star$ 增量最小生成树。从包含$n$个点的空图开始，依次加入$m$条带权边。每加入一条边，输出当前图中最小生成树的权值（如果当前图不联通，输出无解）。
解：
法一：每次加边后计算$MST$，复杂度$O(m^2 ext{log}n)$。
法二：根据回路性质，每次计算出$MST$后，把原图中的其余边删除，加入新边后再次计算$MST$，复杂度$O(mn ext{log}n)$。
法三：在之前$MST$基础上新加一条边恰好得到一个环，根据回路性质，为了得到新的$MST$，需要删除环上权值最大的边，用简单深搜判断，复杂度$O(mn)$。
$star$ 最小瓶颈生成树。给出加权无向图，求一棵生成树，最小化最大边权。
解：
最小生成树就是最小瓶颈生成树。
$star$最小瓶颈路。给定加权无向图的两个节点$u$和$v$，求从$u$到$v$的一条路径，使得路径上的最长边最短。
解：
法一：二分+BFS。
法二：$MST$上$u$到$v$的路径即最小瓶颈路。
$star$每对节点间的最小瓶颈路。给出加权无向图，求每两个节点$u$和$v$之间的最小瓶颈路的最大边长$f(u, v)$。
解：
先求出最小生成树。再用dfs把MST变成有根树，同时计算$f(u, v)$，当新访问一个节点$u$时，考虑所有已经访问过的节点$x$，更新$f(x, u) = max(f(x, v), w(u, v))$，其中$v$是$u$的父亲节点。每个$f(u, v)$只需要常数时间，总复杂度$O(n^2)$。
$star次小生成树（权值大于MST当且仅当MST唯一）$
解：
法一：考虑任一MST，由于次小树与其不完全相同，枚举$n-1$条边中不在次小树中的，删除该边计算余图的MST，综合答案得到次小树。复杂度$O(nm ext{log}n)。$
法二：
引理：次小生成树可通过$MST$发生一次边交换得到。
证明：为此只需证明MST和次小树恰有$n-2$条公共边。假设次小树中两条边$x$和$y$不在MST中，考虑图MST + x + y的次小生成树T，只需证明T中至多包含x和y中的一条边。假设x在T中，MST中某条边同时被删除，那么此时$n$条边的图的最小生成树的权值大于MST的权值，因此不小于T的权值，因此需要删除y，因为它是其所在环上权值最大的边。
因此枚举需要进入的边，删除环上在MST上权值最大的边，新树即次小树。复杂度$O(n^2)$（使用上一个问题的预处理）。
$star$有向最小生成树。给定一个有向带权图$G$和其中一个节点$u$，找出一个以$u$为根节点，权和最小的有向生成树。有向生成树(directed spanning tree)也叫树形图(arborescence)，是指一个类似树的有向图，满足以下条件：
1. 恰有一个入度为$0$的点，称为根节点。
2. 其它节点入度为$1$。
3. 可以从根节点到达其它节点。
不难发现，树形图中不存在有向环。
解：
固定根的最小树形图可以用朱-刘（朱永津-刘振宏，1965）算法解决。复杂度$O(nm)$。
1. 预处理：删除自环并判断根节点可否到达其它节点，如果不能，输出无解。
2. 给所有的非根节点选择一条权值最小的入边。若$n-1$条边不成圈，则这些边形成最小树形图，否则缩圈为点，继续上述过程。
缩圈之后，同时需要把圈上边权和加到答案中。注意对缩圈得到的节点引入入边时需要调整入边的权值以抵消删除圈内与入边指向相同节点的边的影响。