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

關鍵詞：樹的零度；最大匹配；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]的譜。其中，零特征值的重數(shù)稱為[G]的零度，記作[η（G）]。顯然，[η（G）=n-r（A（G））]，這里[n]為[G]的階數(shù)，[r（A（G））]為[A（G）]的秩[1-3]。

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

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

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

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

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

2.1 基本方法：

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

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

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

2.3 樹的最大匹配算法

2.3.1 基本步驟：

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

2） 從樹T中任取一個頂點，固定該頂點將其作為起始頂點v0，對樹T進行分級：將頂點v0作為第0級，除去v0，與v0鄰接的其它頂點作為第1級，除去第1級中的諸頂點，與它們鄰接的其它頂點作為第2級，······，以此類推，可以將樹T中的各頂點劃分為第0級、第1級、······、第P級；

3） 在第P級中選取一個頂點[vp1]，將[vp1]與其雙親結點進行匹配，標記[vp1]雙親結點并將其記入頂點集[S]中，匹配邊記入匹配集[M]中，[vp1]頂點的兄弟結點不參與與其雙親結點的匹配，選取第P級中的其它頂點重復上述匹配過程；

4） 在第P-1級中選取一個頂點，重復第（3）步過程，直到第0級中所有頂點均完成了匹配過程為止。

5） 統(tǒng)計匹配集[M]中匹配邊的個數(shù)，即樹T的最大匹配數(shù)。

6） 通過定理1.2，利用一棵樹的最大匹配數(shù)和零度之間的關系計算出樹T的零度值。

2.3.2 樹零度算法的C++程序代碼

3 實例分析

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

4 結束語

樹的零度有著很好的應用背景，并且也有很多有關零度問題有待解決。比如：實現(xiàn)大頂點樹的更優(yōu)分層排序、構造更簡潔的樹的輸入表示形式；一般圖的零度算法及其實現(xià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] Cvetkovi[c][′] D M， Doob M， Sachs H. Spectra of Graphs[M]. [s.l]：Johann Barth Verlag，1985.

[4] Cvetkovi[c][′] D M， Gutman I， Trinajsti[c][′] N. Graph theory and molecular orbitals，II.Croat[J].hem Acta， 1972， 44：365-374.

[5] Cvetkovi[c][′] 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] 郭承志.樹的零度算法及實現(xiàn)[J].智能計算機與應用，2013（6）：18-19.endprint

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

關鍵詞：樹的零度；最大匹配；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]的譜。其中，零特征值的重數(shù)稱為[G]的零度，記作[η（G）]。顯然，[η（G）=n-r（A（G））]，這里[n]為[G]的階數(shù)，[r（A（G））]為[A（G）]的秩[1-3]。

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

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

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

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

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

2.1 基本方法：

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

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

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

2.3 樹的最大匹配算法

2.3.1 基本步驟：

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

2） 從樹T中任取一個頂點，固定該頂點將其作為起始頂點v0，對樹T進行分級：將頂點v0作為第0級，除去v0，與v0鄰接的其它頂點作為第1級，除去第1級中的諸頂點，與它們鄰接的其它頂點作為第2級，······，以此類推，可以將樹T中的各頂點劃分為第0級、第1級、······、第P級；

3） 在第P級中選取一個頂點[vp1]，將[vp1]與其雙親結點進行匹配，標記[vp1]雙親結點并將其記入頂點集[S]中，匹配邊記入匹配集[M]中，[vp1]頂點的兄弟結點不參與與其雙親結點的匹配，選取第P級中的其它頂點重復上述匹配過程；

4） 在第P-1級中選取一個頂點，重復第（3）步過程，直到第0級中所有頂點均完成了匹配過程為止。

5） 統(tǒng)計匹配集[M]中匹配邊的個數(shù)，即樹T的最大匹配數(shù)。

6） 通過定理1.2，利用一棵樹的最大匹配數(shù)和零度之間的關系計算出樹T的零度值。

2.3.2 樹零度算法的C++程序代碼

3 實例分析

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

4 結束語

樹的零度有著很好的應用背景，并且也有很多有關零度問題有待解決。比如：實現(xiàn)大頂點樹的更優(yōu)分層排序、構造更簡潔的樹的輸入表示形式；一般圖的零度算法及其實現(xià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] Cvetkovi[c][′] D M， Doob M， Sachs H. Spectra of Graphs[M]. [s.l]：Johann Barth Verlag，1985.

[4] Cvetkovi[c][′] D M， Gutman I， Trinajsti[c][′] N. Graph theory and molecular orbitals，II.Croat[J].hem Acta， 1972， 44：365-374.

[5] Cvetkovi[c][′] 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] 郭承志.樹的零度算法及實現(xiàn)[J].智能計算機與應用，2013（6）：18-19.endprint

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

關鍵詞：樹的零度；最大匹配；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]的譜。其中，零特征值的重數(shù)稱為[G]的零度，記作[η（G）]。顯然，[η（G）=n-r（A（G））]，這里[n]為[G]的階數(shù)，[r（A（G））]為[A（G）]的秩[1-3]。

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

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

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

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

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

2.1 基本方法：

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

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

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

2.3 樹的最大匹配算法

2.3.1 基本步驟：

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

2） 從樹T中任取一個頂點，固定該頂點將其作為起始頂點v0，對樹T進行分級：將頂點v0作為第0級，除去v0，與v0鄰接的其它頂點作為第1級，除去第1級中的諸頂點，與它們鄰接的其它頂點作為第2級，······，以此類推，可以將樹T中的各頂點劃分為第0級、第1級、······、第P級；

3） 在第P級中選取一個頂點[vp1]，將[vp1]與其雙親結點進行匹配，標記[vp1]雙親結點并將其記入頂點集[S]中，匹配邊記入匹配集[M]中，[vp1]頂點的兄弟結點不參與與其雙親結點的匹配，選取第P級中的其它頂點重復上述匹配過程；

4） 在第P-1級中選取一個頂點，重復第（3）步過程，直到第0級中所有頂點均完成了匹配過程為止。

5） 統(tǒng)計匹配集[M]中匹配邊的個數(shù)，即樹T的最大匹配數(shù)。

6） 通過定理1.2，利用一棵樹的最大匹配數(shù)和零度之間的關系計算出樹T的零度值。

2.3.2 樹零度算法的C++程序代碼

3 實例分析

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

4 結束語

樹的零度有著很好的應用背景，并且也有很多有關零度問題有待解決。比如：實現(xiàn)大頂點樹的更優(yōu)分層排序、構造更簡潔的樹的輸入表示形式；一般圖的零度算法及其實現(xià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] Cvetkovi[c][′] D M， Doob M， Sachs H. Spectra of Graphs[M]. [s.l]：Johann Barth Verlag，1985.

[4] Cvetkovi[c][′] D M， Gutman I， Trinajsti[c][′] N. Graph theory and molecular orbitals，II.Croat[J].hem Acta， 1972， 44：365-374.

[5] Cvetkovi[c][′] 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] 郭承志.樹的零度算法及實現(xiàn)[J].智能計算機與應用，2013（6）：18-19.endprint