和谐森林的特性与标签构建

### 和谐森林的特性与标签构建 #### 1. 引言 在图论中，森林的和谐性是一个重要的研究课题。本文将探讨森林的一些特性，包括特定类型森林的不和谐性、树的双构造方法、树和森林的标签构建等内容，旨在对和谐森林进行全面的刻画。 #### 2. (4k + 2)-奇森林的不和谐性 引理 1 指出，对于所有 $k \geq 0$，(4k + 2)-奇森林不是和谐的。 证明过程如下： 设 $F$ 是一个具有 $n$ 个顶点和 $m$ 条边的 (4k + 2)-奇森林。因为 $F$ 有 $4k + 2$ 个组件，所以 $n - m = 4k + 2$。通过一系列等式推导： $n - m = 4k + 2$ $n - m + 2m = 4k + 2 + 2m$ $n + m = 2(2k) + 2 + 2m$ $n + m = 2(2k + m) + 2$ $n + m = 2(2k') + 2$ $n + m = 4k' + 2$ 由于 $k'$ 是整数，可得出 $n + m$ 模 4 同余于 2。根据定理 2，$F$ 不是和谐的。 #### 3. 树的双构造 本部分提供了一种不寻常的树的归纳定义，这种方法在尽可能公平地标记顶点和边时非常有用。双构造依赖于两种双添加操作： - 双叶添加 leaf(x, y, z)：将 $y$ 和 $z$ 以及边 $xy$ 和 $xz$ 添加到树 $T$ 中。 - 双路径添加 path(x, y, z)：将 $y$ 和 $z$ 以及边 $xy$ 和 $yz$ 添加到树 $T$ 中。 非空树 $T$ 的双构造是一系列双添加操作，从一个基顶点或基边开始创建 $T$。定理 3 证明了每个非空树都可以通过这种方式构建。 证明过程： 如果 $T$ 有一个或两个顶点，那么它分别是基顶点或基边。否则，考虑 $T$ 中的一条最长路径，其一端的倒数第三个、倒数第二个和最后一个顶点分别为 $u$、$v$ 和 $w$。根据 $v$ 的度分为两种情况： - 若 $v$ 的度为 2，则 $T = T' + path(u, v, w)$ ，其中 $T'$ 是某个树。 - 若 $v$ 的度至少为 3，由于 $w$ 是最长路径的端点，存在至少一个与 $v$ 相邻的叶子 $x \neq u$，则 $T = T' + leaf(v, w, x)$ 。 在这两种情况下，$T'$ 的顶点数都比 $T$ 少两个，通过对树的顶点数进行归纳可得出结论。 根据树的顶点数的奇偶性，定义了偶树（顶点数为偶数的树）和奇树（顶点数为奇数的树）。并且有如下结论： - 树 $T$ 是奇树当且仅当其双构造从基顶点开始。 - 树 $T$ 是偶树当且仅当其双构造从基边开始。 此外，还定义了奇度树（每个顶点的度都是奇数的树），定理 4 表明，树是奇度树当且仅当它是偶树且其双构造仅使用双叶添加。 引理 2 指出，对于偶树的任何双构造，树的偶分割边是通过双路径添加 path(u, v, w) 为某个顶点 $w$ 添加的边 (u, v)。 推论 1 表明，偶树 $T$ 是奇度树当且仅当 $T$ 没有偶分割边。 对