几类图的匹配多项式.docVIP

本科毕业论文 （ 2010 届） 题 目 几类图的匹配多项式 学 院 数学与信息工程学院 专 业 数学与应用数学 班 级 2006级数学2班 学 号 0604010208 学生姓名 泮彬彬 指导教师 张海良 完成日期 2010年5月 摘 要 本文研究了完全图、轮图这2类图的匹配多项式以及它们的特征多项式和谱，并推出了这两类图的匹配多项式公式。轮图的邻接矩阵恰好是圈的邻接矩阵的镶边矩阵，两者间的特征值存在着一定的联系，研究了轮图的谱与圈的谱的关系，同时给出几类图的匹配多项式之间的关系，并加以证明。 关键词 匹配多项式；图的谱；图的特征多项式 Abstract In this article, we study the matching polynomials, characteristic polynomials and spectrum of complete graph and wheel graph. Then the two graph’s formula of matching polynomials is released. The adjacency matrix of wheel graph is exactly the bordered matrix of the circle’s adjacency matrix. The eigenvalues between the two have something in common. What’s more, we discuss the relationship between the spectrum of wheel graph and the spectrum of circle, at the same time; the relationships in the matching polynomials of graphs are proved. Keywords Matching Polynomials; Characteristic Polynomials; Spectrum 目 录 1. 引言 1 2．引理 2 3．完全图的匹配多项式、特征多项式与谱 2 4．轮图的匹配多项式、特征多项式与谱 5 5．几类图的匹配多项式之间的关系 17 参考文献 21 谢辞 22 几类图的匹配多项式 The Matching Polynomial of Several Graphs 数学与信息工程学院 数学与应用数学专业 泮彬彬 指导老师：张海良 1引言 图的匹配多项式和特征多项式、拉普拉斯多项式一样包含了许多图的组合性质，并且在化学中得到了广泛的应用，Farrel E J．在An Introductlon to Matching Polynomials中定义了匹配多项式为，其中是G的k匹配的的数目，k匹配是指其中有k条棱的匹配, 矢量，，分别表示顶点和棱的权重，，文[1]中定义图的匹配多项式的另一种表达形式为，其中是G的t匹配的的数目，为该图的边数。G的一个匹配是指G的一个生成子图，它的每个分支是孤立点或孤立边，t-匹配是指其中有t条边匹配。Godsil C.D在文[1]中还给出了部分图的匹配多项式如下列引理。以后对于图的匹配唯一性的研究、匹配等价性的研究、匹配多项式的计算、图的匹配多项式之间的整除关系的研究以及匹配多项式最大根对图的刻画有大量的研究成果，如下列参考文献。完全图是每对顶点之间都恰连有一条边的简单图。n个端点的完全图有n个端点及n(n ? 1) / 2条边，以表示个端点表示，用在单图G=(V,E)中用表示图G的邻接矩阵,则矩阵A(G)的特征值称为图G的特征值。所有图G的特征值组成的序列称为图G的谱表示。，其中为特征值，为相应特征值的重数。设A是矩阵，a为实数，为向量，则称为A的镶边矩阵，顶点V所关连边的数目称为顶点V的度。 2若干引理 引理1[1]设图G有k个分支：，，…，则。 引理2[1]⑴，表示有n个点的圈； ⑵，表示有n个点的路。 引理3[1] 设是图的一条边,且,则，这里表示从图中删去边，点而得到的图。 引理4[1] 设，则。这里是对邻接于点u的所有点i求和。 3完全图的匹配多项式、特征多项式与谱 的匹配多项式为： 的特征多项式为： 的谱为： 的匹配多项式为： 的特征多项式为： 的谱为： 的匹配多项式为： 的特征多项式为： 的谱为： 的匹配多项式为： 的特征多项式为： 的谱为： 的