《第二类型双圈图的距离矩阵学士学位论文.doc》由会员分享，可在线阅读，更多相关《第二类型双圈图的距离矩阵学士学位论文.doc（17页珍藏版）》请在金锄头文库上搜索。
1、浙江农林大学本科生毕业设计（论文）本 科 生 毕 业 设 计（论文）（ 2013 届）理学院题 目： 第二类型双圈图的距离矩阵的行列式 学生姓名： 章叶锋 学 号： 200911040223 专业班级： 信息与计算科学 指导教师： 龚世才 职称： 教授 2013 年 5 月 15 日浙江农林大学本科生毕业设计（论文）本科生毕业设计（论文）诚信承诺书我谨在此承诺：本人所写的毕业设计（论文）第一类型双圈图的距离矩阵的行列式均系本人独立完成，没有抄袭行为，凡涉及其它作者的观点和材料，均作了引用注释，如出现抄袭及侵犯他人知识产权的情况，后果由本人承担。 承诺人（签名）： 年 月 日 关于第二类型双圈图
2、的距离矩阵的行列式摘要 在图论中，图形都有自己的距离矩阵，距离矩阵即是是一个包含一组点两两之间距离的矩阵(即二维数组)。因此给定N个欧几里得空间中的点, 其距离矩阵就是一个非负实数作为元素的NN的对称矩阵。最简单的图形就是树，是由个顶点和条边组成的一个不存在回路的图。本文主要研究的是第二类型双圈图，即由个顶点和条边组成的存在两个回路且两个回路之间没有相交点的图形。我们的主要工作就是通过Matlab计算各个第二类型双圈图的距离矩阵的行列式并通过生成函数寻找其中的规律。关键词 距离矩阵;树;第二类型双圈图;生成函数ON THE DETERMINANT OF THE SECOND TYP GRAPH
3、SAbstract：In graph theory, the graphics have their own distance matrix, distance matrix that contains a set point or two between distance matrix (two-dimensional array). Therefore, given N points in the Euclidean space, the distance matrix is a non-negative real numbers as elements of N N symmetric
4、matrix. The most simple graph is a tree, consisting of a non-existent by the vertices and edges in the circuit of FIG. This paper studies the second type of bicyclic graphs, graphics there is no point of intersection between the two loops and two loops composed by vertices and edges. Our main job is
5、 to calculate the determinant of the matrix of distance of the second type of bicyclic graphs by useing Matlab and by the generating function to find the law.朗读显示对应的拉丁字符的拼音Keywords：Distance matrices,tree,the second type of bicyclic graphs,generating function目 录1 研究背景.62 基本概念.63 预备知识.74 第二类型双圈图的行列式 .
6、10 4.1数据计算. 10 4.2数据处理. 13参考文献.16致谢.171研究背景 图论从诞生至今已逾300年，在很多方面都有应用。随着现在技术的发展，代数图论是现在图论中的一个主要研究领域，也已有很长的历史。图论的代数表示形式主要有： 1.图的Laplace矩阵2.图的邻接矩阵研究者不断尝试图的其它矩阵表示.1.正规Laplace矩阵2.混合图Laplace矩阵3.无符号Laplace矩阵 近年来，图的距离矩阵越来越受到人们的关注，很多人已经对它进行了研究，其中最主要的是在1971年，Graham和Pollack证明了树的距离矩阵的行列式是一个定值，即2005年，R.bapat,S.j.
7、Kirkland和M.Neumann等进一步研究了赋权树和单圈图的距离矩阵。本文安排如下：首先我们给出与本篇论文相关的一些概念和理论，如树、单圈图、双圈图、距离矩阵、生成函数。接下来我们将计算基本的第二类型双圈图以及通过加边而生成的图形的距离矩阵的行列式并寻找它们之间的规律。2基本概念2.1 距离矩阵 对于一个图(图1)，我们可以根据图各个点之间的距离关系列出它的距离矩阵，其中：其中表示和之间的距离。 图12.2 树 在图论中，树(图2)是任意两个顶点间有且只有一条路径的图。 或者说，只要没有回路的连通图就是树。 定义：如果一个无向简单图满足以下相互等价的条件之一，那么就是一棵树。(1) 是没
8、有回路的连通图。(2) 没有回路，但是在内添加任意一条边，就会形成一个回路。(3) 是连通的，但是如果去掉一条边，就不再连通。(4) 是连通的，并且3顶点的完全图不是的子图。(5) 内的任意两个顶点能被唯一路径所连通。(6) 是连通的，有条边，并且没有简单回路。 图22.3 单圈图定义：在图论中，单圈图即是由个顶点和条边组成的存在一个回路的图(图3，图4)。 图3 图4 定理1.1 D是有个顶点的圈的距离矩阵，然后定理 1.2 G是一个有个顶点且长度为的单圈图。是G的距离矩阵。则，同时的惯性由给出。定理1.3 G是一个有个顶点切长度为的单圈图。D是G的距离矩阵。则D的惯量是。2.4 双圈图一个
9、含有条边的连通图称为双圈图。第一类型双圈图：即由个顶点和条边组成的存在两个回路且两个回路之间没有相交边的图(图5)。 图5第二类型双圈图：即由个顶点和条边组成的存在两个回路且两个回路之间没有相交点的图(图6). 图63预备知识定理1. 距离矩阵的行列式，记作，数域上的矩阵的初等行变换是指下列三种变换：1)以中一个非零的数乘矩阵的某一行；2)把矩阵的某一行的倍加到另一行，这里是中任意一个数；3)互换矩阵中两行的位置。定理2. 把一矩阵的行列互换，所得到的矩阵称为的转置，记为。定理3. 有时候我们把一个大矩阵看成是由一些小矩阵组成的，就如矩阵是由数组组成的一样，特别是在运算中，把这些小矩阵当作数一
10、样来处理，这就是所谓的矩阵的分块。定理4.生成函数:设数列的生成函数，数列的生成函数，我们可以得到以下生成函数的性质：性质1 若 ，则。性质2 若，则。性质3若，则。4第二类型双圈图的距离矩阵的行列式4.1数据计算首先我们研究最基本的第二类型双圈图(图7)，以后我们可以再研究类似图8这类的图形。 图7 图8我们把称为基本图形，首先我们在上加一条边，计算其距离矩阵的行列式的值，然后依次计算加两条边和加三条边的距离矩阵的行列式的值。然后猜想这些行列式的之间的关系。接下来我们可以计算以下各个加边的第二类型双圈图的距离矩阵的行列式并寻找它们的规律。 以下是加两条边的情况： 接下来是加三条边条边的各种情况：
