樹同構

樹同構(Tree Isomorphism)描述的是圖論中，兩個樹之間的完全等價關係。在圖論的觀點下，兩個同構的樹可以被當作同一個圖來研究。

定義

樹同構的概念源於圖同構。圖同構的概念為，兩個簡單圖 $G$ 和 $H$ 稱為是同構的，若且唯若存在一個將 $G$ 的節點 $1,\ldots ,n$ 映射到 $H$ 的節點 $1,\ldots ,n$ 的一一對應 $\sigma$ ，使得 $G$ 中任意兩個節點 $i$ 和 $j$ 相連接，若且唯若 $H$ 中對應的兩個節點 $\sigma (i)$ 和 $\sigma (j)$ 相連接。樹同構即在以上定義中增加 $G$ 和 $H$ 都是樹的限制條件。兩顆樹 $T_{1},T_{2}$ 同構可以記作 $T_{1}\simeq T_{2}$ 。

在此基礎上，定義有根樹及其同構的概念^[1]。有根樹可表示為(T,r)，其中T表示一棵樹， $r\in V(T)$ 是一個有特殊標記的點，稱為樹的根結點。對於邊 $xy\in E(T)$ ，若x在根結點到y的路徑上，稱x為y的父結點，y為x的子結點。有根樹的表示形式可以為「種植的樹」，即根節點r標有向下箭頭；所有結點的子節點都畫在該點上方。

有根樹同構的定義為，對於兩顆有根樹 $(T_{1},r_{1})$ ， $(T_{2},r_{2})$ ，存在一個同構映射 $f$ ，其中 $f(r_{1})=r_{2}$ 。 $(T_{1},r_{1})$ 與 $(T_{2},r_{2})$ 同構可記作 $(T_{1},r_{1})\simeq (T_{2},r_{2})$ 。

由以上定義可知，有根樹同構的關係嚴格強於樹同構的關係。

有根樹同構判定算法

有根樹同構的判定問題是P問題（P/NP問題）。這裏介紹其中一種算法，該算法將有根樹的比較轉化為字符串的比較。

有根樹的0-1編碼

對有根樹進行0-1編碼，並且採用字典序對編碼進行比較。字典序的比較方法為：對不同序列 $s=s_{1}s_{2}\dots s_{n}$ 和 $t=t_{1}t_{2}\dots t_{m}$ ：

如果 $s$ 是 $t$ 的初始序列（即 $t=st_{i}\dots t_{m}$ ），則 $s<t$ ;
如果 $t$ 是 $s$ 的初始序列（即 $s=ts_{i}\dots s_{n}$ ），則 $t<s$ ;
令 $i$ 是 $s_{i}\neq t_{i}$ 的最小下標，若 $s_{i}<t_{i}$ 則 $s<t$ ，若 $t_{i}<s_{i}$ 則 $t<s$ 。

例： $00<001$ , $01{\textbf {0}}11<01{\textbf {1}}0$ 。

對有根樹(T,r)進行如下編碼：

所有非根葉結點都賦值為01；
假設點v的子結點 $w_{1},w_{2},\dots ,w_{k}$ 都已經完成編碼，編碼為 $A(w_{1}),A(w_{2}),\dots ,A(w_{k})$ ，且有 $A(w_{1})\leq A(w_{2})\leq \dots \leq A(w_{k})$ ，則v結點的編碼 $A(v)=0A(w_{1})A(w_{2})\dots A(w_{k})1$

如此遞歸。r結點的編碼 $A(r)$ 即為該有根樹的編碼，用 $\#(T,r)$ 表示。

若 $\#(T_{1},r_{1})=\#(T_{2},r_{2})$ ，則說明有根樹 $(T_{1},r_{1})$ 與 $(T_{2},r_{2})$ 同構。

判定定理的簡單證明

該算法的判定定理是： $(T_{1},r_{1})\simeq (T_{2},r_{2})$ 若且唯若他們具有相同的0-1編碼。對該定理進行如下簡單證明：

充分性：從有根樹同構的定義和編碼過程可證。
必要性：對編碼進行解碼。任意有根樹的編碼必然有 $0S1$ 的一般形式，其中 $S=S_{1}S_{2}\dots S_{t}$ 。 $S_{1}$ 是 $S$ 中0,1個數相等的最小前綴， $S_{2}$ 是第二個0,1平衡的最小前綴，以此類推，可以解碼出唯一形態的有根樹。這棵有根樹的其他表示形式都與該解碼形式同構。