毕业设计（论文）-关于图的Fielder向量及其应用.doc

陕西理工学院毕业论文 题 目 关于图的fielder向量及其应用 学生姓名 学号 所在学院 数学与计算机科学学院 专业班级 数教1102班 指导教师 完成地点 陕西理工学院 2015年06月12日本科毕业论文任务书院(系) 数学与计算机科学学院 专业班级 数教1102班 学生姓名 一、毕业论文题目 关于图的fielder向量及其应用 二、毕业论文工作自 2015 年 3 月_ 10_日 起至 2014 年 6 月 20 日止三、毕业论文进行地点: 陕西理工学院 四、毕业论文内容要求：利用已有的计算fielder向量的一种新方法,并了解图的fielder向量在刻画图的结构及其连通性方面的应运用.要求：（1）论文内容要条理清楚、文字表达要准确、推理过程要准确无误;（2）论文格式要按照学院要求的规范格式严格书写;（3）论文字数（包括符号）不少于6000字;（4）独立完成毕业论文,严禁弄虚作假和整篇抄袭他人成果;论文的电子版必须自己动手输入文字和符号,所用的图像（或图形）也必须自己画,严禁复制粘贴他人的文字、符号和图像等.指 导 教 师 系(教 研 室) 系(教研室)主任签名 批准日期 接受设计任务开始执行日期 学生签名 关于图的fielder向量及其应用(陕理工学院数学与计算机科学学院数教1102班,陕西 汉中 723000)指导教师： 【摘要】 基于图的fielder向量方法,本文总结了求图的fielder向量的方法,讨论了图的fielder向量与图的连通性的关系,并用实例说明了该方法在判断图的连通性方面的应用. 【关键词】 fielder向量;laplace矩阵;特征值;特征向量;图的连通性1 引 言在图论中,有很多性质,人们为了更加深入的了解图论,开始研究图的性质,文献1-5,7-8,11中都有体现.图的fielder向量就是图的众多性质之一.图的fielder向量是图的laplace矩阵的次小特征值所对应的特征向量,在参考文献1,15中有提及.然而要计算图的fielder向量就必须通过图的laplace矩阵来计算,在参考文献1,4-5,8中因均有提及.此外,图的fielder向量可以解决和图论有关的许多问题,其中包括在文献1和11中提及的图的连通性、矩阵的重排、图分割、蛋白质分析与数据挖掘、机器学习与网络搜索等.本文总结和概括例求fielder向量的方法和步骤.先给出的是图的laplace矩阵的有关概念以及求法,利用laplace矩阵的次小特征值求其所对应的特征向量（即图的fielder向量）,再利用其判断图的连通性.2 预备知识2.1 图的概念称数学结构为一个图,其中是非空集合,是从集合到的一个映射,则称是一个以为顶集合.以为边集合的有向图,中的元素称为图的顶点,中的元素称为的边,称为g的关联函数,若,则简写为;称是有向边的尾,为有向边的头.若,时,称为有限图,否则为无限图6.一般,把中的元素表示成中的元素,记做.所以就可以简单的记为.（1） 边的端点：时,称顶与是边的端点.（2） 边与顶相关联：若边的端点是与,则称与,相关联.（3） 邻顶：同一条边的两个端点叫做邻顶.（4） 邻边：与同一个顶点相关联的两条边叫做邻边.（5） 环：只与一个顶相关联的边叫做环.（6） 重边：,则称与是重边.（7） 单图：无环无重边的图.（8） 完全图：任二顶皆相邻的图,记之为.(完全图有两个特点：如果完全图有个顶点,则每个顶点的度都是.如果完全图有个顶点,则边的总数为)3.（9） 二分图：,且中任二顶不相邻,中任二顶不相邻,则称为二分图;若中每个顶皆与中一切顶相邻,则称为完全二分图,记成,其中8.（10） 阶：表示图中顶点个数,记为.（11） 顶点的度：某个顶点关联的边的条数（环的个数）. 定义16在顶边交错链中,;且,则称是的一条道路.其中允许或,.称是的起点,是的终点,为路长,称为的内点,各边相异的道路称为行迹,各顶相异的道路称为轨道,记成.起点与终点重合的道路称为回路;起点与终点重合的轨道称为圈,长的圈称为阶圈;两顶的距离是指与为起止点的最短轨道之长度,记成;如果存在道路以为起止顶,则称与在图中连通.若图中任意两个顶点皆连通,则称图为连通图.2.2 图的性质2.2.1 同构如果图和图的顶点集分别是和,且他们可以一一对应起来,并且这种对应是保持边的,即就是存在双射,使得当且仅当,就称图和图是同构的,并且称是它们之间的同构映射.我们一般认为同构的图是一样的,如何判断两个图是同构的是图论中一个非常重要的问题9.2.2.2 子图如果图满足,就称是的子图,阶数等于的子图称为图的支撑图,若,则用表示由生成的子图,也称导出子图.其顶点集为,中两点相邻且仅当它们在图中相邻3.2.2.3 连通图如果无向图中任意两点之间都至少存在一条路相连,则称这样的图为连通图,图中的极大连通子图称为联通分支,若图是连通图,则它只有一个联通分支,就是它本身;若图不是连通图,则联通分支大于13.2.2.4 图的定向在无向图中,与顶点关联的边的数目称为顶点的度,记做.如果将它的每条边都给定一个方向,使其成为一个有向图,我们把这种做法叫做无向图的一个定向.图中的边,假设我们规定它的方向是由点指向点,则把顶点叫做边的起点,把顶点叫做这条边的终点.在这个有向图中,以顶点为起点的有向边的数目称为是顶点的出度,记为,以顶点为点的有向边的数目称为顶点的入度,记做,在不引起混淆的前提下一般都把它们记做和.如果与顶点关联的边在定向中都是以为起点,则我们就把称为有向图的一个源;同样的,如果与顶点关联的边在定向中都是以为终点,则我们把称作是有向图的一个汇,在给一个无向图的边定向后,如果定向图中不含有向圈,则我们把这个定向称作是无圈定向10.3 图的fielder向量3.1 laplace矩阵3.1.1 邻接矩阵设是无向图,我们根据的顶与顶点之间是否相邻,编写一个方阵,1表示相邻,0表示不相邻,严格定义如下7： 称为无向图的邻接矩阵,其中, (3-1)例1 求图-1的邻接矩阵图-1 解 图-1的邻接矩阵为一般而言,任何图的邻接阵的主对角线皆为零,完全图的充要条件是其邻接矩阵除主对角线外,其余元素皆为1.每个图的邻接矩阵皆为关于主对角线的0-1对称矩阵. 对于有多个顶点的简单无向图,其顶点集为边集为.令为图的邻接矩阵,其中时,顶点与有边连接;否则,.3.1.2 度矩阵 设是无向图,根据的每个顶点关联的边的条数,构成一个方阵,其中表示顶点的度数.图-1的度矩阵为. 显然,图的度矩阵是对角阵,只有对角线上的元素非零,其余元素均为零. 一般的对于有多个顶点的简单无向图,设其顶点集为,边集为 .则为的顶点度矩阵,其中是顶点的度数2.3.1.3 laplace矩阵 由上述所给的邻接矩阵以及顶点度矩阵可以的到laplace矩阵如下14：, (3-2)其中就是度矩阵,就是邻接矩阵.图-1的laplace矩阵为： = - =.图的laplace矩阵有一个很好的性质,即laplace矩阵的每一行和每一列之和为零.3.1.4 fielder向量令表示顶点的度,表示的第大的度,即有3, (3-3)或表示图的顶点数.在图的拉普拉斯矩阵中, (3-4)是图的度对角矩阵.对图的每一条边,取其一个端点为始点,另一个端点为终点,这一过程称为给图一个定向.当图取定义定向时其定向关联矩阵定义为,其中2,= (3-5) 则(其中是的转置矩阵)且与的定向无关.容易证明：是一个半正定的、对称的实矩阵,且它的每一行的行和为零,因此又是奇异的1.假设它的特征值按照从小到大的顺序排列为13, (3-6)称为图的第大拉普拉斯特征值.设是图的相应于的一个特征向量,则中的分量可以与图的顶点之间建立一个一 一对应关系,称为给的点赋值.我们常将对应于点的中的分量记为）或.特别地,假如x是相应于的单位特征向量,则有2. (3-7)对的每个分量取绝对值,得到一个新的向量记作.fielder证明11：图是联通的当且仅当的第二个最小的拉普拉斯特征值.因此, fielder称为图的代数连通度,记为.称对应于的特征向量为fielder向量.对于例1中的简单图,根据定义求出它的拉普拉斯第二小特征值,继而求出其所对应的特征向量,亦即fielder向量.由图-1可知则矩阵的特征多项式为 = = =,所以特征值是=4,=3（二重）,=2.由此可知该图的拉普拉斯矩阵的最小特征值是2,第二小特征值是3,那么我们把3代入其次方程组得到方程组则该方程组的系数矩阵为则它的增广矩阵为因为系数矩阵的秩为=4,增广矩阵的秩为=4,所以=4.故方程组有唯一解=0,从而图的fielder向量为,即为零向量. 例2 求图-2的fielder向量 图-2 解 由图可知图的邻接矩阵为,度矩阵为laplace矩阵为容易求得,图的laplace矩阵的所有特征值,按从大到小的顺序排列为：,=1（二重）,.于是图的laplace矩阵的第二小特征值为,把带入下面的齐次方程组得到方程组解得,.所以此图的fielder向量为（其中为任意实数）.求fielder向量的步骤可以归纳如下：第一步：写出图的邻接矩阵和度矩阵.第二步：用图的度矩阵和邻接矩阵做差求出图的laplace矩阵即.第三步：求出laplace矩阵的所有特征值,并按从大到小的顺序排列,则就是图的laplace矩阵的次小特征值.第四步：根据第三步求出次小特征值求其所对应的特征向量即就是所要求的fielder向量.4 运用图的fielder向量判断图的连通性由前面的fielder证明可知,图是联通的当且仅当的第二个最小的拉普拉斯特征值 (即图的fielder向量所对应的特征值）.因此,被fielder称为是图的代数连通度,记为.下面我们给出两个通过比较与0的大小关系来判断图的连通性：例3 判断图-3的连通性： 图-3解 由图可知图的邻接矩阵为度矩阵为则图的laplace矩阵为则由求得laplace矩阵的所有特征值,按从大到小的顺序为=4（二重）,=3,=2,.很明显图的laplace矩阵的第二小特征值（fielder向量所对应特征值）为所以该图是联通图.例4 判断图-2的连通性 图-2 解 由图可知图的邻接矩阵为度矩阵为 laplace矩阵为则通过求图的laplace矩阵的所有特征值,按从大到小的顺序排列为,=1（二重）,.即图的laplace矩阵的第二小特征值为 亦即,所以该图是连通图.5 基于fielder向量的基因表达谱数据分类方法利用基因表达数据进行癌症的分类与识别是当前生物信息学研究的主要方向之一.很多科学家尝试将一种基于图的fielder向量的聚类算法引入到基因表达谱数据的肿瘤分类中来.该方法将分属不同类的所有样本通过高斯权构造laplace完全图, 经svd分解后获得fielder向量,利用各个样本所对应的fielder向量的分量的符号差异来进行基因表达谱数据的分类.通过模拟数据仿真实验和对白血病两个亚型(all与aml)及结肠癌真实数据实验12.6 结束语图的fielder向量即就是图的laplace矩阵的次小特征值所对应的向量.在fielder向量的应用中较为普遍的是通过fielder向量所对应的特征值与零的大小关系来判断图的连通性,当时,图是连通的;相反当时,图是不连通的.参考文献1 尚文.图的最大和次小拉普拉斯特征值a.硕士论文.成都:电子科技大学,2005,31-38.2 郭继明.图的拉普拉斯特征值d.博士学位论文.上海:同济大学理学院,2006,3-4.3 梁昊.图的拉普拉斯矩阵和临界群d.博士学位论文.中国科学技术大学,2009,4-5.4 张晓东,李炯生. 树的laplace矩阵的最大和次大特征值 j .中国科学技术大学学报, 1998, 28( 5): 513- 518.5 郭曙光.单圈图的laplace矩阵的最大特征值 j .高校应用数学学报, 2001, 16a: 131- 136.6 王树禾.图论m.北京:科学出版社,20009,10-11.7 孙房,徐美进,支路.图的拟拉普拉斯矩阵的永久式j.辽宁工业大学学报,2008,28(6):1-2.8 张海霞.关于图的laplace特征值a.硕士论文.大连理工大学,2005,4-15.9 李锋,陆韬.任意图同构判定及其应用j.上海:复旦大学学报,2006,45(4):1-2.10 张雪飞,王世英.完全偶图的定想图j.山西大学学报,2013,26(3):2-3.11 龚世才.图的特征向量的组合结构d.博士学位论文.安徽大学,2010,1-3.12 王年,庄振华,唐俊,苏亮亮.基于fielder向量的基因表达谱数据分类方法j.中国生物杂志,2010,30(12):82-86.13 lijianxi ,guo ji-ming .the smallest values of algebraic connectivity for unicyclic graphsj.journal of zhangzhou normal university,zhangzhou fujian,china,2010,1635:1-2.14 zhangxiao dong,two sharp upper bounds for the laplace eigenvaluesj.linear algebra and its applicati-ons, 2004,376:207-213.15 fi