树 (序论)

关于图论中的树, 请参见 “树”.

在序论中, 树是偏序集中的一类, 它的序关系如果图示出来, 则像是一棵树. 反过来, 对于图论中的树, 如取一顶点作为树根, 则它可以自然地赋予偏序结构并成为树, 树根是它的最小元, 而从树根出发的一条道路就是它的一条升链.

1定义

定义 1.1 (树). 树是偏序集 $(T,\le )$, 满足以下条件:

•	$T$ 有最小元, 称为树根.

•	对任意 $t\in T$, $T$ 的子偏序集 $\{s\in T\mid s\le t\}$ 是良序集.

如无歧义, 也将树简记为 $T$.

通常会谈论树的以下结构:

定义 1.2. 在树 $(T,\le )$ 中,

•	$T$ 的树枝是其极大链.

•	元素 $t\in T$ 的高度是良序集 $\{s\in T\mid s\le t\}$ 的序数, 记为 $\mathrm{ht}(t)$.

•	给定序数 $\alpha$, 则 $T$ 的高度为 $\alpha$ 的水平集为 $\{t\in T\mid \mathrm{ht}(t)=\alpha \}$.

2例子

•	良序集是树, 例如自然数集 $(\mathbb{N},\le )$ 是树.

•	集合 $\{0,1\}$ 的子集构成的偏序集不是树.

•	对于图论中的树, 如取一顶点作为树根, 则它可以自然地赋予偏序结构并成为树.

3性质

命题 3.1 (计数). 记 $a_n$ 为集合 $\{1,\cdots ,n\}$ 上使其能成为树的偏序结构个数, 则有 $a_n=n^{n-1}$ 且 (指数型) 生成函数$$T(x)=\sum _{n=1}^{\infty }\frac{a_n}{n!}{x}^n$$满足 $T(x)=x{\mathrm{e}}^{T(x)}$.

4相关概念

•	Suslin 树
•	Aronszajn 树

术语翻译

树 • 英文 tree • 德文 Baum (m) • 法文 arbre (m) • 拉丁文 arbor (f) • 古希腊文 δἐνδρον (n)