矩阵在图论中的应用
矩阵在图论中的应用
摘要
图可以用矩阵表示,图中顶点与顶点之间关系、顶点与边之间关系、边与回路的关系,都可以用矩阵来表示。本文章所涉及的只是图论中的1些基本概念和理论,将图用矩阵(关联矩阵、邻接矩阵)表示,在方法上应用矩阵来研究图的1些性质。用矩阵表示1个图的各种关系,不仅是给出图的1种表示方法,而且可以充分利用矩阵代数中的各种运算,来研究图的结构特征及性质,这样便于用计算机处理图。
关键词:矩阵;图;关联矩阵;邻接矩阵;回路;2部图
The Implication of Matrix for Graph
Abstract
Graph can be denoted by matrix. In the graph , all the correlations such as two vertexes, the vertex with the sideline, and the sideline with the cycle can be illustrated through the matrix . This paper involves only some basic concepts and theory in the graph. It’s committed to exercise the matrix theory to do some hart operation based on the affiliated matrix and the adjacency matrix , and make efforts to do some research on the characteristics of graph. Matrix can represent each kind of relations of graph ,not only give one expression method of graph, moreover can fully use operation in the matrix algebra, studing the structure characteristic and the nature of graph ,bringing much convenience to the graph processing in computer.
Key words: matrix;graph; affiliated matrix; adjacency matrix; cycle; bipartite graph
1 引言
图论是近210年来发展10分迅速、应用比较广泛的1个新兴的数学分支,在许多领域,诸如物理学、化学、运筹学、信息论、控制论、计算机等方面甚至在生产生活中都有广泛的应用。因此受到全世界越来越广泛的重视。图论的内容10分丰富,涉及面也比较广。本文章所涉及的只是图论中的1些基本概念和理论,在方法上应用矩阵来研究图的1些性质。用矩阵表示1个图的各种关系,不仅是给出图的1种表示方法,而且可以充分利用矩阵代数中的各种运算,来研究图的结构特征及性质,且便于计算机处理。用矩阵表示图,必须首先将图的顶点、边等分别按照某种顺序排列,然后并按照这种顺序依次给定惟1标号,使其成为标号图,最后给出其矩阵表示。 本文通过运用邻接矩阵和关联矩阵的特征,把图的运算转化成矩阵的运算,这就包括图的点边运算、求补图运算、图的交和并运算、图的边的收缩。运用图的1些性质,转化为矩阵,进而判断图是否具有其他性质,这就包括用邻接矩阵判断图的回路,判断图是否为2部图。
【包括:毕业、、任务书】 【说明:中有些数学符号是编辑器编辑而成,网页上无法显示或者显示格式错误,给您带来不便请谅解。】
本文档为【矩阵在图论中的应用】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。