生成树
连通无向图中包含全部顶点的一棵树;恰有 n-1 条边,是 MST、生成森林和树形结构的基础。标签 图论 / 生成树 / 树
定义
给定无向图 。若子图 是一棵 树,则称 为 的生成树(spanning tree),也称支撑树。
生成树必须包含 的全部顶点,但不要求包含全部边。若 ,则任何生成树都恰有 条边。
生成树存在当且仅当 连通。图不连通时不存在生成树,只能对每个连通块分别取生成树,得到生成森林。
等价刻画
设 是 个顶点的连通无向图, 是 的生成子图。以下条件等价:
- 是一棵树;
- 连通且恰有 条边;
- 无环且恰有 条边;
- 是 的极小连通生成子图:删去任意一条边都会不连通;
- 是 的极大无环生成子图:加入任意一条未选的边都会成环。
这里的“极小”和“极大”都是按边集的包含关系而言,不是边权和最小。
基本回路与基本割
固定一棵生成树 。
- 对每条非树边 , 中有唯一一个环,称为 关于 的基本回路。这个环由 和 上 到 的唯一路径组成。
- 对每条树边 ,删去 会把 分成两个连通块,从而确定一个割,称为 的基本割。 是这个割中唯一的树边。
这两类结构给出生成树之间的交换方式:把一条非树边加入 ,再从它形成的基本回路中删去一条树边,仍然得到一棵生成树。MST 的环性质、动态 MST 和树上路径问题都依赖这个观察。
与最小生成树、生成森林的关系
- 带权连通图的最小生成树(MST)是一棵生成树,并使边权和最小。生成树本身没有权值目标,任意一棵生成树都可能不是 MST。
- 带权不连通图没有生成树;对每个连通块求 MST 再合并,得到 最小生成森林。
- Kruskal、Prim、Borůvka 都输出 MST,因此也输出生成树。
- 生成树不要求唯一,也不要求按特定方式构造;BFS、DFS 和 MST 算法都能产生某棵生成树。
常见误解
- 认为生成树要包含原图的所有边:生成树只保留 条边,是生成子图,不是原图。
- 认为不连通图也有生成树:没有;它只有生成森林。
- 认为生成树是诱导子图:不是。生成树可以删去顶点之间的边,只保留一棵树。
- 认为生成树唯一:一般不是;只有 本身已经是树时,生成树才唯一。
- 认为生成树上的路径就是原图最短路:不是。生成树只保证连通,不保证路径最短。
- 认为任意生成树都是最小生成树:只有边权和最小的那一棵(或那些)才是 MST。