跳至內容

樹同構

維基百科,自由的百科全書

樹同構(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.