树
连通无环无向图;n 个点 n-1 条边,任意两点有唯一简单路径,是有根树、DFS 序和树形 DP 的基础。标签 图论 / 树
定义
无向图 若连通且无环,则称为树。无环图称为森林,森林的每个连通块都是一棵树。
只有一个顶点、没有边的图也是树。 时,树至少有两个叶子,其中叶子指度为 的顶点。
等价刻画
对 个顶点的无向图,以下条件等价:
- 连通且无环;
- 连通且恰有 条边;
- 无环且恰有 条边;
- 任意两点之间有且仅有一条简单路径;
- 连通,且任意一条边都是桥;
- 任意一对不相邻顶点之间加一条边,恰好形成一个环。
这些刻画说明树是“最小的连通图”,也是“最大的无环图”:少一条边会不连通,多一条边会成环。
有根树
给树指定一个根 ,并把边定向为从父节点指向子节点,就得到有根树。
- 根没有父节点;除根外,每个节点恰有一个父节点。
- 祖先、后代、兄弟按父子关系定义;深度是到根的边数,节点的高度是它到子树中叶子的最大距离。
- 有根树中的叶子通常指没有子节点的节点;无根树的叶子通常指度为 的顶点。
- 根的选择是额外的结构。同一棵无根树可以指定不同的根,得到不同的父子关系。
节点 的子树通常指 与它的所有后代。它是一个连通子图;按 DFS 序展开后,子树对应一个连续区间。
常见误解
- 认为 个点、 条边一定是树:还需要连通或无环。三角形加一个孤立点有 个点、 条边,但不是树。
- 认为树一定是有根树:根是额外指定的结构;无根树本身没有父子关系。
- 认为树中两点之间的路径不唯一:树中任意两点之间有且仅有一条简单路径。
- 认为删掉树的一条边仍然连通: 时,每条边都是桥。
- 把有根树的子树和任意连通子图混淆:有根树的子树要求包含节点的全部后代。