图的关联矩阵

图的关联矩阵的研究摘要利用矩阵的形式来对图进行表示，不仅在理论方面便于用代数知识对图进行研究，而且也便于计算机对图进行处理，在图论的应用中具有极其重要的意义，图的关联矩阵是用来表示的图中结点与边的关系，本文首先对图的定义及分类进行描述，再对图中的结点和边的一些性质进行描述，同时对数域和线性空间的定义进行叙述。其次我们对有向图和无向图中的关联矩阵进行描述，通过举例，让我们更加直观的理解关联矩阵。接下来我们结合线性代数的知识，简明地证明了具有n个顶点无向图G的关联矩阵的秩为nT,接下来我们引入了积和式的定义，然后证明了一类连通图的积和式的计值关键词:图完全图数域线性空间关联矩阵积和式ResearchontheIncidenceMatrixofGraphsABSTRACTUsingthefonnofmatrixtorepresenttliegraph,notonlyintlieoiytofacilitatetlieuseofalgebraknowledgetostudythemap,butalsotofacilitatetliecomputertodealwiththemap,intheapplicationofgraphtheoiyhasaveiynnpoitantsignificance,thegraphisassociatedwiththematrixIntinspaper,v/efii'stdesci'ibethedefinitionandclassificationofgraphs,andtliendescribethevanouspropertiesofnodesandedgesinthegraph,anddesci'ibethedefinitionoflogai'ithmicdomainandlinearspaceSecondly,wedescribetheassociativemati'icesindirectedgraphsandundirectedgraphsBywayofexample,letusunderstandtheassociativemah'icesmorenituitivelyThenwecombinetlieknowledgeoflinearalgebratoprovetherankofn-1withtliecoirelationmatrixofnvertexundirectedgraphsG,Thenweintroducethedefinitionofjpeinianent,andthenprovethataclassofconnectedgiaphsoftheproductandthetypeofvalueKeywords：GraphCompletegraphNumberfieldLinearspaceIncidencematrixpermanent;目录TOC\o"1-5"\h\z第1章绪论1第2章图的关联矩阵5关联矩阵的定义5.关联矩阵的举例及其简单应用6第3章第4章致谢16参考文献17III第第9页共17页成一道工序且每名员工完成工序互不相同，这6名员工是否可以让流水线顺利工作或者是否需要再指派员工才可以让流水线正常作业？解:利用关联矩阵的思想，我们可以建立数学模型，将员工A,B,C,D,E,F分别取代关联矩阵中顶点所对应的位置，工序Xi,X2,X3,X4,X5,X6依次取代关联矩rl01rl0100Lio001000110-1TOC\o"1-5"\h\z0101100000001000100oJ矩阵M的每行中有几个1就代表该行对应的员工可以做几道工序，每一列有几个1则代表该列所对应的工序有几个人可以做，从上面的矩阵M中我们可以看出员工D只掌握处这道工序，员工E只掌握&这道工序，沟,X4fX5这三道工序只有A,B两名员工掌握。因为同一时间一名员工只可以完成一道工序，所以对于这6名员工不管怎么安排，都有一道工序没有人做，所以为了流水线顺利工作，需要再指派一名至少会为，X,,XS这三道工序中的一道的员工；（2）利用矩阵的形式来对图进行表示，不仅在理论方面便于用代数知识对图进行研究，而且也便于计算机对图进行处理，在图论的推广应用中具有极其重要的意义，例如在运筹学中求图的最大匹配⑸和寻求图中最大生成树⑹的问题，图的关联矩阵的思想在网络设计和数学建模中应用也颇为广泛。在数学建模中应用关联矩阵法，多多目标的系统从多个角度进行考虑，综合评价各个指标的适合程度，然后用矩阵表示各个设定方案评价指标的评价值，然后再计算各个方案的评价指标的加权值，再通过一定的分析比较，确定最优的方案为评价指标加权值的和最大的方案，其主要步骤依次为：确定评价指标体系，确立权重体系，给出单项指标的评价标准，最后为对方案进行综合评价得出结论;致谢导师具有深厚的专业知识素养、一丝不苟的治学态度，止于至善的工作作风，诲人不倦的高尚师德，作为一个长者，导师常面带微笑，怀有平易近人的人格魅力，让人如沐春风，在导师的启发督促下回顾四年学习的相关课程基础之上，笔者查阅了大量文献资料，通过不断学习钻研，不仅让本人树立坚定的学习目标、同时还掌握了一些基本的研究方法，在督促引导学习思考之余，导师也传授了一些为人处事的道理，每每一语中的，让我反省了一些自己学习生活中存在的问题。本次论文从题目的确定到完成，每一过程都在导师的启发和指导下完成的，花费了老师的大量时间精力。在此，谨向导师表示衷心的谢意，，在完成论文的过程中，遇到了很多的疑点和难点，都是在老师的耐心引导启发下，问题才都得到圆满解决。所以再次对老师表达一下自己的谢意，老师，谢谢您！参考文献⑴殷剑宏，吴开亚编著.图论及其算法[M].合肥：中国科学技术大学出版社，2003.7.⑵林翠琴编著.组合学与图论[M].北京：清华大学出版社,2009.4.[3]许胤龙，孙淑玲编著.-3板.组合数学引论[M].合肥：中国科学技术大学出版社，2010.4.[4]胡运权主编.运筹学教程[M].北京：清华大学出板社,2012.11.⑸李世群.简单图的最大匹配的矩阵求法[J].数学的实践与认识，2007,37(7):120-124.⑹李斌.简单有向连通图关联矩阵右逆的图特征及应用[J].重庆大学学报：自然科学版，2000,23(2):34-38.[7]北京大学数学系几何与代数研究室前代数小组编./r/