树同构判定
树同构判定
图同构与树同构
同的同构问题还没有有效算法。
树的同构本质上寻找不同树之间的双射关系。
通过对树编码，将树的同构问题转化为编码比较问题。
有根树的同构严格强于图同构关系。
如上，图同构的两张图转化成树，如果选取的根不同，则树不同构。
如何选取根？
概念定义：
-
dis(v1, v2)表示v1到v2点的距离
-
ex(v), 偏心率， ex(v)保存树中距离v最远的点的距离。
ex(v1) = max(dis(v1, vk)) , k = 1 → n
-
C(T), 成为中心，表示图中偏心率最小的点集合。
一种重要性质
对于一个树来说(对于图不成立)，他的中心最多含有两个点，且若含有两个点，这两个点必定相邻。
所以，寻找一个树的中心，只需要迭代地删掉叶子节点，最后剩下的单个节点或者两个节点就是树的中心。
树的编码（有根树的同构判定）
将树转换字符串，但是通过比较字符串的字典序来比较两个编码的大小关系。
字典序比较规则：
编码方法
采用如上编码方案，两个树只有编码相同的时候才会同构。
reference
https://zh.coursera.org/lecture/discrete-mathematics-ch/you-gen-shu-tong-gou-de-pan-ding-NAxTd
