生成树

生成树是连通网络的骨架。它保留任意两顶点之间的可达性，却删除所有形成环的冗余边。树中任意两点之间只有一条简单路径，因此每条边都承担不可替代的连接职责。

这种骨架同时具有两种极值性质。删去任意树边，图会断开；向树加入任意一条非树边，图中会出现唯一一个圈。前者说明它是极小连通结构，后者说明它是极大无圈结构。

一个连通图往往有许多生成树。它们选择不同的路径承担连接任务，反映原图中的冗余可以怎样被裁剪。生成树本身不保留故障容错；删去骨架上的一条边便会断网，所以工程系统通常在树之外保留额外边。

三角形图有三棵生成树，每棵都删除三条边中的一条。原图的一个圈对应三种可删边选择；得到的每棵树都保留三个顶点，并含两条边。

四边形加一条对角线时，不能只“任选三条边”。选出的边必须覆盖四个顶点且保持连通；若三条边围成一个三角形并漏掉第四个顶点，就不是生成树。这个边界说明，边数 $n-1$ 只是必要条件，还要同时检查连通或无圈。

非连通图没有覆盖全部顶点的生成树。对每个连通分量分别取生成树，可以得到生成森林。若图有 $c$ 个连通分量，任意生成森林含 $n-c$ 条边。

带权图中的最小生成树公理库最小生成树Minimum spanning tree · MST连通加权图中总边权最小的生成树及其算法问题。在所有生成树中最小化总权重。它仍然先满足“覆盖、连通、无圈”，再比较成本；最短路径树则从固定源点优化到各点的距离，两种目标通常产生不同树。

深度优先搜索和广度优先搜索记录首次发现新顶点的边，便能在线性时间内构造一棵生成树。搜索树还保留遍历层次、父子关系或 DFS 时间戳，成为连通性、割点和回边分析的基础。

图拟阵公理库图拟阵Graphic matroid以图边为底集、以无环边集为独立集的拟阵。把无圈边集视为独立集，生成树恰好是其基。不同生成树都含 $n-1$ 条边，基交换性质解释了许多贪心算法为何能够逐边替换而不破坏可行性。

Cayley 公式公理库Cayley 树计数公式Cayley's formula顶点集固定为 $[n]$ 的标号树恰有 $n^{n-2}$ 棵。计数完全图的生成树；矩阵树定理把生成树总数写成图 Laplacian 的任一主余子式。生成树因此不仅是算法输出，也连接组合计数、线性代数与电网络。