树

树恰好使用足够的边把全部顶点连起来。少一条树边，原本由它连接的两侧失去唯一通道；多加一条非边，新边与原有的唯一端点路径合成一个圈。它同时位于“极小连通”和“极大无圈”两种边界上。

唯一通道也带来层级。指定一个根后，从根到每个非根顶点的唯一道路确定一条父边，递归可以沿父子方向展开而不会从第二条路线回流。根、孩子次序和边方向都属于后来添加的数据，无根树的定义并不包含它们。

树没有环路冗余，这使证明与算法容易分解，也使网络对单边故障敏感。所谓“结构简单”具体表现为路径唯一和叶可剥离，并不意味着直径、度数分布或嵌入形状都相同。

路径 $P_n$ 与星图 $K_{1,n-1}$ 都是树。前者的最长路径贯穿全部顶点，后者任意两片叶子之间只需经过中心；它们边数同为 $n-1$，直径却分别为 $n-1$ 与 $2$（当 $n\ge 3$）。边数公式不会抹去这些结构差异。

公司汇报关系只有在每位非最高负责人恰有一个直接上级、所有成员属于同一体系且不存在循环汇报时，才形成有根树。若一个项目成员同时汇报给两位经理，底层无向骨架可能出现多条路径；若存在相互汇报，则有向关系还出现圈。现实层级是否真是树，需要逐项核对这些约束。

每棵树都是二分图公理库二分图Bipartite graph顶点可分成两个独立侧、且每条边都跨越两侧的有限简单无向图。。任选根 $r$，按距离 $\mathrm{dist}(r,v)$ 的奇偶把顶点分成两侧；树的每条边连接相邻层，因此一定跨侧。这个证明只用无圈性确保相邻点的根距离不可能同奇偶。

一个有向无环图公理库有向图Directed graph · Digraph以顶点有序对为弧、能够保留连接方向的有限简单图结构。未必是树：它可能不连通，也可能让同一顶点通过多条路线从源点到达。反过来，给无根树的边任意定向会得到有向无环图，但未必得到从某个根可达全部顶点的树形结构。

有限性不能从计数刻画中删去。双向无限路径连通且无圈，却没有叶子；在无限基数下，$|E|=|V|-1$ 不再像有限整数那样区分结构。唯一简单路径刻画仍可用于无限树，叶归纳和 $n-1$ 计数则需要另行证明适用范围。

树中每条边都是桥公理库割点与桥Cut vertex and bridge删除后增加连通分量数的顶点或边。。删去边 $uv$ 后若两端仍可相连，替代路径与 $uv$ 会组成圈；所以删除该边恰把树分成两个分量。相应地，至少含三个顶点的树中，每个度数至少为二的顶点都是割点。

生成树公理库生成树Spanning tree包含原图全部顶点且自身为树的子图。从一般连通图中选出一个覆盖全部顶点的树形骨架。它保留可达性，却舍弃所有环路冗余；最小生成树再在这些骨架之间比较边权总和，最短路径树则比较固定源到各点的距离，两种优化目标不能互换。

叶删除支持大量归纳证明：先在较小树上建立结论，再把叶及其唯一关联边接回。Prüfer 编码公理库Prüfer 编码Prüfer code · Prüfer sequence把含 $n$ 个标号顶点的树双射编码为长度 $n-2$ 的顶点序列。反复删除最小标号叶，Cayley 公式公理库Cayley 树计数公式Cayley's formula顶点集固定为 $[n]$ 的标号树恰有 $n^{n-2}$ 棵。由此计数标号树；树上动态规划也把同一分解思想改写成自底向上的状态合并。

为树指定根后，父子、祖先、深度与子树公理库有根树与祖先关系Rooted tree · Ancestor relation · Parent and depth in a tree在树中选定根后，由唯一根路径定义父子、祖先、深度与子树。都由唯一根路径定义。Euler tour、最近公共祖先和重链剖分利用的是这层附加结构；讨论这些算法时应把原无向树与选择出的根清楚分开。