邻接矩阵的应用
时间:2019-08-23 13:05 来源:毕业论文 作者:毕业论文 点击:次
| 摘 要：本文首先给出了图的基本概念，接着给出了有向图和无向图的邻接矩阵的定义；其次，总结了邻接矩阵在离散数学，数据结构等方面的应用，主要包括如何利用邻接矩阵求图中各顶点间的通路条数、如何判断两个图是否同构、它和可达矩阵的关系、它在图的遍历以及关键路径和最短路径中的应用等，通过以上的应用使我们认识到邻接矩阵的意义以及它的方便之处. 毕业论文关键词：图；邻接矩阵；同构；关键路径 Application of the Adjacency Matrix Abstract: Firstly ，this paper introduces the basic concept of graph, and then gives the definition of adjacency matrix in directed graph and undirected graph; Secondly, summarizes the application of adjacency matrix in discrete mathematics and the data structure, and it mainly includes how to use adjacency matrix to solve the channel number of graph vertices , how to judge whether two graphs isomorphism, and the relationship between it and reachability matrix, the application of it in graph traversal and in the critical path and the shortest path and so on, through the application of the above makes us realize the significance of adjacency matrix and the convenience of it. Key words: Graph; Adjacency matrix; Isomorphism; Critical path 目 录 摘 要 1 引言 2 1.预备知识 3 1.1图的基本概念 3 1.1.1无向图 3 1.1.2有向图 3 1.2邻接矩阵的基本概念 3 1.2.1无向图的邻接矩阵 3 1.2.2有向图的邻接矩阵 4 2.邻接矩阵在不同学科领域的应用 4 2.1 邻接矩阵在离散数学中的应用 4 2.1.1用邻接矩阵可求一个图中各顶点间通路的条数[2] 4 2.1.2通过邻接矩阵判断图同构 6 2.1.3由邻接矩阵求可达矩阵 7 2.2邻接矩阵在计算机科学（数据结构）中的应用 8 2.2.1邻接矩阵在图的遍历中的应用 8 2.2.2用邻接矩阵寻找关键路径 11 3.结束语 13 参考文献 14 致谢 15 邻接矩阵的应用引言 平常生活,学科研究中，人们常常用点和点间是否有连线来表示事物之间是否有某种联系，诸如此类所构成的图形即是图论中的图，图论是近些年来发展飞快，应用又广泛的一科既古老又年轻的学科，受到全世界越来越广泛的重视.一个图既能用数学定义来描述，也能用图形来描述，用数学定义描述图精确，但是抽象不好理解，用图形代表图形象且直观，但是如果图中的边和顶点的数目较多时，用这种方法就比较复杂繁琐，因此可以用邻接矩阵表示一个图的各种关系，然后可以用矩阵的知识来研究图的一般性质.因为矩阵的行和列有特定的顺序，因此用矩阵表示图，首先必须将图的顶点、边等进行排序，然后根据上述顺序进行标号，最后用矩阵表示出来. 目前有很多研究邻接矩阵的文章，它们对邻接矩阵的应用都有所讨论，例如在文献[1]-[6]中详细的介绍了邻接矩阵在离散数学中的应用，[7]-[9]中详细介绍了图论以及邻接矩阵的研究背景以及已经研究现状，而在[10]-[13]中详细介绍了邻接矩阵在计算机学科数据结构中的应用.当然这些文献中仍有不足之处，如文献[1]中只是简单的提了邻接矩阵与可达矩阵的关系，并没具体探讨，文献[10]中也只是简单的给出了图的遍历及关键路径的概念，本文在上述文献的基础上，对邻接矩阵的应用作了详细的归纳与总结，具有很大的意义. (责任编辑：qin) |