为什么要给树编码
在顶点集 上,一共有多少棵树?当 时,答案是三棵:三个顶点的树只能是一条路径,而确定中间顶点就确定了整棵树。当 时,树有两种形状:路径和星形。标号路径共有 条,因为把顶点排列的顺序反过来,得到的仍是同一条路径;标号星形共有 棵,每一种中心顶点对应一棵。因此总数是 。从 、,我们会猜想一般的答案是 。
逐一列出树的形状再计数,很快就会变得难以实行:形状越来越多,而且每种形状都有各自的对称性。更有效的方法是建立一个双射。 正好是以 为取值集合、长度为 的序列数。因此,我们希望有一条规则把每棵标号树变成这样的序列,再有另一条规则把每个这样的序列变回树,并且两条规则恰好互相还原。Prüfer 编码正是这样的一对规则。本节的核心不是记住算法步骤,而是证明两个算法互为逆运算。证明的关键在于:编码记录了树中每个顶点的度数。
定义与算法
定义 1.5.1
(标号树与叶)
设 是由正整数组成的有限集合。 上的标号树,是以 为顶点集的连通无圈简单无向图。本节主要考虑 。不过,算法会不断删除顶点,剩余顶点的标号不一定从一开始连续排列,因此也允许任意这样的 ,并沿用整数本身的大小次序。两棵标号树相等,是指它们的边集相同;这比图同构要求更严格。
度数为 的顶点称为叶。单顶点树的唯一顶点度数为 ,所以它没有叶。因此,下面两个算法都要求 ,而 的情况另行处理。
我们将用到一棵有 个顶点的树 的三个基本事实:
- 恰有 条边,所以 。
- 至少有两片叶。取一条最长路径即可看出:端点在路径外不能有邻点,否则可以延长路径;在路径上也不能有另一个邻点,否则会形成圈。
- 若 是叶,则 是 上的一棵树。删除一个度为一的顶点,既不会产生圈,也不会使其余顶点之间失去连通性。
对有限序列 和数值 ,用 表示 中等于 的项数,用 表示 中出现过的数值所组成的集合。
定义 1.5.2
(Prüfer 编码算法)
设 是顶点集为 的树,。令 。对 ,依次执行:
- 取 中标号最小的叶,记为 ;
- 记录它唯一的邻点 ;
- 令 。
输出序列为 。
定义 1.5.3
(Prüfer 解码算法)
设 的每一项都属于 ,且 。令 ,并用 表示尚未处理的后缀。对 ,依次执行:
- 取 ;
- 添加边 ;
- 令 ,并从后缀中删去首项 。
当后缀为空时,在 剩下的两个标号之间添加一条边。输出的图记为 。
两个算法都是递归的:编码算法完成第一步后,其余过程与对 编码相同;解码算法完成第一步后,其余过程与在 上对 解码相同。
编码算法的每一步都有定义
引理 1.5.4
(编码器不变量)
对每个 , 都是有 个顶点的树。因此算法的每一步都能执行, 的长度恰为 ,而最后的 只是一条边。
证明
(对删除次数归纳)
对 作归纳。当 时,由 ,结论成立。假设 是有 个顶点的树,其中 。此时 ,所以由基本事实 2,图中有叶。因此,标号最小的叶 确定存在,它唯一的邻点 也确定存在。由基本事实 3,删去该叶后, 是有 个顶点的树。
循环恰好执行 次,每次记录一项,所以编码长度为 。最终的树有两个顶点,因此只能由连接它们的一条边组成。
定理 1.5.5
(编码记录度数)
对每个顶点 ,都有
特别地, 的叶恰好是 中没有出现在 里的顶点。
证明
(计算一个顶点处的边)
第 步恰好删除一条边,即 。最后一步完成后只剩下一条边。因此, 中每条边要么在某个唯一的步骤被删除,要么就是最后留下的边。
固定顶点 ,考察 中所有与它关联的边。分两种情况。
情况 1:存在某个 ,使 。 第 步开始时, 是 的叶,所以与它关联的原有边中,恰有一条保留到了这一步。这条边在第 步被删除;但这一步中 是被删除的叶,而不是被记录的邻点。其余 条关联边,都已在更早的步骤 被删除。在每个这样的步骤中, 仍在图中,因此被删除的叶 不是 。所以,被删除的边 与 关联,当且仅当 。反过来,每个满足 的步骤 ,也确实删除了一条与 关联的边。第 步之后, 已被删除,不可能再出现在记录中。故 。
情况 2: 是最后剩下的两个顶点之一。 在 中的度数为 。同样的计数说明,它原有的关联边中,恰有 条在记录 的步骤中被删除。
最后,由 当且仅当 ,就得到关于叶的结论。
度数记录定理也适用于 ,其编码就是后缀 。因此 的叶恰是仍在树中、却不在剩余后缀中出现的顶点,这正是解码算法的选择规则。
解码算法的每一步都有定义,且输出一棵树
引理 1.5.6
(解码器不变量)
对每个 ,在第 步开始前,都有:
- (I1) ;
- (I2) 的每一项都属于 。
因此:
- (a) 可选的标号 一定存在;
- (b) 且 ,所以不会产生自环;
- (c) ,即作为邻点的标号在本步之后仍然保留。
最后, 有两个不同的元素。 中每个标号,要么恰好一次作为某个 被移除,要么属于最后的一对标号。 有 条边。
证明
(对解码步骤归纳)
当 时,两个不变量都成立:,且 的所有项都属于 。
假设第 步开始前 (I1) 和 (I2) 成立。后缀 有 项,所以它包含的不同标号至多有 个。而 ,因此 中一定有标号没有出现在后缀里,(a) 得证。
由 (I2), 属于 。选择 时要求它不在 中,而 正是这个后缀的第一项,因此 。这证明了 (b),也随即得到 (c)。
再检查不变量能否保持。移除一个标号后,。 的每一项原本都在 中,所以都属于 ;它们也都不等于 ,因此都属于 。
标号只有被选为 时才会离开 ,离开后不会重新加入,所以没有标号会被选择两次。移除 个标号后,恰好剩下两个,再用最后一条边连接它们。解码算法在循环中添加 条边,最后再添加一条,共得到 条边。
定理 1.5.7
(解码器输出一棵树)
是顶点集为 的标号树。
证明
(逐个接上顶点的向下归纳)
对 ,定义 为顶点集 上的图,其边为最后添加的边,以及所有满足 的边 。这些边的端点确实都在 中:若 ,则 和 都属于 。
只有一条边,是一棵树。由 得到 ,只需添上新顶点 和一条边 ,其中由解码器不变量引理的 (c) 知 。把一个新顶点以一条边接到树上,所得图仍是一棵树。因此,从 向下归纳可知, 是顶点集 上的一棵树。
解码得到的树,其度数同样由序列决定。我们可以只用解码算法本身证明这一点,不必借助编码算法。
引理 1.5.8
(解码所得度数)
在 中,每个 都满足 。
证明
(计算解码后一个顶点处的边)
的边为各条 及最后添加的边。这些边两两不同:若 ,则较早被移除的标号 已经不在 中,而较晚的边的两个端点都在 中,所以较晚的边不可能等于含有 的那条较早的边。最后添加的边,其两个端点也都在 中,因此也不同于那条较早的边。
边 与 关联,当且仅当 或 ;由解码器不变量引理的 (b),这两种情况不会同时发生。每个满足 的下标 ,都贡献一条与 关联的边。
除此以外,下列两种情况恰有一种发生:或者存在唯一的 使 ,或者 是最后的一对标号之一。无论哪种情况,都恰好再贡献一条与 关联的边。
编码与解码互为逆运算
定理 1.5.9
(编码与解码互逆)
对任意有限集 ,若 ,则:
- 对 上的每棵树 ,都有 ;
- 对每个序列 ,都有 。
证明
(对顶点数归纳)
两部分都对 作归纳,并且同时考虑所有大小为 的顶点集。
当 时,唯一的序列是空序列, 上唯一的树是连接两个顶点的那条边。解码算法直接连接两个标号,所以两个等式都成立。
现在设 。
第一部分。 令 。由度数记录定理, 就是 的叶集。因此,解码算法第一步选出的 ,并添加边 ;这确实是 的一条边。
余下的解码过程,是在 上对 解码。根据编码算法的定义,这个序列正是 。由归纳假设,余下的解码过程得到 。所以
第二部分。 令 。由解码度数引理, 的叶恰好组成集合 ,所以标号最小的叶是 。 包含边 ,而 是叶,因此编码算法第一步记录的就是 。
删除 时,只会删去边 。余下的图,恰好是在 上对序列 解码所得的图。由归纳假设,对这个图编码就得到 。因此 。
证明透视
各部分只用自己一方的事实
证明对每个算法只需一个事实,每部分只用自己的那个。第一部分用度数记录定理(只关于 的陈述)说明解码的第一个选择 就是编码第一次删除的 ;第二部分用解码度数引理(只关于 的陈述)说明编码第一次删除的是 。两部分都没有假设正要证明的恒等式,所以论证不是循环的。
两部分的关键一步相同:树的叶恰是不在其编码中出现的标号,所以“最小的缺席标号”与“最小的叶”选出同一个顶点。一步之后,每个算法都在 或 上继续;这是一个大小为 、通常不再是整数起始段的集合,因此归纳要同时对所有同样大小的顶点集进行,并由基础情形 收尾。
Cayley 公式与指定度数的计数
定理 1.5.10
(Cayley 公式)
对 ,顶点集 上的标号树共有 棵。当 时,公式给出 ,即只有边 这一棵树。当 时,也恰有一棵树:顶点集为 的无边图;它连通且无圈。
由互逆定理, 上的树与集合 之间存在双射,而后者有 个元素。 的情况是直接观察得出的,不是由这个计数论证得到的。上述编码论证不适用于 ,因为序列的长度不可能为 ,编码算法在这个情形下也没有定义。
定理 1.5.11
(指定度数的树)
设 ,且 都是整数。若每个 ,并且 ,则在 上满足每个顶点的度数均为 的树,其数目为
否则,数目为 。
由度数记录定理和互逆定理,这样的树与长度为 、其中每个标号 恰好出现 次的序列一一对应。规定的各个重数之和恰好为
因此,这些序列的排列数就是上述多项式系数。若有 ,则不可能是顶点的度数,因为图的度数不会为负。若有 ,则顶点 是孤立点,这与 时图的连通性矛盾。若度数之和不对,则违背基本事实 1。这些情况下都不存在满足条件的树。
例题详解
例题 1.5.12
(星形树与路径)
星形。 设 是 上以 为中心的星形树,其中 。除 外,每个顶点都是叶;不断删除叶的过程中, 仍是中心。因此,每一步记录的邻点都是 ,所以
共有 项。这与度数记录定理一致,因为 。
路径。 考虑路径 。标号最小的叶总是当前的左端点,因此编码为 。
再考虑重新标号后的路径 。它的叶是 和 。先删除 ,记录 ;此时 成为叶,删除 后记录 。所以它的编码为 ,而路径 的编码为 。两棵树同构,但它们是不同的标号树,编码也不同。
例题 1.5.13
(编码七个顶点的树)
设 的边为 。其度数为 、,其余顶点的度数均为 。
| 步骤 | 当前的叶 | 删除的顶点 | 记录的邻点 |
|---|---|---|---|
| 1 | |||
| 2 | |||
| 3 | |||
| 4 | |||
| 5 |
最后剩下顶点 和 。编码为 。正如度数记录定理所预言的, 和 各出现两次, 出现一次,原树的叶一次也不出现。
例题 1.5.14
(解码序列)
在顶点集 上,对序列 解码。
| 步骤 | 剩余标号 | 剩余后缀 | 未出现在后缀中的标号 | 新边 |
|---|---|---|---|---|
| 1 | ||||
| 2 | ||||
| 3 | ||||
| 4 | ||||
| 5 |
最后添加的边为 。输出的图有六条边:。
注意第 4 步:只有当序列中的两个 都已离开剩余后缀之后,标号 才能被选中。为了核对结果,可以对所得树重新编码。依次删除的顶点为 ,记录的邻点依次为 ,恰好还原了 。
反例与适用范围
反例模式
改变选择叶的规则
对于路径 ,选择“标号最小的叶”得到编码 。若改成选择“标号最大的叶”,则第一步删除 ,得到编码 。若只说“任取一片叶”,甚至不能定义一个函数,因为同一棵树可能得到这两个不同的编码。双射依赖于明确的选择规则,也依赖于标号的大小次序。
这个计数同样只属于完全图:它枚举的是 的生成树,而不是其他图的生成树。
反例模式
其他图的生成树
Cayley 公式计算的是完全图 的生成树数目。边集为 的四顶点圈恰有 棵生成树,而不是 棵。在顶点集 上对序列 解码,得到边 、 和 。但 并不是这个圈的边。因此,Prüfer 解码不是枚举一般图的生成树的算法。
常见错误
常见错误
(检查整个原序列中是否出现过某标号)
解码时必须检查标号是否出现在剩余后缀中。在解码例题中,标号 虽然出现在原序列中,但在第 4 步、两个 都离开后缀之后,它仍被正确选取。
常见错误
(数形状而不是数标号树)
上有 棵标号树,但忽略标号后只有两种形状,即路径和星形。公式 计算的不是同构意义下的树,Prüfer 编码也不是形状的不变量:同构的路径 与 的编码分别是 与 。
最后,两个算法并不是因为“看起来可逆”就互逆:没有度数记录定理和解码度数引理,就没有理由认定解码的第一次选择与编码的第一次删除一致。
练习
快速检查
(设 ,且 。求 上顶点 的度数为 的标号树数目。)
解答
由度数记录定理和互逆定理,我们要计算的是 中恰有 项等于 的序列数。先选出这些项的位置,有 种选法;再在其余 个位置上,各填入标号 中的一个,每个位置有 种选择。因此总数为
范围 是准确的。连通性要求 ,而编码中出现的次数满足 ,给出上界。底数 至少为 ,所以指数为 时,这个因子确实等于 。当 时,唯一可能是 ,计数为 ,对应唯一的一条边。
作为核对,取 。 分别得到 、 和 ,并且 。一般地,由二项式定理,
快速检查
(设 是 上边集为 的树。求 ,再对结果解码,核对是否还原了 。)
解答
编码。 最初的叶为 。各步如下:
- 删除 ,记录 ;此时 成为叶;
- 删除 ,记录 ;
- 删除 ,记录 ;此时 成为叶;
- 删除 ,记录 ;此时 成为叶;
- 删除 ,记录 ;此时 成为叶;
- 删除 ,记录 。
最后剩下顶点 和 。因此编码为 ,长度为 。唯一一个度数为 的顶点是 ,它在编码中恰好出现两次。
解码。 剩余标号中未出现在当前后缀里的集合依次为:
- ,添加边 ;
- ,添加边 ;
- ,添加边 ;
- ,添加边 ;
- ,添加边 ;
- ,添加边 。
最后添加边 。这七条边恰好就是 的全部边。
快速检查
(列出 及 上的所有标号树,并写出它们的编码。在 上对 解码。)
解答
上只有一棵树,即边 ,编码为空。这与 相符。
上每棵树都是一条路径,其中间顶点可记为 。中间顶点度数为 ,另外两个顶点都是叶,因此编码为 。三棵树的编码分别是 、 和 ,与 相符。
在 上对 解码:未出现在后缀里的标号为 和 ,所以先连接 与 ,剩余标号为 。最后添加边 。所得路径是 ,中间顶点确实为 。
快速检查
(求 上度数序列为 的标号树数目。解释为什么 上不存在度数序列为 的树。)
解答
所有度数都至少为 ,且总和为 ,所以可用指定度数定理:
第二个序列的度数和是 ,所以树的数目为 。
快速检查
(利用指定度数定理,证明对 , 上共有 条标号路径。)
解答
一棵树是路径,当且仅当它有两个度为 的顶点,其余顶点的度数都为 。选取两个端点有 种方式。对每一种选法,由指定度数定理得到的树数为
所以总数为 。
这与前面的计数一致:当 时得到 ;当 时得到 ,与开头的结果相同;当 时得到 。
相关内容
先修知识包括树、叶以及树的边数公式 。本节引向指定度数序列的枚举,以及一般图的生成树计数。对于一般图,必须使用 Prüfer 编码以外的方法。