原创】第二类型双圈图的距离矩阵的行列式-毕业论文

1、泛浪“人学科生毕业设计（论文）（2013 届）理学院题 目:专业班级:第二类型双圈图的距离矩阵的行列式信息与计算科学2013年5月15日1本科生毕业设计（论文）诚信承诺书我谨在此承诺：本人所写的毕业设计（论文） 第一类型双圈图的距 离矩阵的行列式均系本人独立完成，没有抄袭行为，凡涉及其它作者的 观点和材料，均作了引用注释，如出现抄袭及侵犯他人知识产权的情况， 后果由本人承担。承诺人（签名）：年 月关于第二类型双圈图的距离矩阵的行列式摘要在图论中，图形都有自己的距离矩阵，距离矩阵即是是一个包含一组点两两之间距离 的矩阵（即二维数组）。因此给定N个欧几里得空间中的点，其距离矩阵就是一个非负实数作为

2、元 素的NX n的对称矩阵。最简单的图形就是树，是由n个顶点和n_1条边组成的一个不存在回路的图。本文主要研究的是第二类型双圈图，即由n个顶点和n 1条边组成的存在两个回路且两个回路之间没有相交点的图形。我们的主要工作就是通过Matlab计算各个第二类型双圈图的距离矩阵的行列式并通过生成函数寻找其中的规律。关键词 距离矩阵；树;第二类型双圈图；生成函数ON THE DETERMINANT OF THE SECOND TYP GRAPHSAbstract: In graph theory, the graphics distanee matrix, distanee matrix that co

3、ntains a set point or two betwee n dista nee matrix (two-dime nsi onal array). Therefore, give n N poi nts in the Euclidea n space, the distanee matrix is a non-negative real numbers as elements of N x N symmetric matrix. The most simple graph is a tree, consisting of a non-existent by the vertices

4、and edges in the circuit of FIG . This paper studies the sec ond type of bicyclic graphs, graphics there is no point of in tersect ion betwee n the two loops and two loops composed by vertices and edges. Our main job is to calculate the determ inant of the matrix of dista nce of the sec ond type of

5、bicyclic graphs by use ing Matlab and by the generating function to find the law.Keywords: Distance matrices,tree,the second type of bicyclic graphs,generating function1 研究背景62 基本概念63 预备知识74 第二类型双圈图的行列式 104.1数据计算 104.2数据处理 13参考文献16致谢171研究背景图论从诞生至今已逾300年，在很多方面都有应用。随着现在技术的发展，代数图论是现在图论中的一个主要研究领域，也已有很长的

6、历史。图论的代数表示形式主要有：1. 图的Laplace矩阵2. 图的邻接矩阵研究者不断尝试图的其它矩阵表示1. 正规Laplace矩阵2. 混合图Laplace矩阵3. 无符号Laplace矩阵nJn_2即 -1 n-12近年来，图的距离矩阵越来越受到人们的关注，很多人已经对它进行了研究，其中最主要的 是在1971年，Graham和Pollack证明了树的距离矩阵的行列式是一个定值,2005年，R.bapat,S.j.Kirkland和M.Neumann等进一步研究了赋权树和单圈图的距离矩阵。本文安排如下：首先我们给出与本篇论文相关的一些概念和理论，如树、单圈图、双圈图、距离 矩阵、生成函数

7、。接下来我们将计算基本的第二类型双圈图以及通过加边而生成的图形的距离矩 阵的行列式并寻找它们之间的规律。2基本概念2.1距离矩阵对于一个图G(图1)，我们可以根据图G各个点之间的距离关系列出它的距离矩阵A =(aj人其中./、 I aijb,若 i = j ；、dis(i, j )若i Hj其中dis(i, j )表示j和j之间的距离。图1det G = -42.2树或者说，只要没有回路的连在图论中，树(图2)是任意两个顶点间有且只有一条路径的图。 通图就是树。定义：如果一个无向简单图 G满足以下相互等价的条件之一，那么G就是一棵树。(1) G是没有回路的连通图。(2) G没有回路，但是在 G

8、内添加任意一条边，就会形成一个回路。(3) G是连通的，但是如果去掉一条边，就不再连通。(4) G是连通的，并且 3顶点的完全图K3不是G的子图。(5) G内的任意两个顶点能被唯一路径所连通。(6) G是连通的，有n-1条边，并且G没有简单回路。图22.3单圈图定义：在图论中，单圈图即是由n个顶点和n条边组成的存在一个回路的图(图3,图4)。图3图4定理1.1 D是有2k 1个顶点的圈的距离矩阵，然后= -2I -Ck-Ck12k 1 JJk(k 1)定理1.2 G是一个有2k 1 m个顶点且长度为2k 1的单圈图。D是G的距离矩阵。则_-2k +1det(D) =(_2)m |k(k +1)

9、 +ml_H2 ，同时D的惯性由,n二(1,0,2k m)给出。定理1.3 G是一个有2k m个顶点切长度为2k的单圈图。D是G的距离矩阵。则 D的惯量是 n D , no D ,n_ D = 1,k -1,k m2.4双圈图一个含有n 1条边的连通图称为双圈图。第一类型双圈图：即由n个顶点和n 1条边组成的存在两个回路且两个回路之间没有相交边的图（图5）。图5第二类型双圈图：即由n个顶点和n 1条边组成的存在两个回路且两个回路之间没有相交点的图（图6）.图63预备知识定理1.距离矩阵A的行列式，记作 A，数域P上的矩阵的初等行变换是指下列三种变换:1）以P中一个非零的数乘矩阵的某一行；2）把

10、矩阵的某一行的 C倍加到另一行，这里 C是P中任意一个数；3）互换矩阵中两行的位置。定理2.把一矩阵A的行列互换，所得到的矩阵称为A的转置，记为 A。定理3.有时候我们把一个大矩阵看成是由一些小矩阵组成的，就如矩阵是由数组组成的一 样，特别是在运算中，把这些小矩阵当作数一样来处理，这就是所谓的矩阵的分块。定理4.生成函数：设数列a川的生成函数: kA(x)二話乂，数列的生成函数B（x）bkxkk，我们可以得到以下生成函数的性质:性质i(k ：)(k 卸)，则 B(x)=x A( x) o0bk = f若Uk J性质2若 bk 二 ak 1，则B(x)A(x)八 axk =0kxk。性质3B(x

11、)A(x)1 - x o4第二类型双圈图的距离矩阵的行列式4.1数据计算首先我们研究最基本的第二类型双圈图G（图7）,以后我们可以再研究类似图8这类的图形。图76图8我们把G称为基本图形，首先我们在G上加一条边，计算其距离矩阵的行列式的值，然后依次计算加两条边和加三条边的距离矩阵的行列式的值。然后猜想这些行列式的之间的关系。接下来我们可以计算以下各个加边的第二类型双圈图的距离矩阵的行列式并寻找它们的规律。以下是加两条边的情况:G21G22G24G25G27接下来是加三条边条边的各种情况:G3-3G34G3-5G3-6G30G3 J1G3_J2所以，可以得到fn = 4fn1 4fn2通过计算d

12、et Gi =detGi2胡2图形编号G21G22G23G24G25G26G27行列式值-32-32-32-32-32-32-32图像编号G3上G32G3-3G3rG3-5Q6G3_7G3-8Q_9行列式 的值808080808080808080G3T0G3T1G3T2G3-13G3T4G315G3T680808080808080只要加上的边的个数是相同的,从上面的计算结果可以知道对于一个基本的第二类型双圈图, 则他的距离矩阵的行列式的值是不变的。4.2数据处理接下来我们可以先研究下面这个图形1Gf对于Gf的距离矩阵的行列式，我们用:表示行向量，1表示值都是1的行向量,D是一个行列式，d是F的

13、转置图Gf 4和Gf 的距离矩阵的行列式正好可以表示为011+c10和1 11D1 +cfD，如果把021e + 1-1111-2011201d+11-1110-211110110e110E1 1d +11 1d +11D1 1d +11 1d +11D11111D-2200-4200-2110-2112-2110=410-4111001011D111111.fD11D01D011 +c0 d-410-411 11d D1 +dDGf的距离矩阵的行列式表达式记为f n，则GfJ和Gf总的距离矩阵的行列式分别为f n -1和 f n -2，即 f 3 = -4f 2 -4f 1。根据之前计算的结

14、果，可以证明该表达式是正确的。接下来我们用生成函数求解递推关系fn=-4fn-1-4fn-2Q0A x 八 f n xnn=0则有COAx - f 0 - f 1x八 f nxnn =2QO- L4 f n -1 -4 f n -2 xnn =2QOQO=-4x f n xn -4x2 f n xnn 4n =0二-4x A x A f 0 L 4x2 A x将f O = -4, f 1二12代入上式并整理，得4x41 2x2Ci1 2xC1 2x 2其中，C1，C2为待定系数，通过比较等式两边的常数项与一次项系数，可得e 弋2=-4、2G = Y所以，0- -2,C2 - -2. 1 1Ax

15、七厂兀辺飞7. n n2)x0oO一 2、_2nxn2、n z0n z0因此f n A-2 一2 n 一2 n 1 -2 n(_2)n 十2 n 一4一2n对于Gf这类加三条边的第二类型双圈图，将n二3代入上式可得f 3 严80 ；与之前的计算结果一致，所以f n = _2 n -4-2n为通项公式。参考文献1 R.B. Bap at. The Lap lacian matrix of a graph, Math. Stude nt 65 (1996) 214-223.2 N. Dyn, W.A. Light, E.W. Cheney, In terpolati on by piecewise

16、-l in ear radial basis functions I, J. Approx. Theory 59 (1989) 202 -223.3 R.L. Graham, H.O. Pollack, On the address ing problem for loop switch ing, Bell System Tech. J. 50(1971) 2495 -519.4 R.L. Graham, L. Lov sz, Distance matrix polynomials of trees, Adv. Math. 29 (1) (1978) 60-88.5 Edward J. Kap

17、lan, 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, Laplacia n matrices of graphs: a survey, Lin ear Algebra Appl. 197198 (1994) 143 -76.8 T. Parthasarathy, G. Ravi ndran, N-matrices, Li near Alge

18、bra Appl. 139 (1990) 89 -102.9 L. Reid, X. Sun, Distance matrices and ridge function interpolation, Can. J. Math. 45 (6) (1993)1313 -323.10 X. Sun, Solvability of multivariate interpolation by radial or related functions, J. Approx. Theory 72(3) (1993) 252 t267.11 王蕚芳，石生明，高等代数M.高等教育出版社，2003:290.12 王贵平，王衍，任嘉辰.图论算法理论、实现及应用 M,北京：北京大学出版社,2011: 88.13 许胤龙，孙淑玲，组合数学引论 M.中国科学技术大学出版社， 2010: 4.14 胡良