[音乐]
[音乐] [音乐]
大家好,本次讲解有根树同构的相关性质
首先我们回忆一下一般的树。
一般树说它是一个连通的无环图 而在树中,有一类特殊的节点也就是度数为 1
的节点,我们把它叫做树的叶子节点 那什么是有根树?有根树是一个二元组
一个有序二元组,其中 T 就是一棵树,而 r
是树中的一个节点 我们把 r 叫做整棵树的根。
在图中呢用向下 的箭头表示出来。
在右边这个图中,大家可以看到最下面这个节点就是整棵树的根 一旦定了根之后,我们就可以定义两个节点之间的关系
我们说一条边 (x,y),如果说
x 是出现在从根 小 r 到 y 的这个路径上
那么我们说 x 是 y 的父亲,相应的我们称 y 是 x 的儿子节点。
注意我们这里从 r 到 y 的路径只有唯一的一条 这是从树的等价定义中得到的
那么我们同样回忆一下图同构问题 什么是图同构?图同构是说我们有两个图
G 和 G' 同构是说存在这样一个结点之间的双射函数,它为保持了边之间的对应关系
就是下面是两个例子,就左边这个环和右边这个五角星它们是同构的
我们想说的是呢,一般的图之间的同构问题到目前为止还没有有效的算法
但是我们想,本次课想讲的是有根树之间的同构问题 有快速算法,当然我们需要先定义一下什么是有根树之间的同构
我们定义有根树之间的同构是说给了两棵 有根树分别是两个二元组 (T,
r) 和 (T', r') 它的要求首先 f 是两棵树的节点之间的一个双射关系
并且保持了边的一一对应,也就是这里的第一条 在 f 关系下 T 和 T' 同构
此外,它还有第二条就是说第一棵树的根将会被映射到第二棵树的根 可以看到有根树的同构的定义比
一般的图同构的定义要强,因为它多了一条要求 我们看一下这种强在有的时候是严格地强的
比如说现在这个例子中,这两个都是含有五个节点的 路径,所以说它们在图同构的意义下,它们显然是同构的
但是如果我们现在选取第一棵树的根为这个路径中的第三个节点 而第二个路径的根为从左数的第四个节点。
我们可以看到它这个时候就不再同构了。
因为 如果我们把我们要求 r 映射到了 r'
的话 那么这个函数余下的部分不再是一个双射函数。
换句话讲我们说 有根树的同构这个定义是严格地强于一般的图同构关系
好了,我们本次呢就要讲有根树同构的 这个判定算法。
我们整个这个思路呢是想把树的同 树的比较转化为字符串的比较。
这里我们会用到我们之前讲过的一个 重要的序关系是字典序。
但这里的字典序和我们在序论中所讲的字典序略有不同 大家记得在我们在序论中讲字典序是两个
n 原串之间的字典序,而这个时候我们 把这个序关系做一个扩展。
我们现在是任给了两个不同的序列 S 和 T,注意这里 S
和 T 的长度可能不同,S 中含有 n 个字符,而 T 中含有 m 个字符
那么如果第一种情况是说 S 是 T 的初始序列,也就是说
T 能够写成 S 接上一个后缀的形式 那么我们定义 S 是小于 T 的。
反过来,如果说 T 是 S 的初始序列 也就是说 T 是 S 的一个前缀的话,那么我们规定
T 小于 S 如果这两种情况都不成立,那么我们知道必然存在一个位置小 i si 和 ti 不相等。
那么我们取 si 和 ti 不相等的最小的那个下标 我们看一下是
si 和 ti 的关系,如果 si 比 ti 小的话,那么我们规定
s 小于 t 如果 si 大于 ti 那么我们规定
s 大于 t,这就是我们的一般的这样一个字典序
我们看两个例子,第一个说 00 是小于 001 的,因为显然
00 是 001 的一个前缀 而在第二个例子中,我们说第一个是一个
五长的串而第二个是一个四长的串,但它们第一个不同的位置在于第三个位置 左边是
0 右边是 1,那么 0 是小于 1 的,所以我们说第一个串
它在字典序下是小于第二个串,而这个串的比较 就将是我们用来做有根树比较的一个重要的工具
为了用串的比较来做有根树的比较,我们将会对有根树做编码
编码的思路呢,是一共有两条规则
我们对这个下面第一张图中的这棵树,我们首先对所有非根 的叶节点都赋值为 01。
大家可以看到在第二张图中,我赋好了所有的叶子节点 注意是所有的非根叶节点。
一旦非根的叶节点做好之后,我就开始处理其他的内部节点 我现在假设这个节点小
v 它的儿子节点 是 w1,w2,一直到
wk,就是假设它都已经 完成赋值并且第 wi
号节点的 赋值是 A(wi),因为它们现在是二进制串,所以我们可以用
字典序去比较,假设说 A(w1) 小于 等于
A(w2) 小于一直小到 A(wk) ,也就是一个不会递减的一个序的话 那么我们对
v 节点怎么赋值呢?我们是在 v 节点两头写上
01 然后中间按照儿子节点的编码,不递减
的这样一个顺序写成 A(w1)、 A(w2) 一直到 A(wk) 这样一个
在图中,我们可以看到这个蓝色的点就被赋值为 0、 01、 01、
1 因为它的两个儿子节点都是 01,是一样的。
我们反复地运用 R2 去处理所有的 所有的非叶子节点,直到最后我们处理到根节点
大家可以看,我们说根节点最后的编码就是整 棵树,我们就把它认为是整棵有根树的这样一个编码
大家可以看到,在第四张图中,最后这个节点、 最下面这个节点
R 节点,它的编码是多少呢?它首先有三个儿子,分别是编码为
01、 001 011 以及 01。
我们当然是会选用儿子节点的 编码不递减的这样一个序,所以说,首先是它中间第二个儿子的
就现在这个图中第二个儿子的编码,接着是左右两个儿子的编码,然后再两头再加上
0 大家可以看到,任给一棵有根树呢,我们都可以用
这个编码方案,给出它的整棵有根树的这样一个编码
关于这个编码一个最重要的性质是说 这里给了 (T,r) 和 (T', R')。
它们两个在有 根树同构意义下相等,当且仅当它们具有相同的编码
这个编码的正确性的证明首先是证明充分性
就是说两棵树有根树同构,意义下同构 那么它一定有相同的编码,这里我没有给出所有的细节,大家可以根据那个
有根树同构的定义,以及那个编码的构造去一步一步地验证
这里稍微着重讲一下的是那个
必要性,也就是说,如果具有相同的编码那么它们是有根树 同构意义下相等的。
而这个必要性的证明比较有意思的一点,它其实就是
一个解码的过程,就是说我给了你这样一个编码,我如何恢复出原始的这个有根树
我们说,你任意给一个有根树的编码,根据我们的编码构造,它必然是 0S1 是 1 这样的一般、 一般的这样一个形式。
大家会还记得在根那个节点的话,它是把所有儿子节点的编码 按照一个序排好,然后再两头加上
01,所以中间一定是一个大 S 那大 S 是什么呢?大 S 会对应它的
T 个儿子结点的编码,所以分别是 S1、 S2、 St 那么 S1、 S2、 St
分别又是什么呢? S1 就会是 S 中 01 个数相等的最小的一个前缀
这是把我们刚才的编码反过来看,就是我们有了这个编码之后,我们去观察 S1
必然是它之后的,它的儿子节点的编码而且它的 01 个数一定是相等。
类似地,我们可以知道 S2 是第二个 01 平衡的最小的前缀等等 然后我们对 S1 再做解码,对
S2 再做解码,一直恢复到所有的叶子节点 这样一个过程重复呢,我们就可以恢复出整个的有根树
并且显然这个同一个编码一定会恢复出同构的有根树
我们看一个例子来增强我们对刚才解码过程的一个 一个认识。
我们给了这样的一个 01 字符串 我们说了,首先把它分成 0 S 1。
那么 两头是 0 和 1,中间就是 S 的部分,然后我们再去看 S 分解成 S1、 S2 一直到 St。
S1 是什么呢?是 01 相等的最小的 前缀。
这里我用红色的括号,用两个红色的括号表示出来,这是第一部分 然后剩下的是第二部分。
接着我们对第一个前缀再进行不断地分解 一直分解到最后的
01 的这个,是对叶子节点的、 对非根叶子节点的这样一个编码
还有一个更直观的方法,就是从编码恢复树,一个更直观的方法是什么呢?我们遇到 0
的时候 我们试一个画箭头的画法,遇到 0 就朝上画走一步
再遇到 0,再朝上走一步,遇到 1 的时候,朝下走一步
大家可以看,我们现在这个方法是,比如说在这个例子中,我们是先 有 5
个 0,所以我们朝上走了 5 步,然后再 朝下走了两步,接着顺序地画完。
我们把整个画好之后,大家可以 容易地验证,其实这个就给出了我们
原始的有根树的这样一个样子 好了,总结一下本次课的主要内容。
本次课介绍了 有根树的定义,并且得到一个最重要的性质是,在我们的编码方案下两棵有根树同构
当且仅当它们具有相同的编码,并且
根据这个编码,我们就可以迅速地得到有根树同构
存在有效的判定算法这样一个结论,因为我们只需要去判断它们所 产生的编码是否相等即可。
好了,这就是本次课的主要内容,谢谢大家!
[音乐]