樹同構(Tree Isomorphism)描述的是圖論中,兩個樹之間的完全等價關係。在圖論的觀點下,兩個同構的樹可以被當作同一個圖來研究。
樹同構的概念源於圖同構。圖同構的概念為,兩個簡單圖 和 稱為是同構的,若且唯若存在一個將 的節點 映射到 的節點 的一一對應 ,使得 中任意兩個節點 和 相連接,若且唯若 中對應的兩個節點 和 相連接。樹同構即在以上定義中增加 和 都是樹的限制條件。兩顆樹 同構可以記作 。
在此基礎上,定義有根樹及其同構的概念[1]。有根樹可表示為(T,r),其中T表示一棵樹, 是一個有特殊標記的點,稱為樹的根結點。對於邊 ,若x在根結點到y的路徑上,稱x為y的父結點,y為x的子結點。有根樹的表示形式可以為「種植的樹」,即根節點r標有向下箭頭;所有結點的子節點都畫在該點上方。
有根樹同構的定義為,對於兩顆有根樹 , ,存在一個同構映射 ,其中 。 與 同構可記作 。
由以上定義可知,有根樹同構的關係嚴格強於樹同構的關係。
有根樹同構的判定問題是P問題(P/NP問題)。這裏介紹其中一種算法,該算法將有根樹的比較轉化為字符串的比較。
對有根樹進行0-1編碼,並且採用字典序對編碼進行比較。字典序的比較方法為:
對不同序列 和 :
- 如果 是 的初始序列(即 ),則 ;
- 如果 是 的初始序列(即 ),則 ;
- 令 是 的最小下標,若 則 ,若 則 。
例: , 。
對有根樹(T,r)進行如下編碼:
- 所有非根葉結點都賦值為01;
- 假設點v的子結點 都已經完成編碼,編碼為 ,且有math>A(w_1)\le A(w_2)\le \dots\le A(w_k)</math>,則v結點的編碼
如此遞歸。r結點的編碼 即為該有根樹的編碼,用 表示。
若 ,則說明有根樹 與 同構。
該算法的判定定理是: 若且唯若他們具有相同的0-1編碼。
對該定理進行如下簡單證明:
- 充分性:從有根樹同構的定義和編碼過程可證。
- 必要性:對編碼進行解碼。任意有根樹的編碼必然有 的一般形式,其中 。 是 中0,1個數相等的最小前綴, 是第二個0,1平衡的最小前綴,以此類推,可以解碼出唯一形態的有根樹。這棵有根樹的其他表示形式都與該解碼形式同構。
樹同構的判定算法基於有根樹同構的判定算法構成。在前文所述中,有根樹相對於樹的區別在於,有根樹有一個特定標記的根。對於一般的樹,我們需要一種找根的算法;在確定這棵樹的有根表達形式之後,對於有根樹進行編碼判定即可。
定義樹的中心點集合 。由於 至多包含兩個頂點,且若 ,那麼該兩點必定相鄰,那麼可以選擇 中的點為根。
樹同構的判定算法中,首先通過刪葉子結點的方式,算出 。
- 若 ,那麼 即為樹T的編碼。
- 若 ,那麼分別計算 與 ,以其中較小的作為樹T的編碼。
若兩棵樹的編碼相同,即可認為兩棵樹是同構的。
- ^ Jiří Matoušek (mathematician); Jaroslav Nešetřil. Invitation to discrete mathematics 2nd. Oxford. ISBN 9780198570431.