树

树是一种刚好足以连通的结构。任意两点之间都能走到，却没有一条边可以靠绕路替代：删掉任何一条边，原来的一整棵树就分成两块。与之对偶，给树增加一条原来没有的边，新边会和两端之间的唯一路径形成恰好一个圈。

唯一通路也是树上递归有效的原因。把树定根并删除根后，每个孩子恰好落在一个不同的连通分量中；若两个孩子仍能在根之外相连，那条路与两条根边就会组成圈。因此孩子子树的顶点集互不重叠，每个非根子树与外部只通过父边连接。对子树分别计算后沿父边合并，才不会把共享顶点重复当成两个独立部分。

唯一路径如何刻画树 ​

连通性保证任意两点之间至少有一条路。若有两条不同的简单路径，沿它们分开再重合的部分会得到一个圈理路路与圈Path and cycle in a graph用相邻顶点序列刻画图中的行走、简单路径与首尾闭合的简单圈。，与无圈矛盾。因此树中路径唯一。

反过来，若任意两点之间恰有一条简单路径，图当然连通；若存在圈，则圈上两点之间沿两个方向分别前进，可得到两条不同的路径，矛盾。这段论证表明，唯一性不是树的额外算法性质，而是连通与无圈的等价表达。

叶子为什么一定存在 ​

在至少有两个顶点的有限树中，取一条最长简单路径。它的端点至少有一个邻居，即路径中的下一点。若端点还有其他邻居，该邻居若不在路径上，就能延长路径；若已经在路径上，就产生圈。两种情况都不允许，所以路径的两个端点都是叶子。

删除一个叶子及其唯一关联边，剩余部分仍无圈，也仍连通：两个剩余顶点之间的路径不可能把只有一个邻居的叶子当作中间站。因此可由单顶点树开始归纳，得到

对有 $c$ 个连通分量的森林，逐分量相加得到 $|E|=|V|-c$，空森林也满足这个等式。

边数不是独立判据 ​

一个三角形加一个孤立顶点共有四个顶点、三条边，恰好满足 $m=n-1$，却既不连通也不无圈。要从边数判定树，仍需保留等价刻画中的另一项条件。

为什么“连通加 $n-1$ 条边”足够？连通图若有圈，可删去圈上一条边而不破坏连通性；重复操作会得到一棵包含所有顶点的树，它已有 $n-1$ 条边。原图若也只有这么多边，就没有额外的圈边可删。另一方向，无圈图是森林，$m=n-c=n-1$ 强制 $c=1$。

同样大小可以有很不同的形状 ​

五顶点路径 $1-2-3-4-5$ 与五顶点星图 $K_{1,4}$ 都是树，都有四条边。直径指所有两点间距离的最大值：路径的两个端点相距 $4$，而星图中任意两片叶子经过中心只需 $2$ 步，所以二者直径分别为 $4$ 和 $2$。

以路径端点 $1$ 为根时，最深顶点 $5$ 的深度是 $4$；以中点 $3$ 为根时，最深处只有 $2$。这改变了有根树的高度，却没有改变无根树的直径。因此“树有线性条边”不意味着每种树操作都是对数时间，线性链就可能使按父子关系查找退化为线性深度。

二叉树理路二叉树Binary tree由空树或根节点及左右两个子树槽位递归组成的有限结构；单孩子所在的左右位置也属于树形。需要区分左、右槽位，并常为递归方便允许空树。其非空、无共享部分忘掉这些额外信息后，才落到本条的无向树模型。一个有向无环图也未必来自树：菱形结构 $r\to a,r\to b,a\to t,b\to t$ 没有有向圈，但忽略方向后有圈，且 $t$ 有两个不同的上游路径。

树是极小连通图：每条边都是桥。它也是在给定顶点集上的极大无圈图：增加任意缺失边都会成圈。后一性质对一般森林不成立；两个不同分量之间仍可加边而不成圈。两种极值说法分别对应“删不掉”和“加不了”，不是在比较不同顶点集的大小。

选根后，把偶数深度与奇数深度顶点分在两侧。任一边连接父子，深度相差 $1$，所以每条边都跨越两侧，证明树是二分图理路二分图Bipartite graph顶点可分成两个独立侧、且每条边都跨越两侧的有限简单无向图。。单顶点树可把另一侧取为空集。

树上动态规划利用的是子树接口，而不只是画成分叉状的外观。例如计算每个子树的节点数，叶子返回 $1$，内部节点返回 $1$ 加所有孩子结果之和；每条父子边只传递一次结果，总工作量为 $O(n)$。若共享同一个子问题形成 DAG，直接套用独立子树求和就可能重复计数。

一般连通图可以抽取生成树理路生成树Spanning tree包含原图全部顶点且自身为树的子图。来保留可达性。最小生成树在所有生成树中优化总边权；从源点得到的最短路树则保留源点到各点的最短距离。两者优化的目标不同，不能仅因输出都为树而互相替代。