基于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=φ]；

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） 统计匹配集[M]中匹配边的个数，即树T的最大匹配数。

6） 通过定理1.2，利用一棵树的最大匹配数和零度之间的关系计算出树T的零度值。

2.3.2 树零度算法的C++程序代码

3 实例分析

图1是一个具有11个顶点、层数为4的树。

4 结束语

树的零度有着很好的应用背景，并且也有很多有关零度问题有待解决。比如：实现大顶点树的更优分层排序、构造更简洁的树的输入表示形式；一般图的零度算法及其实现尚未给出……。

参考文献：

[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] 郭承志.树的零度算法及实现[J].智能计算机与应用，2013（6）：18-19.