Beyond the Void
BYVoid
有向樹與樹的括號序列最小表示法
本文正體字版由OpenCC轉換

[有向樹] 一個弱連通有向圖,若去掉方向後得到一棵樹,則稱此有向圖爲一棵有向樹,記爲T。

[外向樹] 若一個有向樹T,有且只有一個頂點入度爲0,其餘頂點入度都爲1,則稱T爲外向樹。T中入度爲0的節點被稱爲T的根節點,出度爲0的節點被稱爲T的葉節點。每個節點的有向邊指向的節點被稱爲該節點的子節點

[內向樹] 若一個有向樹T,有且只有一個頂點出度爲0,其餘頂點出度都爲1,則稱T爲向樹。T中出度爲0的節點被稱爲T的根節點,入度爲0的節點被稱爲T的葉節點。每個節點的有向邊的反向邊指向的節點被稱爲該節點的子節點

外向樹和內向樹都是有根樹

e5a496e59091e6a091 e58685e59091e6a091
圖1 圖2

如上,圖1爲一棵外向樹,圖2爲一棵內向樹。

[樹的括號序列最小表示法]

定義S[t]表示以t爲根的子樹的括號序列

S[t]=

{

‘(',')’ (如果t爲葉節點)

‘(',S[c1],S[c2],…,S[ck],')’ (c1,c2,…,ck爲t的k個子節點,S[c1],S[c2],…,S[ck]要按照字典序排列)

}

爲了保證同構的樹的括號序列表示具有唯一性,我們必須規定子樹點的順序。按照子樹的括號序列的字典序就是一種不錯的方法。

例如上述圖2,它的括號序列最小表示就是((()()())())

[有根樹的同構]

對於一個有根樹,我們可以通過比較他們的括號序列的最小表示,如果他們的括號序列最小表示完全相等,那麼他們同構

BYVoid 原創講解,轉載請註明。


上次修改時間 2017-05-26

相關日誌