有向生成树

有向生成树通常指覆盖一个有向图全部顶点、并按一个根形成树形可达关系的有向子图。方向有两种约定：出向生成树从根沿有向路径到达所有顶点；入向生成树则从所有顶点沿有向路径汇入根。本文以出向情形为主，也称出向树形图（out-arborescence）。

例如，顶点为 $s,a,b,c,d$，选边 $s\to a,s\to b,a\to c,b\to d$。根 $s$ 能到达其余四点，而且每点从根到达的有向路径唯一。若原图还含 $c\to d$ 等额外边，选出的四条边仍可构成原图的一棵有向生成树；“生成”要求覆盖全部顶点，不要求保留全部边。

每个非根顶点恰有一条进入边，根的入度为零；四条边覆盖五个顶点。

定义中的树和方向

设有限有向图 $G=(V,E)$、根 $r\in V$。一个出向生成树为子图 $T=(V,F)$，满足忽略方向后的 $T$ 是一棵树，且从 $r$ 到每个顶点都存在有向路径。底层树使无向路径唯一；可达性再保证这条路径的每一步方向都朝外。于是根入度为零，非根顶点入度均为一，且 $\mathrm{\#}F=\mathrm{\#}V-1$。

单点图的空边集构成以该点为根的出向树。若只覆盖顶点的一个真子集，它可以是树形图，却不是原图的生成树。若方向全部逆转，同一底层树从出向变为入向；入向树的非根顶点是出度一，而非入度一。

可达性加边数的等价判据

定理。 对一个含 $n\ge 1$ 个顶点、$n-1$ 条弧且不含自环的有向子图 $T$，若根 $r$ 能到达全部顶点，则 $T$ 是以 $r$ 为根的出向生成树。这里不预先排除长度大于一的有向环。

证明。 每个非根顶点都被某条从根出发的路径最后一步进入，所以入度至少一。已有 $n-1$ 个非根顶点，而所有顶点入度之和等于总边数 $n-1$，故每个非根点入度恰一，根入度为零。

再证明底层结构没有无向环。根可达所有顶点，忽略方向后图连通；一个 $n$ 点连通无向图至少需 $n-1$ 条边。若这里存在一个无向环，删除环上任意一条边仍保持连通，便得到少于 $n-1$ 条边的连通图，矛盾。因此底层图是一棵树，且已知根有向可达全部顶点，满足定义。若存在反向成对的两条弧，底层作为多重边计数，它们形成二边闭合，同一删边论证也将排除这种冗余。

上述最少边数事实可以直接建立：从一个顶点出发逐步把其他顶点纳入已连接集合，每加入一个新顶点，至少需要一条将它接入的不同边；直到纳入全部 $n$ 点，至少使用 $n-1$ 条。

主例有五个顶点和四条边，且从 $s$ 可达所有点，因此判据立即适用。仅有“每个非根点入度一、根入度零”却不足够：根 $r$ 孤立，另外两点有边 $a\to b,b\to a$，共有三点两边，各入度符合条件，但根无法到达环上的两点。这说明可达条件不能删除。

给定根时的存在条件

一个有向图存在以 $r$ 为根的出向生成树，当且仅当 $r$ 能到达全部顶点。必要性来自生成树的路径本身。为证明充分性，可给每个非根点 $v$ 选择一条从 $r$ 到 $v$ 的最少边路径，令 $d(v)$ 为其长度，选这条路径最后一条边 $p(v)\to v$，其中 $d(p(v))=d(v)-1$。

所有非根点各贡献一条边，总共 $n-1$ 条。沿这些父边逆向追溯时，非负整数 $d$ 每次减一，最终到达唯一的距离零顶点 $r$。将顺序反过来就得到从根到每点的有向路径，所以依上一节判据，选边形成出向生成树。这里距离只用来作存在性构造，未要求原图本身没有环。

变式。 主例增加边 $c\to d$ 后，可改选 $s\to a,s\to b,a\to c,c\to d$。它仍有四条边且根可达全部顶点，故是另一棵出向生成树。若同时保留原来的 $b\to d$，共五条边，顶点 $d$ 有两条进入边；虽然根仍可达全部点，所得子图已不是树。

路径唯一性与成本选择

出向生成树对每个非根顶点只保存一个父节点，因此适合表示广播分发、搜索发现关系和依赖传播的一个骨架。不过选出的树通常不唯一，且树中的根到点距离未必等于原图最短距离。上面的距离递减构造会保存最少边距离；任意出向生成树则没有这一保证。

若每条弧有费用，最小费用出向生成树要求在所有合格树中最小化边费用总和。不能对每个非根点简单选择最便宜的进入边就结束：这些局部选择可能形成一个根不可达的有向环。Edmonds 的最优分支理论处理的正是这种全局相容性，超出本篇对定义与存在条件的讨论。