树 (范畴论) [树]

观念

树是表达 “多个对象到一个对象的态射” 所需的基本结构. 因此, 可被树探测的对象 (即树形对象) 给出算畴 (多重范畴) 的一种定义.

这里所说的树特指有限, 有根 (rooted), 对称 (即一个节点上的边不计顺序) 的树.

定义

通过结点和边

树由结点 (vertex), 内边 (internal edge) 和外边 (external edge) 构成, 内边是两个结点之间的边, 外边是仅联系到一个结点的边; 每个结点有若干个 (可能是零个) 入边和一个出边. 整个树有一个唯一的根 (root), 即唯一指向外部的出边. 外部的入边称为叶 (leaf).

树

上图是一棵树的例子, 其中

  • $g$ 是根,
  • $e$ 是一个叶, 是外边, 是结点 $w$ 的入边,
  • $f$ 是内边, 是结点 $v$ 的出边, 也是结点 $w$ 的入边.

注意, 我们不要求树可以画在平面上. 同一结点的所有入边之间没有顺序.

作为偏序集

树的所有边的上下关系构成一个偏序. 具体地, 树可定义为满足如下条件的 (有限) 偏序集 $(P,\leq)$:

  • $P$ 有最小元 $\bot$ (即树的根);
  • 对任意 $x\in P$, 不超过 $x$ 的元素的子集构成一个全序.

此时 $P$ 的极大元 (可能不唯一) 即是树的叶.

树的态射

树的态射是个比较复杂的概念.

一种方便的定义是, 树的态射由如下几种基本态射生成:

  • 树的同构;
  • 退化 (degeneracy) $S \twoheadrightarrow T$, 其中 $S$ 是由 $T$ 在一条边中间插入一个新结点所得;
  • 内部面映射 (inner face map) $S \hookrightarrow T$, 其中 $S$ 是由 $T$ 缩合一条内边所得;
  • 外部面映射 (outer face map) $S \to T$, 其中 $S$ 是由 $T$ 剪除一个外顶点 (仅关联一条内边的顶点) 所得;

例

线性树

线性树是形如 $$ \begin{array} {c} \downarrow\\ \bullet\\ \downarrow\\ \bullet\\ \vdots\\ \bullet\\ \downarrow \end{array} $$ 的树. 这给出单纯形范畴到树的范畴的嵌入 $$ \Delta \hookrightarrow \Omega. $$