樹的零度算法及實現(xiàn)

摘 要： 根據(jù)樹的基本特征，構(gòu)建便于計算樹的零度的樹的存儲結(jié)構(gòu)，采用對樹進行層序遍歷，實現(xiàn)對樹的匹配，求出最大匹配數(shù)，并結(jié)合樹的最大匹配與零度之間的關(guān)系，設計并實現(xiàn)可以計算任意樹的最大匹配數(shù)和零度的算法。通過實例研究表明文中算法的時間復雜度為O（n），該算法簡單、實用、易于操作。

關(guān)鍵詞： 二部圖； 樹的零度； 最大匹配； 算法

中圖分類號： TP312 文獻標識碼： A 文章編號：2095-2163（2013）03-0018-02

The Nullity Algorithm of Trees And Realization

GUO Chengzhi

（School of Mathematics Statistics， Qinghai University of Nationalities， Xining 810007， China）

Abstract： This paper creates storage structure of trees to calculate the 1ity of trees easily， using relationship between the maximum matching number and 1ity of trees ，the algorithm is designed and implemented to calculate the the maximum matching number and 1ity of any tree.The algorithm is simple， practtcal and easy to operate.

Key words： Bipartite Graphs； Nullity of Trees； Maximum Matching； Algorithm

0 引 言

設G是一個圖，V（G）={v1，v2，…，vn}是其頂點集。圖G的鄰接矩陣記為A（G），這是一個n階矩陣[aij]，當vi鄰接于vj時，aij=1，否則，aij=0。記PG（λ）為A（G）的特征多項式，PG（λ）的全部根（包括重復的）所構(gòu)成的集合稱為G的譜。其中，零特征值的重數(shù)稱為G的零度，記作η（G）。顯然，η（G）=n-r（A（G）），這里n為G的階數(shù)，r（A（G））為A（G）的秩。當η（G）>0即A（G）為奇異陣時，稱圖G為奇異的，否則，稱圖G為非奇異的，所以該問題有很好的化學背景[1-3]，一個二部圖G（相應于一個交替烴）如果是奇異的，就意味著該圖所表示的分子是不穩(wěn)定的；并且這個問題對非二部圖（相應于非交替烴）也是有意義的。

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

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

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

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

1 樹的零度算法設計和算法復雜度分析

1.1 基本方法

依據(jù)定理2，下面將引入計算樹的零度的算法：首先，求取樹T的最大匹配數(shù)q，即將樹T進行按層優(yōu)先存儲，利用對樹T進行層序遍歷，來實現(xiàn)對樹T的匹配并求出最大匹配數(shù)；然后結(jié)合定理2求出樹的零度值。

1.2 樹中頂點（結(jié)點）的存儲結(jié)構(gòu)

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

mark data parent child brother

其中：

mark為標記域，用0和1標記樹結(jié)點是否已匹配過，0表示未匹配，1表示已匹配；

data為數(shù)據(jù)域；

parent為指向該結(jié)點的雙親結(jié)點的指針；

child為指向該結(jié)點的孩子結(jié)點的指針；

brother指向該結(jié)點的兄弟結(jié)點的指針。

1.3 計算樹的零度的流程圖

根據(jù)1.1給出的方法，結(jié)合樹的頂點的存儲結(jié)構(gòu)，設計了便于計算樹的最大匹配數(shù)和樹的零度算法，其流程圖如圖1所示。

1.4 算法復雜度分析

本算法先將樹T（含有n頂點）中的頂點自上而下、自左而右的順序，以層優(yōu)先的方式進行存儲，然后從最后一個頂點出發(fā)依次與其雙親頂點進行匹配，所以該算法在完成最大匹配時的最大運行時間為n-1，其時間復雜度為O（n）。

通過定理2可了解一棵樹的最大匹配數(shù)和零度之間的關(guān)系。在文獻[6]中只給出了計算二部圖的最大匹配數(shù)的算法，該算法的時間復雜度為O（mn），其中m是G的邊數(shù)、n是G的頂點數(shù)。但是，該算法的程序?qū)崿F(xiàn)是比較困難的。在文獻[7]中給出了一個計算樹的零度算法，該算法在求最大匹配時的時間復雜度為O（n22）。

圖1 計算樹的零度的流程圖

用 第3卷

2 實例分析

圖2是一個具有11個頂點、層數(shù)為4的樹。

依據(jù)上述算法：

輸入：按廣義表形式來表示圖1所示的樹T

輸出：根據(jù)1.2中所定義的樹結(jié)點建立樹T的存儲結(jié)構(gòu)，然后對樹T進行層序遍歷，并將遍歷到的頂點依次壓入棧str中，如圖3所示，此時棧str的棧頂元素為str[10]，即為樹T中的最后遍歷到的元素。

匹配結(jié)果：根據(jù)1.3中算法，選取樹T的一個頂點str[10]，將其與雙親結(jié)點str[6]匹配，由于二者的標志位均為0，所以匹配成功，二者的標志位置為1并進行計數(shù)，樹T獲得一條匹配邊；str[6]的兄弟結(jié)點str[8]、str[9]不參加與其雙親結(jié)點的匹配。選取T的下一個頂點str[7]，將其與雙親結(jié)點str[4]匹配，重復上述過程，得到圖4所示的樹T匹配后的存儲結(jié)構(gòu)圖，圖中為了強調(diào)匹配過程中在樹T中所選中的頂點，故將其標志位置為2。

圖3 樹T的存儲結(jié)構(gòu)圖

圖4 完成匹配后，樹T的存儲結(jié)構(gòu)圖

Fig.4 Complete matching， storage structure of tree T

匹配邊集：GK、EH、BF、AC，最大匹配數(shù)為，其零度是。

3 結(jié)束語

本算法先將樹T（含有n頂點）以層優(yōu)先的方式進行遍歷、存儲，然后從最后一個頂點出發(fā)依次與其雙親頂點進行匹配，其時間復雜度為O（n）。通過實例研究表明本文算法簡單、實用，易于操作。樹的零度有著很好的應用背景，并且也有很多有關(guān)零度問題等待人們?nèi)ソ鉀Q。比如：實現(xiàn)大頂點樹的更優(yōu)分層排序、構(gòu)造更簡潔的樹的輸入表示形式；一般圖的零度算法及其實現(xiàn)尚未給出。另外，零度與圖的其他參數(shù)之間的關(guān)系應用的相關(guān)算法也是一個有趣的問題。

參考文獻：

[1]COLLATZ L， SINOGOWITZ U. Spektren edlicher Grafen[J]. Abh Math Sem Univ Hamburg，1957， 21：63-77.

[2]LONGUET-HIGGINS H C. Resonance structures and MO in unsaturated hydrocarbons[J].Journal of Chemistry and Physics， 1950， 18：265-274.

[3]CVETKOVIC′ D M， DOOB M， SACHS H. Spectra of Graphs[M]. [s.l]：Johann Barth Verlag，1985.

[4]CVETKOVIC′ D M， GUTMAN I， TRINAJSTIC′ N. Graph theory and molecular orbitals，II.Croat[J].hem Acta， 1972， 44：365-374.

[5]CVETKOVIC′ D M， GUTMAN I. The algebraic multiplicity of the number zero in the spectrum of a bipartite graph[J]. Mat Vesnik， 1972（9），：141-150.

[6]AN Xuezhong， LIU Bolian. On the 1ity of unicyclic graph Linear Algebra and its Applications ，2005， 408：212-220.

[7]CHENG B，LIU B L. On the 1ity of graphs[J]. Electronic Journal of Linear Algebra，2007，16： 60-67.