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

定義

編輯

樹同構的概念源於圖同構圖同構的概念為,兩個簡單圖  稱為是同構的,若且唯若存在一個將 的節點   映射到 的節點 一一對應 ,使得 中任意兩個節點  相連接,若且唯若 中對應的兩個節點  相連接。樹同構即在以上定義中增加  都是的限制條件。兩顆樹 同構可以記作 

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

有根樹同構的定義為,對於兩顆有根樹  ,存在一個同構映射 ,其中   同構可記作 

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

有根樹同構判定算法

編輯

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

有根樹的0-1編碼

編輯

對有根樹進行0-1編碼,並且採用字典序對編碼進行比較。字典序的比較方法為: 對不同序列  

  • 如果  的初始序列(即 ),則 ;
  • 如果  的初始序列(即 ),則 ;
  •   的最小下標,若  ,若  

例: , 

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

  • 所有非根葉結點都賦值為01;
  • 假設點v的子結點 都已經完成編碼,編碼為 ,且有 ,則v結點的編碼 

如此遞歸。r結點的編碼 即為該有根樹的編碼,用 表示。

 ,則說明有根樹  同構。

判定定理的簡單證明

編輯

該算法的判定定理是: 若且唯若他們具有相同的0-1編碼。 對該定理進行如下簡單證明:

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

樹同構判定算法

編輯

樹同構的判定算法基於有根樹同構的判定算法構成。在前文所述中,有根樹相對於樹的區別在於,有根樹有一個特定標記的根。對於一般的樹,我們需要一種找根的算法;在確定這棵樹的有根表達形式之後,對於有根樹進行編碼判定即可。

定義樹的中心點集合 。由於 至多包含兩個頂點,且若 ,那麼該兩點必定相鄰,故可以選擇 中的點為根。

樹同構的判定算法中,首先通過刪葉子結點的方式,算出 

  •  ,那麼 即為樹T的編碼。
  •  ,那麼分別計算  ,以其中較小的作為樹T的編碼。

若兩棵樹的編碼相同,即可認為兩棵樹是同構的。

參考文獻

編輯
  1. ^ Jiří Matoušek (mathematician); Jaroslav Nešetřil. Invitation to discrete mathematics 2nd. Oxford. ISBN 9780198570431.