第二类型双圈图的距离矩阵-毕业论文.doc

本 科 生 毕 业 设 计（论文） （ 2013 届） 理学院 题 目： 第二类型双圈图的距离矩阵的行列式 学生姓名： 章叶锋 学 号： 200911040223 专业班级： 信息与计算科学 指导教师： 龚世才 职称： 教授 2013 年 5 月 15 日  本科生毕业设计（论诚诺书我谨诺写毕业设计（论类双图阵独没袭为观点释现袭及识产权况担诺签名 月 日 关于第二类型双圈图的距离矩阵的行列式 摘要 在图论中，图形都有自己的距离矩阵，距离矩阵即是是一个包含一组点两两之间距离的矩阵(即二维数组)。因此给定N个欧几里得空间中的点, 其距离矩阵就是一个非负实数作为元素的N×N的对称矩阵。最简单的图形就是树，是由个顶点和条边组成的一个不存在回路的图。本文主要研究的是第二类型双圈图，即由个顶点和条边组成的存在两个回路且两个回路之间没有相交点的图形。我们的主要工作就是通过Matlab计算各个第二类型双圈图的距离矩阵的行列式并通过生成函数寻找其中的规律。 关键词 距离矩阵;树;第二类型双圈图;生成函数 ON THE DETERMINANT OF THE SECOND TYP GRAPHS Abstract：朗读 显示对应的拉丁字符的拼音 Keywords： 目 录 1 研究背景.......................................................................6 2 基本概念.......................................................................6 3 预备知识.......................................................................7 4 第二类型双圈图的行列式 ........................................................10 4.1数据计算................................................................... 10 4.2数据处理................................................................... 13 参考文献......................................................................16 致谢..........................................................................17 1研究背景 图论从诞生至今已逾300年，在很多方面都有应用。随着现在技术的发展，代数图论是现在图论中的一个主要研究领域，也已有很长的历史。图论的代数表示形式主要有： 1.图的Laplace矩阵 2.图的邻接矩阵 研究者不断尝试图的其它矩阵表示. 1.正规Laplace矩阵 2.混合图Laplace矩阵 3.无符号Laplace矩阵 近年来，图的距离矩阵越来越受到人们的关注，很多人已经对它进行了研究，其中最主要的是在1971年，Graham和Pollack证明了树的距离矩阵的行列式是一个定值，即 2005年，R.bapat,S.j.Kirkland和M.Neumann等进一步研究了赋权树和单圈图的距离矩阵。 本文安排如下：首先我们给出与本篇论文相关的一些概念和理论，如树、单圈图、双圈图、距离矩阵、生成函数。接下来我们将计算基本的第二类型双圈图以及通过加边而生成的图形的距离矩阵的行列式并寻找它们之间的规律。 2基本概念 2.1 距离矩阵 对于一个图(图1)，我们可以根据图各个点之间的距离关系列出它的距离矩阵，其中： 其中表示和之间的距离。 图1 2.2 树 在图论中，树是任意两个顶点间有且只有一条路径的图。 或者说，只要没有回路的连通图就是树。 [1] R.B. Bapat, The Laplacian matrix of a graph, Math. Student 65 (1996) 214–223. [2] N. Dyn, W.A. Light, E.W.