最小生成树

生成树从原图删除所有环，却保留全部顶点之间的连通性；MST 再在这些骨架中比较边权总和。割性质从“任何连接方案都必须跨过这道边界”寻找可加入边，环性质从“圈上总有一条边可以删”寻找可排除边。两者是同一个交换动作的正反视角。

目标函数只把所选边各计一次，不关心某条边会出现在多少对顶点的树路径中。因此一棵总造价最小的网络骨架，未必给任何指定根提供最短路线，也不自动具有冗余或容错能力。

三角形的边权为 $1,2,4$ 时，取权 $1,2$ 两边得到总权 $3$；权 $4$ 的边在唯一圈中严格最重，不可能进入 MST。若三条边都为 $1$，删去任意一条都得到总权 $2$ 的 MST，说明平局会造成多解。所有边权互异时 MST 唯一；反命题不成立，含相等权边的图也可能因结构限制只有一棵 MST。

负权边不会导致无界下降，因为任何生成树固定只含 $|V|-1$ 条边；贪心证明也只比较边权。平行边应作为独立候选，较重的同端点平行边构成长度为二的多重图圈并可排除；自环不可能属于生成树。若基础文件格式只表示简单图，应在读入时明确合并平行边或保留边 ID，不能默默覆盖。

图不连通时不存在覆盖全部顶点的生成树。对每个连通分量分别最小化，得到最小生成森林；若有 $c$ 个分量，森林含 $|V|-c$ 条边。有向图的对应问题需要指定根与入弧方向，称为最小树形图，并不由无向割性质直接解决。

MST 与最短路公理库最短路问题Shortest-path problem在有限有向实权图中寻找源点到各顶点的最小有向游走成本。在非负权图上仍可不同。若 $w(sa)=2,w(ab)=2,w(sb)=3$，MST 取 $sa,ab$，总权 $4$；从 $s$ 出发却会沿直边 $sb$ 以成本 $3$ 到达 $b$，而 MST 中的路线成本为 $4$。相应的最短路树取 $sa,sb$，总权 $5$。

在网络布线中，边权可表示铺设一段链路的成本，MST 给出无冗余连通骨架；若系统还要求故障容错，就要增加边连通约束，MST 本身不够。单链接聚类按边权从小到大合并分量，截断 Kruskal 过程可得到指定簇数；这一解释依赖权重是可比较的不相似度。

任意 MST 也是最小瓶颈生成树：若有另一棵树的最大边更轻，可在 MST 最大边诱导的割上找到更轻替换边，矛盾；最小瓶颈树反过来未必最小化总权。边权更新后，删除一条树边需要在新割上寻找替代边，动态 MSF公理库动态最小生成森林Dynamic minimum spanning forest · Dynamic MSF · Fully dynamic MST在无向带权图的边插入与删除之间持续维护每个连通分量的最小生成树，并以最轻跨割替代边恢复最优森林。因此是另一个带更新接口的问题，静态交换性质只提供正确性工具，不给出更新时间界。