形式陈述

图 $G=(V,E)$$G=(V,E)$ 的生成树是子图 $T=(V,E_T)$$T=(V,E_T)$，其中 $E_T\subseteq E$$E_T\subseteq E$ 且 $T$$T$ 是树。有限无向图存在生成树，当且仅当它连通。

直觉

生成树从连通网络中删去所有冗余环路，同时保持所有节点互相可达。

例子与边界

三角形图有三棵生成树，每棵删去一条边。非连通图没有覆盖全部顶点的生成树，但每个连通分量可以各取一棵树，得到生成森林。

推论与应用

带权图中寻找总权重最小的生成树得到最小生成树问题；它用于网络布线、聚类和广播协议。

参考资料

• Reinhard Diestel, Graph Theory, 5th ed., §1.5.
• Thomas H. Cormen et al., Introduction to Algorithms, 4th ed., Chapter 21.