# 最小生成树

1. 最小生成树，直接每条边翻倍，可以达到 2-近似旅行商问题

2. 最小生成树上的边是割里最小权的边

3. 基于比较的 MST 算法复杂度均为 $O(|E|\log|V|)$

4. 割：给定点集 $S$ 后 $(S,V-S)$ 的边集称为一个割；割里的权最小的边为轻边

5. 给定一个割集，及一个包含在某个最小生成树的边集，边集中的边都不跨割集，则割中的轻边加到边集中，边集仍然包含在某个最小生成树

6. Kruskal 算法：将所有边按权值排序，依次加入边集，若加入后形成环，则不加入，直到边集中有 $|V|-1$ 条边
   - 使用并查集

7. Prim 算法：从任意一个点开始，每次加入一个点，加入的点是当前点集到剩余点集的最短边的另一端点，直到点集中有 $|V|$ 个点
   - 使用最小堆

8. 给定最小生成树，图上的一条边权变小，找到新的最小生成树需要时间为一个环的时间

9. 如何找次小生成树？

10. 如何找瓶颈生成树？瓶颈生成树是指树上最大边权最小的生成树；一棵最小生成树也是一棵瓶颈生成树

11. 随机方法求最小生成树，Tarjan, Chazelle

12. 对稀疏图求最小生成树？

13. 几何图上的最小生成树？$\Theta(|V|\log|V|)$，使用 Delaunay 三角剖分或 Voronoi 图