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

浙江农林大学本科生毕业设计（论文）

本 科 生 毕 业 设 计（论文）
（ 2013 届）
理学院

题 目： 第二类型双圈图的距离矩阵的行列式

学生姓名： 章叶锋

学 号： 200911040223

专业班级： 信息与计算科学

指导教师： 龚世才 职称： 教授

2013 年 5 月 15 日

浙江农林大学本科生毕业设计（论文）

本科生毕业设计（论文）诚信承诺书
我谨在此承诺：本人所写的毕业设计（论文）《第一类型双圈图的距离矩阵的行列式》均系本人独立完成，没有抄袭行为，凡涉及其它作者的观点和材料，均作了引用注释，如出现抄袭及侵犯他人知识产权的情况，后果由本人承担。

承诺人（签名）：
年 月 日

关于第二类型双圈图的距离矩阵的行列式

摘要 在图论中，图形都有自己的距离矩阵，距离矩阵即是是一个包含一组点两两之间距离的矩阵(即二维数组)。因此给定N个欧几里得空间中的点, 其距离矩阵就是一个非负实数作为元素的N×N的对称矩阵。最简单的图形就是树，是由个顶点和条边组成的一个不存在回路的图。本文主要研究的是第二类型双圈图，即由个顶点和条边组成的存在两个回路且两个回路之间没有相交点的图形。我们的主要工作就是通过Matlab计算各个第二类型双圈图的距离矩阵的行列式并通过生成函数寻找其中的规律。
关键词 距离矩阵;树;第二类型双圈图;生成函数

ON THE DETERMINANT OF THE SECOND TYP GRAPHS

Abstract：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 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 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 研究背景.......................................................................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 树
在图论中，树(图2)是任意两个顶点间有且只有一条路径的图。 或者说，只要没有回路的连通图就是树。
定义：如果一个无向简单图满足以下相互等价的条件之一，那么就是一棵树。
(1) 是没有回路的连通图。
(2) 没有回路，但是在内添加任意一条边，就会形成一个回路。
(3) 是连通的，但是如果去掉一条边，就不再连通。
(4) 是连通的，并且3顶点的完全图不是的子图。
(5) 内的任意两个顶点能被唯一路径所连通。
(6) 是连通的，有条边，并且没有简单回路。

图2

2.3 单圈图
定义：在图论中，单圈图即是由个顶点和条边组成的存在一个回路的图(图3，图4)。

图3 图4
定理1.1 D是有个顶点的圈的距离矩阵，然后

定理 1.2 G是一个有个顶点且长度为的单圈图。是G的距离矩阵。则，同时的惯性由给出。
定理1.3 G是一个有个顶点切长度为的单圈图。D是G的距离矩阵。则D的惯量是。

2.4 双圈图

一个含有条边的连通图称为双圈图。
第一类型双圈图：即由个顶点和条边组成的存在两个回路且两个回路之间没有相交边的图(图5)。

图5
第二类型双圈图：即由个顶点和条边组成的存在两个回路且两个回路之间没有相交点的图(图6).

图6
3预备知识
定理1. 距离矩阵的行列式，记作，数域上的矩阵的初等行变换是指下列三种变换：
1)以中一个非零的数乘矩阵的某一行；
2)把矩阵的某一行的倍加到另一行，这里是中任意一个数；
3)互换矩阵中两行的位置。
定理2. 把一矩阵的行列互换，所得到的矩阵称为的转置，记为。
定理3. 有时候我们把一个大矩阵看成是由一些小矩阵组成的，就如矩阵是由数组组成的一样，特别是在运算中，把这些小矩阵当作数一样来处理，这就是所谓的矩阵的分块。
定理4.生成函数:
设数列的生成函数，数列的生成函数，我们可以得到以下生成函数的性质：
性质1
若 ，则。
性质2
若，则。
性质3
若，则。

4第二类型双圈图的距离矩阵的行列式

4.1数据计算
首先我们研究最基本的第二类型双圈图(图7)，以后我们可以再研究类似图8这类的图形。

图7 图8

我们把称为基本图形，首先我们在上加一条边，计算其距离矩阵的行列式的值，然后依次计算加两条边和加三条边的距离矩阵的行列式的值。然后猜想这些行列式的之间的关系。
接下来我们可以计算以下各个加边的第二类型双圈图的距离矩阵的行列式并寻找它们的规律。

以下是加两条边的情况：

接下来是加三条边条边的各种情况：

通过计算
图形编号

行列式值
-32
-32
-32
-32
-32
-32
-32
图像编号

行列式的值
80
80
80
80
80
80
80
80
80

80
80
80
80
80
80
80
从上面的计算结果可以知道对于一个基本的第二类型双圈图，只要加上的边的个数是相同的，则他的距离矩阵的行列式的值是不变的。

4.2数据处理
接下来我们可以先研究下面这个图形。

对于的距离矩阵的行列式，我们用表示行向量，表示值都是1的行向量，是一个行列式，是的转置 。
==
图和的距离矩阵的行列式正好可以表示为和，如果把的距离矩阵的行列式表达式记为，则和的距离矩阵的行列式分别为和，即。
所以，可以得到。
根据之前计算的结果，可以证明该表达式是正确的。
接下来我们用生成函数求解递推关系

令

则有

将代入上式并整理，得

设

其中，为待定系数，通过比较等式两边的常数项与一次项系数，可得

所以，

因此

对于这类加三条边的第二类型双圈图，将代入上式可得
；
与之前的计算结果一致
,所以

为通项公式。

参考文献

[1] R.B. Bapat, The Laplacian matrix of a graph, Math. Student 65 (1996) 214–223.
[2] N. Dyn, W.A. Light, E.W. Cheney, Interpolation by piecewise-linear radial basis functions I, J. Approx. Theory 59 (1989) 202–223.
[3] R.L. Graham, H.O. Pollack, On the addressing problem for loop switching, Bell System Tech. J. 50(1971) 2495–2519.
[4] R.L. Graham, L. Lovász, Distance matrix polynomials of trees, Adv. Math. 29 (1) (1978) 60–88.
[5] Edward J. Kaplan, Mathematical Programming and Games, John Wiley, 1982.
[6] R. Merris, The distance spectrum of a tree, J. Graph Theory 14 (3) (1990) 365–369.
[7] R. Merris, Laplacian matrices of graphs: a survey, Linear Algebra Appl. 197/198 (1994) 143–176.
[8] T. Parthasarathy, G. Ravindran, N-matrices, Linear Algebra Appl. 139 (1990) 89–102.
[9] L. Reid, X. Sun, Distance matrices and ridge function interpolation, Can. J. Math. 45 (6) (1993)1313–1323.
[10] X. Sun, Solvability of multivariate interpolation by radial or related functions, J. Approx. Theory 72(3) (1993) 252–267.
[11]王蕚芳,石生明,高等代数[M].高等教育出版社,2003:290.
[12]王贵平,王衍,任嘉辰. 图论算法理论、实现及应用[M],北京：北京大学出版社,2011：88.
[13]许胤龙，孙淑玲，组合数学引论[M].中国科学技术大学出版社，2010：4.
[14]胡良剑，孙晓君，MATLAB数学实验[M].高等教育出版社，2006:6.

致谢

本论文在选题和撰写过程中都得到了龚世才老师的精心指导．不论是在工作上还是在日常生活中，龚老师给了我无微不至的关怀．特别是在学习和工作中，龚老师广博的学识给予了我很大的帮助和支持．在此，我表示由衷的感谢．另外，龚老师严谨治学的学术作风和兢兢业业的治学态度使我受益非浅．在此，同时感谢在我工作和学习中给予我帮助的各位领导和老师，也感谢在完成本文的过程中给予我很大帮助的我的几位同学．
最后，对各位老师审阅我的论文深表感谢，谢谢你们能仔细阅读我的原稿以及给出的宝贵意见，让我在这方面有了一定的进步并渴望给予批评指正．

16