树

连通无环无向图;n 个点 n-1 条边,任意两点有唯一简单路径,是有根树、DFS 序和树形 DP 的基础。

标签 图论 / 树

定义

无向图 𝐺=(𝑉,𝐸) 若连通且无环,则称为树。无环图称为森林,森林的每个连通块都是一棵树。

只有一个顶点、没有边的图也是树。𝑛≥2 时,树至少有两个叶子,其中叶子指度为 1 的顶点。

等价刻画

对 𝑛 个顶点的无向图,以下条件等价:

  • 连通且无环;
  • 连通且恰有 𝑛−1 条边;
  • 无环且恰有 𝑛−1 条边;
  • 任意两点之间有且仅有一条简单路径;
  • 连通,且任意一条边都是桥;
  • 任意一对不相邻顶点之间加一条边,恰好形成一个环。

这些刻画说明树是“最小的连通图”,也是“最大的无环图”:少一条边会不连通,多一条边会成环。

有根树

给树指定一个根 𝑟,并把边定向为从父节点指向子节点,就得到有根树。

  • 根没有父节点;除根外,每个节点恰有一个父节点。
  • 祖先、后代、兄弟按父子关系定义;深度是到根的边数,节点的高度是它到子树中叶子的最大距离。
  • 有根树中的叶子通常指没有子节点的节点;无根树的叶子通常指度为 1 的顶点。
  • 根的选择是额外的结构。同一棵无根树可以指定不同的根,得到不同的父子关系。

节点 𝑣 的子树通常指 𝑣 与它的所有后代。它是一个连通子图;按 DFS 序展开后,子树对应一个连续区间。

常见误解

  • 认为 𝑛 个点、𝑛−1 条边一定是树:还需要连通或无环。三角形加一个孤立点有 4 个点、3 条边,但不是树。
  • 认为树一定是有根树:根是额外指定的结构;无根树本身没有父子关系。
  • 认为树中两点之间的路径不唯一:树中任意两点之间有且仅有一条简单路径。
  • 认为删掉树的一条边仍然连通:𝑛≥2 时,每条边都是桥。
  • 把有根树的子树和任意连通子图混淆:有根树的子树要求包含节点的全部后代。
源码位置