基于C++的樹的零度算法實(shí)現(xiàn)

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

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

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)：1009-3044（2014）34-8150-02

設(shè)[G]是一個(gè)圖，[V（G）={v1，v2，…，vn}]是其頂點(diǎn)集。圖[G]的鄰接矩陣記為[A（G）]，它是一個(gè)[n]階矩陣[[aij]]，當(dāng)[vi]鄰接于[vj]時(shí)，[aij=1]，否則，[aij=0]。記[PG（λ）]為[A（G）]的特征多項(xiàng)式，[PG（λ）]的所有根（包括重復(fù)的）所構(gòu)成的集合稱為[G]的譜。其中，零特征值的重?cái)?shù)稱為[G]的零度，記作[η（G）]。顯然，[η（G）=n-r（A（G））]，這里[n]為[G]的階數(shù)，[r（A（G））]為[A（G）]的秩[1-3]。

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

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

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

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

2 樹的零度算法設(shè)計(jì) [6]

2.1 基本方法：

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

2.2 樹中頂點(diǎn)（結(jié)點(diǎn)）的存儲(chǔ)結(jié)構(gòu)：

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

2.3 樹的最大匹配算法

2.3.1 基本步驟：

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

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

3） 在第P級(jí)中選取一個(gè)頂點(diǎn)[vp1]，將[vp1]與其雙親結(jié)點(diǎn)進(jìn)行匹配，標(biāo)記[vp1]雙親結(jié)點(diǎn)并將其記入頂點(diǎn)集[S]中，匹配邊記入匹配集[M]中，[vp1]頂點(diǎn)的兄弟結(jié)點(diǎn)不參與與其雙親結(jié)點(diǎn)的匹配，選取第P級(jí)中的其它頂點(diǎn)重復(fù)上述匹配過程；

4） 在第P-1級(jí)中選取一個(gè)頂點(diǎn)，重復(fù)第（3）步過程，直到第0級(jí)中所有頂點(diǎn)均完成了匹配過程為止。

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

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

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

3 實(shí)例分析

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

4 結(jié)束語

樹的零度有著很好的應(yīng)用背景，并且也有很多有關(guān)零度問題有待解決。比如：實(shí)現(xiàn)大頂點(diǎn)樹的更優(yōu)分層排序、構(gòu)造更簡潔的樹的輸入表示形式；一般圖的零度算法及其實(shí)現(xiàn)尚未給出……。

參考文獻(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] 郭承志.樹的零度算法及實(shí)現(xiàn)[J].智能計(jì)算機(jī)與應(yīng)用，2013（6）：18-19.endprint

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

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

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)：1009-3044（2014）34-8150-02

設(shè)[G]是一個(gè)圖，[V（G）={v1，v2，…，vn}]是其頂點(diǎn)集。圖[G]的鄰接矩陣記為[A（G）]，它是一個(gè)[n]階矩陣[[aij]]，當(dāng)[vi]鄰接于[vj]時(shí)，[aij=1]，否則，[aij=0]。記[PG（λ）]為[A（G）]的特征多項(xiàng)式，[PG（λ）]的所有根（包括重復(fù)的）所構(gòu)成的集合稱為[G]的譜。其中，零特征值的重?cái)?shù)稱為[G]的零度，記作[η（G）]。顯然，[η（G）=n-r（A（G））]，這里[n]為[G]的階數(shù)，[r（A（G））]為[A（G）]的秩[1-3]。

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

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

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

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

2 樹的零度算法設(shè)計(jì) [6]

2.1 基本方法：

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

2.2 樹中頂點(diǎn)（結(jié)點(diǎn)）的存儲(chǔ)結(jié)構(gòu)：

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

2.3 樹的最大匹配算法

2.3.1 基本步驟：

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

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

3） 在第P級(jí)中選取一個(gè)頂點(diǎn)[vp1]，將[vp1]與其雙親結(jié)點(diǎn)進(jìn)行匹配，標(biāo)記[vp1]雙親結(jié)點(diǎn)并將其記入頂點(diǎn)集[S]中，匹配邊記入匹配集[M]中，[vp1]頂點(diǎn)的兄弟結(jié)點(diǎn)不參與與其雙親結(jié)點(diǎn)的匹配，選取第P級(jí)中的其它頂點(diǎn)重復(fù)上述匹配過程；

4） 在第P-1級(jí)中選取一個(gè)頂點(diǎn)，重復(fù)第（3）步過程，直到第0級(jí)中所有頂點(diǎn)均完成了匹配過程為止。

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

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

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

3 實(shí)例分析

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

4 結(jié)束語

樹的零度有著很好的應(yīng)用背景，并且也有很多有關(guān)零度問題有待解決。比如：實(shí)現(xiàn)大頂點(diǎn)樹的更優(yōu)分層排序、構(gòu)造更簡潔的樹的輸入表示形式；一般圖的零度算法及其實(shí)現(xiàn)尚未給出……。

參考文獻(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] 郭承志.樹的零度算法及實(shí)現(xiàn)[J].智能計(jì)算機(jī)與應(yīng)用，2013（6）：18-19.endprint

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

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

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)：1009-3044（2014）34-8150-02

設(shè)[G]是一個(gè)圖，[V（G）={v1，v2，…，vn}]是其頂點(diǎn)集。圖[G]的鄰接矩陣記為[A（G）]，它是一個(gè)[n]階矩陣[[aij]]，當(dāng)[vi]鄰接于[vj]時(shí)，[aij=1]，否則，[aij=0]。記[PG（λ）]為[A（G）]的特征多項(xiàng)式，[PG（λ）]的所有根（包括重復(fù)的）所構(gòu)成的集合稱為[G]的譜。其中，零特征值的重?cái)?shù)稱為[G]的零度，記作[η（G）]。顯然，[η（G）=n-r（A（G））]，這里[n]為[G]的階數(shù)，[r（A（G））]為[A（G）]的秩[1-3]。

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

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

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

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

2 樹的零度算法設(shè)計(jì) [6]

2.1 基本方法：

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

2.2 樹中頂點(diǎn)（結(jié)點(diǎn)）的存儲(chǔ)結(jié)構(gòu)：

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

2.3 樹的最大匹配算法

2.3.1 基本步驟：

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

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

3） 在第P級(jí)中選取一個(gè)頂點(diǎn)[vp1]，將[vp1]與其雙親結(jié)點(diǎn)進(jìn)行匹配，標(biāo)記[vp1]雙親結(jié)點(diǎn)并將其記入頂點(diǎn)集[S]中，匹配邊記入匹配集[M]中，[vp1]頂點(diǎn)的兄弟結(jié)點(diǎn)不參與與其雙親結(jié)點(diǎn)的匹配，選取第P級(jí)中的其它頂點(diǎn)重復(fù)上述匹配過程；

4） 在第P-1級(jí)中選取一個(gè)頂點(diǎn)，重復(fù)第（3）步過程，直到第0級(jí)中所有頂點(diǎn)均完成了匹配過程為止。

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

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

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

3 實(shí)例分析

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

4 結(jié)束語

樹的零度有著很好的應(yīng)用背景，并且也有很多有關(guān)零度問題有待解決。比如：實(shí)現(xiàn)大頂點(diǎn)樹的更優(yōu)分層排序、構(gòu)造更簡潔的樹的輸入表示形式；一般圖的零度算法及其實(shí)現(xiàn)尚未給出……。

參考文獻(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] 郭承志.樹的零度算法及實(shí)現(xiàn)[J].智能計(jì)算機(jī)與應(yīng)用，2013（6）：18-19.endprint