生成树

连通无向图中包含全部顶点的一棵树;恰有 n-1 条边,是 MST、生成森林和树形结构的基础。

标签 图论 / 生成树 / 树

定义

给定无向图 𝐺=(𝑉,𝐸)。若子图 𝑇=(𝑉,𝐸𝑇) 是一棵 树,则称 𝑇 为 𝐺 的生成树(spanning tree),也称支撑树。

生成树必须包含 𝐺 的全部顶点,但不要求包含全部边。若 |𝑉|=𝑛,则任何生成树都恰有 𝑛−1 条边。

生成树存在当且仅当 𝐺 连通。图不连通时不存在生成树,只能对每个连通块分别取生成树,得到生成森林。

等价刻画

设 𝐺 是 𝑛 个顶点的连通无向图,𝑇 是 𝐺 的生成子图。以下条件等价:

  • 𝑇 是一棵树;
  • 𝑇 连通且恰有 𝑛−1 条边;
  • 𝑇 无环且恰有 𝑛−1 条边;
  • 𝑇 是 𝐺 的极小连通生成子图:删去任意一条边都会不连通;
  • 𝑇 是 𝐺 的极大无环生成子图:加入任意一条未选的边都会成环。

这里的“极小”和“极大”都是按边集的包含关系而言,不是边权和最小。

基本回路与基本割

固定一棵生成树 𝑇。

  • 对每条非树边 𝑒=(𝑢,𝑣),𝑇+𝑒 中有唯一一个环,称为 𝑒 关于 𝑇 的基本回路。这个环由 𝑒 和 𝑇 上 𝑢 到 𝑣 的唯一路径组成。
  • 对每条树边 𝑒,删去 𝑒 会把 𝑇 分成两个连通块,从而确定一个割,称为 𝑒 的基本割。𝑒 是这个割中唯一的树边。

这两类结构给出生成树之间的交换方式:把一条非树边加入 𝑇,再从它形成的基本回路中删去一条树边,仍然得到一棵生成树。MST 的环性质、动态 MST 和树上路径问题都依赖这个观察。

与最小生成树、生成森林的关系

  • 带权连通图的最小生成树(MST)是一棵生成树,并使边权和最小。生成树本身没有权值目标,任意一棵生成树都可能不是 MST。
  • 带权不连通图没有生成树;对每个连通块求 MST 再合并,得到 最小生成森林。
  • Kruskal、Prim、Borůvka 都输出 MST,因此也输出生成树。
  • 生成树不要求唯一,也不要求按特定方式构造;BFS、DFS 和 MST 算法都能产生某棵生成树。

常见误解

  • 认为生成树要包含原图的所有边:生成树只保留 𝑛−1 条边,是生成子图,不是原图。
  • 认为不连通图也有生成树:没有;它只有生成森林。
  • 认为生成树是诱导子图:不是。生成树可以删去顶点之间的边,只保留一棵树。
  • 认为生成树唯一:一般不是;只有 𝐺 本身已经是树时,生成树才唯一。
  • 认为生成树上的路径就是原图最短路:不是。生成树只保证连通,不保证路径最短。
  • 认为任意生成树都是最小生成树:只有边权和最小的那一棵(或那些)才是 MST。
源码位置