树的零度算法及实现

开篇：润墨网以专业的文秘视角，为您筛选了一篇树的零度算法及实现范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要： 根据树的基本特征，构建便于计算树的零度的树的存储结构，采用对树进行层序遍历，实现对树的匹配，求出最大匹配数，并结合树的最大匹配与零度之间的关系，设计并实现可以计算任意树的最大匹配数和零度的算法。通过实例研究表明文中算法的时间复杂度为O（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 nullity of trees easily， using relationship between the maximum matching number and nullity of trees ，the algorithm is designed and implemented to calculate the the maximum matching number and nullity 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的谱。其中，零特征值的重数称为G的零度，记作η（G）。显然，η（G）=n-r（A（G）），这里n为G的阶数，r（A（G））为A（G）的秩。当η（G）>0即A（G）为奇异阵时，称图G为奇异的，否则，称图G为非奇异的，所以该问题有很好的化学背景[1-3]，一个二部图G（相应于一个交替烃）如果是奇异的，就意味着该图所表示的分子是不稳定的；并且这个问题对非二部图（相应于非交替烃）也是有意义的。

定义 给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。选择这样的边数最大的子集称为图的最大匹配。

定理1[4] 设G是一个二部图，若G中每个圈的长度都是模4余2的，η（G）=n-2q，这里n为G的阶数，q为最大匹配数。

树作为一类特殊的二部图，有着一些特殊的零度性质。特别地，如果一棵树具有完美匹配，则简称为PM树。由定理1可得：

定理2[5] 设T是一棵树，则η（T）=n-2q，这里n为T的阶数，q为最大匹配数。

1 树的零度算法设计和算法复杂度分析

1.1 基本方法

依据定理2，下面将引入计算树的零度的算法：首先，求取树T的最大匹配数q，即将树T进行按层优先存储，利用对树T进行层序遍历，来实现对树T的匹配并求出最大匹配数；然后结合定理2求出树的零度值。

1.2 树中顶点（结点）的存储结构

为了便于利用对树进行层序遍历来实现树对树T的匹配，故使树结点含有以下5部分信息

mark data parent child brother

其中：

mark为标记域，用0和1标记树结点是否已匹配过，0表示未匹配，1表示已匹配；

data为数据域；

parent为指向该结点的双亲结点的指针；

child为指向该结点的孩子结点的指针；

brother指向该结点的兄弟结点的指针。

1.3 计算树的零度的流程图

根据1.1给出的方法，结合树的顶点的存储结构，设计了便于计算树的最大匹配数和树的零度算法，其流程图如图1所示。

1.4 算法复杂度分析

本算法先将树T（含有n顶点）中的顶点自上而下、自左而右的顺序，以层优先的方式进行存储，然后从最后一个顶点出发依次与其双亲顶点进行匹配，所以该算法在完成最大匹配时的最大运行时间为n-1，其时间复杂度为O（n）。

通过定理2可了解一棵树的最大匹配数和零度之间的关系。在文献[6]中只给出了计算二部图的最大匹配数的算法，该算法的时间复杂度为O（mn），其中m是G的边数、n是G的顶点数。但是，该算法的程序实现是比较困难的。在文献[7]中给出了一个计算树的零度算法，该算法在求最大匹配时的时间复杂度为O（n22）。

图1 计算树的零度的流程图

用 第3卷

2 实例分析

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

依据上述算法：

输入：按广义表形式来表示图1所示的树T

输出：根据1.2中所定义的树结点建立树T的存储结构，然后对树T进行层序遍历，并将遍历到的顶点依次压入栈str中，如图3所示，此时栈str的栈顶元素为str[10]，即为树T中的最后遍历到的元素。

匹配结果：根据1.3中算法，选取树T的一个顶点str[10]，将其与双亲结点str[6]匹配，由于二者的标志位均为0，所以匹配成功，二者的标志位置为1并进行计数，树T获得一条匹配边；str[6]的兄弟结点str[8]、str[9]不参加与其双亲结点的匹配。选取T的下一个顶点str[7]，将其与双亲结点str[4]匹配，重复上述过程，得到图4所示的树T匹配后的存储结构图，图中为了强调匹配过程中在树T中所选中的顶点，故将其标志位置为2。

图3 树T的存储结构图

图4 完成匹配后，树T的存储结构图

Fig.4 Complete matching， storage structure of tree T

匹配边集：GK、EH、BF、AC，最大匹配数为，其零度是。

3 结束语

本算法先将树T（含有n顶点）以层优先的方式进行遍历、存储，然后从最后一个顶点出发依次与其双亲顶点进行匹配，其时间复杂度为O（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 nullity of unicyclic graph Linear Algebra and its Applications ，2005， 408：212-220.

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