树的零度算法及实现.docVIP

树的零度算法及实现 　　摘 要： 根据树的基本特征，构建便于计算树的零度的树的存储结构，采用对树进行层序遍历，实现对树的匹配，求出最大匹配数，并结合树的最大匹配与零度之间的关系，设计并实现可以计算任意树的最大匹配数和零度的算法。通过实例研究表明文中算法的时间复杂度为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可了解一棵树的最大匹配数和零度之间的关系