离散数学是计算机专业基础课程之一。本课程重点讲解离散对象的计数问题、图论问题、网络流问题等计算机科学中的重要基本知识。本课程将为后续如数据结构、算法设计、复杂性理论提供必要的基础，课程内容在人工智能、机器学习、网络设计与分析等前沿领域有重要应用。课程重点培养学生逻辑思维能力及解决问题的能力。
有根树同构的判定
Loading...
來自 Shanghai Jiao Tong University 的課程
离散数学
15 個評分
[音乐]
[音乐] [音乐]
大家好，本次讲解有根树同构的相关性质
首先我们回忆一下一般的树。
一般树说它是一个连通的无环图 而在树中，有一类特殊的节点也就是度数为 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 步，然后再 朝下走了两步，接着顺序地画完。
我们把整个画好之后，大家可以 容易地验证，其实这个就给出了我们
原始的有根树的这样一个样子 好了，总结一下本次课的主要内容。
本次课介绍了 有根树的定义，并且得到一个最重要的性质是，在我们的编码方案下两棵有根树同构
当且仅当它们具有相同的编码，并且
根据这个编码，我们就可以迅速地得到有根树同构
存在有效的判定算法这样一个结论，因为我们只需要去判断它们所 产生的编码是否相等即可。
好了，这就是本次课的主要内容，谢谢大家！
[音乐]
