【离散数学】树（三）树的同构

正文之前

在之前的【离散数学】图论中谈到过图的同构，今天我们来谈谈树的同构：

同构树
同构有根树
同构二叉树

正文

同构树

1. 简介

T₁和T₂为同构树，当且仅当存在一个从T₁的结点到T₂的结点的一对一的映上函数 f (one - to - one and onto function f )

简而言之，如果T₁和T₂为同构树，在T₁中结点 v 和 w 相邻，则在T₂中的结点 f (v) 和 f(w) 也相邻

上图中：

• a - A
• b - B
• c - C
• d - D
• e - E

2. 判断

如果T₁中某些特性没有表明在T₂中，就能够表明两棵树不同构

T₁中有度数为2，3的结点，而T₂中没有，所以T₁和T₂不同构

同构有根树

1. 简介

同构有根树的条件是基于同构树之上的：

T₁的结点到T₂的结点的一对一的映上函数 f (one - to - one and onto function f )

还必须保持根结点的一致性

也就是说，如果T₁的根结点为 v ，则T₂的根结点为 f(v)

若 v₁ 为T₁的根结点， v₂ 为T₂的根结点，所以T₁和T₂同构需满足

1. T₁中结点 v 和 w 相邻，则T₂中的结点 f (v) 和 f(w) 也相邻
2. f(v₁) = v₂

上图中：(注意下标）

• v₁ - w₁
• v₂ - w₃
• v₃ - w₄
• v₄ - w₂
• v₅ - w₆
• v₆ - w₇
• v₇ - w₅

2. 判断

同构有根树的判断和同构树的判断相同，只需要找一些不同的特性

上图中，T₁的根结点的度为4，而T₂的根结点的度为3，所以两树不同构

同构二叉树

1. 简介

同构二叉树的条件是基于同构有根树之上的：

不仅需要保持结点的相邻关系和根的一致性，还需要保持左右子节点的一致性

若T₁是根结点为 v₁ 的二叉树，T₂是根结点为 v₂ 的二叉树，所以T₁和T₂同构需满足：

1. T₁中结点 v 和 w 相邻，则T₂中的结点 f (v) 和 f(w) 也相邻
2. f(v₁) = v₂
3. v_i 是T₁中结点 v 的左子节点，则 f(v_i) 是T₁中结点 f(v) 的左子节点
4. v_j 是T₁中结点 v 的右子节点，则 f(v_j) 是T₁中结点 f(v) 的右子节点

上图中，T₁和T₂同构，T₁和T₃不同构：

• v₁ - w₁
• v₂ - w₂
• v₃ - w₃
• v₄ - w₄
• v₅ - w₅
• v₆ - w₆

2. 判断

同构二叉树的判断如同上述，只需要找一些不同的特性

以上图来说，T₁中，v₃没有右子节点，而在T₃中，a₃却有右子节点，所以两树不同构

划重点

对于两棵树是否同构，需要分情况来判断：

对于上图中两棵树，作为二叉树，两棵树不同构，但是，作为有根树或自由树，这两棵树是同构的

关于树的同构就介绍到此了，谢谢！