基于C++的樹的零度算法實現

摘要：首先構建便于計算樹的零度的樹的存儲結構，結合樹的最大匹配與零度之間的關系，利用C++語言設計并實現可以計算任意樹的最大匹配數和零度。

關鍵詞：樹的零度；最大匹配；C++算法

中圖分類號：TP312 文獻標識碼： A 文章編號：1009-3044（2014）34-8150-02

設[G]是一個圖，[V（G）={v1，v2，…，vn}]是其頂點集。圖[G]的鄰接矩陣記為[A（G）]，它是一個[n]階矩陣[[aij]]，當[vi]鄰接于[vj]時，[aij=1]，否則，[aij=0]。記[PG（λ）]為[A（G）]的特征多項式，[PG（λ）]的所有根（包括重復的）所構成的集合稱為[G]的譜。其中，零特征值的重數稱為[G]的零度，記作[η（G）]。顯然，[η（G）=n-r（A（G））]，這里[n]為[G]的階數，[r（A（G））]為[A（G）]的秩[1-3]。

定義2 給定一個二分圖[G]，在[G]的一個子圖[M]中，[M]的邊集[E]中的任意兩條邊都不依附于同一個頂點，則稱[M]是一個匹配。選擇這樣的邊數最大的子集稱為圖的最大匹配。

定理1.1[4] 設[G]是一個二部圖，若[G]中每個圈的長度都是模4余2的，[η（G）=n-2q]，這里[n]為[G]的階數，[q]為最大匹配數。

樹作為一類特殊的二部圖，有著一些特殊的零度性質。特別地，如果一棵樹具有完美匹配，則簡稱為PM樹。由定理1.1可得：

定理1.2 [5] 設T是一棵樹，則[η（T）=n-2q]，這里[n]為[T]的階數，[q]為最大匹配數。

2 樹的零度算法設計 [6]

2.1 基本方法：

依據定理1.2，下面將引入計算樹的零度的算法：首先，求取樹T的最大匹配數[q]，即將樹T進行按層優先存儲，利用對樹T進行層序遍歷，來實現對樹T的匹配并求出最大匹配數；然后結合定理1.2求出樹的零度值。

2.2 樹中頂點（結點）的存儲結構：

為了便于利用對樹進行層序遍歷來實現樹對樹T的匹配，故使樹結點含有以下5部分信息

2.3 樹的最大匹配算法

2.3.1 基本步驟：

1） 建立一個具有n個頂點樹T，匹配集[M=φ]，頂點集[S=φ]；……