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

浙江农林大学本科生毕业设计（论文）本 科 生 毕 业 设 计（论文）（ 2013 届）理学院题 目： 第二类型双圈图的距离矩阵的行列式 学生姓名： 章叶锋 学 号： 200911040223 专业班级： 信息与计算科学 指导教师： 龚世才 职称： 教授 2013 年 5 月 15 日浙江农林大学本科生毕业设计（论文）本科生毕业设计（论文）诚信承诺书我谨在此承诺：本人所写的毕业设计（论文）第一类型双圈图的距离矩阵的行列式均系本人独立完成，没有抄袭行为，凡涉及其它作者的观点和材料，均作了引用注释，如出现抄袭及侵犯他人知识产权的情况，后果由本人承担。 承诺人（签名）： 年 月 日 关于第二类型双圈图的距离矩阵的行列式摘要 在图论中，图形都有自己的距离矩阵，距离矩阵即是是一个包含一组点两两之间距离的矩阵(即二维数组)。因此给定N个欧几里得空间中的点, 其距离矩阵就是一个非负实数作为元素的NN的对称矩阵。最简单的图形就是树，是由个顶点和条边组成的一个不存在回路的图。本文主要研究的是第二类型双圈图，即由个顶点和条边组成的存在两个回路且两个回路之间没有相交点的图形。我们的主要工作就是通过Matlab计算各个第二类型双圈图的距离矩阵的行列式并通过生成函数寻找其中的规律。关键词 距离矩阵;树;第二类型双圈图;生成函数ON THE DETERMINANT OF THE SECOND TYP GRAPHSAbstract：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 研究背景.62 基本概念.63 预备知识.74 第二类型双圈图的行列式 .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.Kirkland和M.Neumann等进一步研究了赋权树和单圈图的距离矩阵。本文安排如下：首先我们给出与本篇论文相关的一些概念和理论，如树、单圈图、双圈图、距离矩阵、生成函数。接下来我们将计算基本的第二类型双圈图以及通过加边而生成的图形的距离矩阵的行列式并寻找它们之间的规律。2基本概念2.1 距离矩阵 对于一个图(图1)，我们可以根据图各个点之间的距离关系列出它的距离矩阵，其中：其中表示和之间的距离。 图12.2 树 在图论中，树(图2)是任意两个顶点间有且只有一条路径的图。 或者说，只要没有回路的连通图就是树。 定义：如果一个无向简单图满足以下相互等价的条件之一，那么就是一棵树。(1) 是没有回路的连通图。(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 双圈图一个含有条边的连通图称为双圈图。第一类型双圈图：即由个顶点和条边组成的存在两个回路且两个回路之间没有相交边的图(图5)。 图5第二类型双圈图：即由个顶点和条边组成的存在两个回路且两个回路之间没有相交点的图(图6). 图63预备知识定理1. 距离矩阵的行列式，记作，数域上的矩阵的初等行变换是指下列三种变换：1)以中一个非零的数乘矩阵的某一行；2)把矩阵的某一行的倍加到另一行，这里是中任意一个数；3)互换矩阵中两行的位置。定理2. 把一矩阵的行列互换，所得到的矩阵称为的转置，记为。定理3. 有时候我们把一个大矩阵看成是由一些小矩阵组成的，就如矩阵是由数组组成的一样，特别是在运算中，把这些小矩阵当作数一样来处理，这就是所谓的矩阵的分块。定理4.生成函数:设数列的生成函数，数列的生成函数，我们可以得到以下生成函数的性质：性质1 若 ，则。性质2 若，则。性质3若，则。4第二类型双圈图的距离矩阵的行列式4.1数据计算首先我们研究最基本的第二类型双圈图(图7)，以后我们可以再研究类似图8这类的图形。 图7 图8我们把称为基本图形，首先我们在上加一条边，计算其距离矩阵的行列式的值，然后依次计算加两条边和加三条边的距离矩阵的行列式的值。然后猜想这些行列式的之间的关系。接下来我们可以计算以下各个加边的第二类型双圈图的距离矩阵的行列式并寻找它们的规律。 以下是加两条边的情况： 接下来是加三条边条边的各种情况： 通过计算图形编号行列式值-32-32-32-32-32-32-32图像编号行列式的值8080 8080808080808080808080808080从上面的计算结果可以知道对于一个基本的第二类型双圈图，只要加上的边的个数是相同的，则他的距离矩阵的行列式的值是不变的。4.2数据处理接下来我们可以先研究下面这个图形。 对于的距离矩阵的行列式，我们用表示行向量，表示值都是1的行向量，是一个行列式，是的转置 。=图和的距离矩阵的行列式正好可以表示为和，如果把的距离矩阵的行列式表达式记为，则和的距离矩阵的行列式分别为和，即。所以，可以得到。根据之前计算的结果，可以证明该表达式是正确的。接下来我们用生成函数求解递推关系令 则有将代入上式并整理，得设其中，为待定系数，通过比较等式两边的常数项与一次项系数，可得所以，因此 对于这类加三条边的第二类型双圈图，将代入上式可得；与之前的计算结果一致,所以 为通项公式。参考文献1 R.B. Bapat, The Laplacian matrix of a graph, Math. Student 65 (1996) 214223.2 N. Dyn, W.A. Light, E.W. Cheney, Interpolation by piecewise-linear radial basis functions I, J. Approx. Theory 59 (1989) 202223.3 R.L. Graham, H.O. Pollack, On the addressing problem for loop switching, Bell System Tech. J. 50(1971) 24952519.4 R.L. Graham, L. Lovsz, Distance matrix polynomials of trees, Adv. Math. 29 (1) (1978) 6088.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) 365369.7 R. Merris, Laplacian matrices of graphs: a survey, Linear Algebra Appl. 197/198 (1994) 143176.8 T. Parthasarathy, G. Ravindran, N-matrices, Linear Algebra Appl. 139 (1990) 89102.9 L. Reid, X. Sun, Distance matrices and ridge function interpolation, Can. J. Math. 45 (6) (1993)13131323.10 X. Sun, Solvability of multivariate interpolation by radial or related functions, J. Approx. Theory 72(3) (1993) 252267.11王蕚芳,石生明,高等代数M.高等教育出版社,2003:290.12王贵平,王衍,任嘉辰. 图论算法理论、实现及应用M,北京：北京大学出版社,2011：88.13许胤龙，孙淑玲，组合数学引论M.中国科学技术大学出版社，2010：4.14胡良剑，孙晓君，MATLAB数学实验M.高等教育出版社，2006:6.致谢本论文在选题和撰写过程中都得到了龚世才老师的精心指导不论是在工作上还是在日常生活中，龚老师给了我无微不至的关怀特别是在学习和工作中，龚老师广博的学识给予了我很大的帮助和支持在此，我表示由衷的感谢另外，龚老师严谨治学的学术作风和兢兢业业的治学态度使我受益非浅在此，同时感谢在我工作和学习中给予我帮助的各位领导和老师，也感谢在完成本文的过程中给予我很大帮助的我的几位同学最后，对各位老师审阅我的论文深表感谢，谢谢你们能仔细阅读我的原稿以及给出的宝贵意见，让我在这方面有了一定的进步并渴望给予批评指正1. 基于C8051F单片机直流电动机反馈控制系统的设计与研究2. 基于单片机的嵌入式Web服务器的研究 3. MOTOROLA单片机MC68HC（8）05PV8/A内嵌EEPROM的工艺和制程方法及对良率的影响研究 4. 基于模糊控制的电阻钎焊单片机温度控制系统的研制 5. 基于MCS-51系列单片机的通用控制模块的研究 6. 基于单片机实现的供暖系统最佳启停自校正（STR）调节器7. 单片机控制的二级倒立摆系统的研究8. 基于增强型51系列单片机的TCP/IP协议栈的实现 9. 基于单片机的蓄电池自动监测系统 10. 基于32位嵌入式单片机系统的图像采集与处理技术的研究11. 基于单片机的作物营养诊断专家系统的研究 12. 基于单片机的交流伺服电机运动控制系统研究与开发 13. 基于单片机的泵管内壁硬度测试仪的研制 14. 基于单片机的自动找平控制系统研究 15. 基于C8051F040单片机的嵌入式系统开发 16. 基于单片机的液压动力系统状态监测仪开发 17. 模糊Smith智能控制方法的研究及其单片机实现 18. 一种基于单片机的轴快流CO,2激光器的手持控制面板的研制 19. 基于双单片机冲床数控系统的研究 20. 基于CYGNAL单片机的在线间歇式浊度仪的研制 21. 基于单片机的喷油泵试验台控制器的研制 22. 基于单片机的软起动器的研究和设计 23. 基于单片机控制的高速快走丝电火花线切割机床短循环走丝方式研究 24. 基于单片机的机电产品控制系统开发 25. 基于PIC单片机的智能手机充电器 26. 基于单片机的实时内核设计及其应用研究 27. 基于单片机的远程抄表系统的设计与研究 28. 基于单片机的烟气二氧化硫浓度检测仪的研制 29. 基于微型光谱仪的单片机系统 30. 单片机系统软件构件开发的技术研究 31. 基于单片机的液体点滴速度自动检测仪的研制32. 基于单片机系统的多功能温度测量仪的研制 33. 基于PIC单片机的电能采集终端的设计和应用 34. 基于单片机的光纤光栅解调仪的研制 35. 气压式线性摩擦焊机单片机控制系统的研制 36. 基于单片机的数字磁通门传感器 37. 基于单片机的旋转变压器-数字转换器的研究 38. 基于单片机的光纤Bragg光栅解调系统的研究 39. 单片机控制的便携式多功能乳腺治疗仪的研制 40. 基于C8051F020单片机的多生理信号检测仪 41. 基于单片机的电机运动控制系统设计 42. Pico专用单片机核的可测性设计研究 43. 基于MCS-51单片机的热量计 44. 基于双单片机的智能遥测微型气象站 45. MCS-51单片机构建机器人的实践研究 46. 基于单片机的轮轨力检测 47. 基于单片机的GPS定位仪的研究与实现 48. 基于单片机的电液伺服控制系统 49. 用于单片机系统的MMC卡文件系统研制 50. 基于单片机的时控和计数系统性能优化的研究 51. 基于单片机和CPLD的粗光栅位移测量系统研究 52. 单片机控制的后备式方波UPS 53. 提升高职学生单片机应用能力的探究 54. 基于单片机控制的自动低频减载装置研究 55. 基于单片机控制的水下焊接电源的研究 56. 基于单片机的多通道数据采集系统 57. 基于uPSD3234单片机的氚表面污染测量仪的研制 58. 基于单片机的红外测油仪的研究 59. 96系列单片机仿真器研究与设计 60. 基于单片机的单晶金刚石刀具刃磨设备的数控改造 61. 基于单片机的温度智能控制系统的设计与实现 62. 基于MSP430单片机的电梯门机控制器的研制 63. 基于单片机的气体测漏仪的研究 64. 基于三菱M16C/6N系列单片机的CAN/USB协议转换器 65. 基于单片机和DSP的变压器油色谱在线监测技术研究 66. 基于单片机的膛壁温度报警系统设计 67. 基于AVR单片机的低压无功补偿控制器的设计 68. 基于单片机船舶电力推进电机监测系统 69. 基于单片机网络的振动信号的采集系统 70. 基于单片机的大容量数据存储技术的应用研究 71. 基于单片机的叠图机研究与教学方法实践 72. 基于单片机嵌入式Web服务器技术的研究及实现 73. 基于AT89S52单片机的通用数据采集系统 74. 基于单片机的多道脉冲幅度分析仪研究 75. 机器人旋转电弧传感角焊缝跟踪单片机控制系统 76. 基于单片机的控制系统在PLC虚拟教学实验中的应用研究77. 基于单片机系统的网络通信研究与应用 78. 基于PIC16F877单片机的莫尔斯码自动译码系统设计与研究79. 基于单片机的模糊控制器在工业电阻炉上的应用研究 80. 基于双单片机冲床数控系统的研究与开发 81. 基于Cygnal单片机的C/OS-的研究82. 基于单片机的一体化智能差示扫描量热仪系统研究 83. 基于TCP/IP协议的单片机与Internet互联的研究与实现 84. 变频调速液压电梯单片机控制器的研究 85. 基于单片机-免疫计数器自动换样功能的研究与实现 86. 基于单片机的倒立摆控制系统设计与实现 87. 单片机嵌入式以太网防盗报警系统 88. 基于51单片机的嵌入式Internet系统的设计与实现 89. 单片机监测系统在挤压机上的应用 90. MSP430单片机在智能水表系统上的研究与应用 91. 基于单片机的嵌入式系统中TCP/IP协议栈的实现与应用92. 单片机在高楼恒压供水系统中的应用 93. 基于ATmega16单片机的流量控制器的开发 94. 基于MSP430单片机的远程抄表系统及智能网络水表的设计95. 基于MSP430单片机具有数据存储与回放功能的嵌入式电子血压计的设计 96. 基于单片机的氨分解率检测系统的研究与开发 97. 锅炉的单片机控制系统 98. 基于单片机控制的电磁振动式播种控制系统的设计 99. 基于单片机技术的WDR-01型聚氨酯导热系数测试仪的研制 100. 一种RISC结构8位单片机的设计与实现 101. 基于单片机的公寓用电智能管理系统设计 102. 基于单片机的温度测控系统在温室大棚中的设计与实现103. 基于MSP430单片机的数字化超声电源的研制 104. 基于ADC841单片机的防爆软起动综合控制器的研究105. 基于单片机控制的井下低爆综合保护系统的设计 106. 基于单片机的空调器故障诊断系统的设计研究 107. 单片机实现的寻呼机编码器 108. 单片机实现的鲁棒MRACS及其在液压系统中的应用研究 109. 自适应控制的单片机实现方法及基上隅角瓦斯积聚处理中的应用研究110. 基于单片机的锅炉智能控制器的设计与研究 111. 超精密机床床身隔振的单片机主动控制 112. PIC单片机在空调中的应用 113. 单片机控制力矩加载控制系统的研究 项目论证，项目可行性研究报告，可行性研究报告，项目推广，项目研究报告，项目设计，项目建议书，项目可研报告，本文档支持完整下载，支持任意编辑！选择我们，选择成功！项目论证，项目可行性研究报告，可行性研究报告，项目推广，项目研究报告，项目设计，项目建议书，项目可研报告，本文档支持完整下载，支持任意编辑！选择我们，选择成功！单片机论文，毕业设计，毕业论文，单片机设计，硕士论文，研究生论文，单片机研究论文，单片机设计论文，优秀毕业论文，毕业论文设计，毕业过关论文，毕业设计，毕业设计说明，毕业论文，单片机论文，基于单片机论文，毕业论文终稿，毕业论文初稿，本文档支持完整下载，支持任意编辑！本文档全网独一无二，放心使用，下载这篇文档，定会成功！18