摘要：图论在人们日常生活中已经得到了广泛应用，本文详细地探究了图——由顶点和边组合而成的离散数学结构，具有的逻辑及结构性质，将现实生活中的实际问题抽象为数学图论问题，中间的桥梁便是矩阵，而邻接矩阵是探究图的一个不可或缺的课题，因此本文重点探究了图的邻接矩阵的概念以及性质，介绍了多种求邻接矩阵的特征值的方法，其中包括定义法、性质计算、Jacobi方法等，并运用各种方法对实例进行计算，可编程的方法也进行了编程，最后，比较各个方法的异同，发现适用范围最广的是性质计算法，它可以应用于有向图和无向图的邻接矩阵的特征值计算，而且计算速度比较快；性能其次的是Jacobi方法，只适用于无向图的邻接矩阵的特征值的计算；最后是定义法，该方法更多运用在寻找图的最优结构这类问题中。
关键词：图；邻接矩阵；特征值
Abstract: Graph theory has been widely used in people’s daily lives. This article explores graphs in detail—discrete mathematical structures composed of vertices and edges. They have logical and structural properties, abstracting practical problems in real life into mathematics In the graph theory problem, the bridge in the middle is a matrix, and the adjacency matrix is an indispensable topic for exploring graphs. Therefore, this article focuses on the concept and nature of the adjacency matrix of graphs, and introduces a variety of methods for finding the eigenvalues of adjacency matrices. Methods, including definition method, property calculation, Jacobi method, etc., and use various methods to calculate examples, programmable methods are also programmed, and finally, compare the similarities and differences of various methods, and find that the most widely used is property calculation Method, it can be applied to the calculation of the eigenvalues of the adjacency matrix of directed graphs and undirected graphs, and the calculation speed is relatively fast; the performance is followed by the Jacobi method, which is only applicable to the calculation of the eigenvalues of the adjacency matrix of undirected graphs; It is a definition method, which is more used in finding the optimal structure of graphs.
Keywords:Graph; Adjacency Matrix; Eigenvalue
1 前言
1.1 课题背景及意义
近年来，数学对人们的生活以及整个国家、整个社会都起到了非常重要的作用，数学来源于生活，与此同时，生活也离不开数学，其中，离散数学的实际应用也推动了社会的发展，离散数学中一个非常重要的版块便是图论。图论是建立在离散化的基础上的，最初，数学家Euler将著名的游客能否不重不漏地走过每条桥最终回到起点这个实际问题，高度总结并抽象成了一个全新的、有创造力的离散数学问题——之后七桥问题的解决，也标志着图论这门学科的诞生，图论是将实际路径问题转化成顶点与边的问题，并通过探讨分析两者之间的规律来确定问题是否有解、是否有最优解以及最优解是什么。
在现实生活中，人们通常会遇到几个地点之间游玩路线最优，或者几个地点之间建造公路成本最低这类的问题，如果只靠实际的不断遍历试错去寻找最优方案，不仅耗费的时间长、人力成本高，而且很有可能面临一个根本米有最优解的困境——这样一来，之前做的工作都算打水漂了，因此，图论的引进是非常有必要的，现在来说，已经有很多问题可以直接利用图论的结论了，比如：
一笔画问题通过欧拉图的性质来解决：当图G为无向图时，如果G连通且每个顶点的度d(v)为偶数，那么图G被称为欧拉图；如果恰有2个顶点的度为奇数，那么存在一条经过所有边、所有顶点的欧拉路径。图G为有向图时，如果图G弱连通，每个顶点的入度等于出度，即d+(v)=d-(v)，那么图G被称为欧拉图；如果图G连通，且恰有2个顶点出度与入度不相等，其中一个出度比入度多1，另一个入度比出度多1，那么存在一条经过所有边、所有顶点的欧拉路径。
经过所有顶点的问题可以用哈密顿图的性质来解决：如果图G上有一条过所有顶点的回路（不一定经过每条边），那么图G就是哈密顿图；如果图G的每一对顶点度数之和不小于n，且n≥3，则图G为哈密顿图。如果具有n个顶点的图G的每一对顶点的度数之和都不小于n-1，那么图G中有一条哈密顿通路。
而且哈密顿问题已经被证明为NP完全问题，因此每增加一个顶点，该问题的算法时间复杂度会呈指数增长，因此靠人力去一一列举通路、找到一条哈密顿通路的方法是行不通的。
综上所述，图论在人们的生活中能够发挥非常重要的作用，而探究图这一离散的数学结构，就需要利用矩阵来表示图中顶点与边之间的关系，其中最基础、最重要的便是图的邻接矩阵，它表示了图中顶点与顶点之间是否有边连接的关系，与拉普拉斯矩
4 结论
上面详细列举了图的邻接矩阵特征值的3种不同的计算方法，分别为定义法、性质计算法以及Jacobi方法，并对后两者进行了编程实现。
在实际计算的过程中，发现了这3种方法的优点和劣势，具体的内容在上文中已经列表介绍，下面将进行总结分析：
定义法更加适用于图未知、特征向量已知的情况。当人们已知某一图的一些特征，但并不知道图的完整结构时，可以利用特征值、特征向量的定义Aα=λα 来求得其邻接矩阵
，当邻接矩阵被确定时，图也就相应地被确定下来了，这也是图的特征值、特征矩阵的应用之一。
性质计算方法是最广泛的方法，无论是对于有向图、无向图还是有环图、无环图来说，只要图是已知的，那么利用性质计算法便一定可以求出该图的邻接矩阵的特征值，只不过当图的结构非常复杂时，其计算难度会随之增加而已；并且该方法是机器计算矩阵特征值的普遍做法，不仅对于图的邻接矩阵，对于任何矩阵它都能用来计算其特征值。
Jacobi方法是只针对无向无环图来设计的，而且对于程序的保护程度也比较高，在计算之前会先验证输入的矩阵是否合法（即矩阵是否为方阵以及矩阵是否对称），而且此方法会将特征向量也一并计算出来，非常方便，移植性很高。
社会的不断发展给图论的发展提供了源源不断的动力，与之相对应的是，图论的不断进步也反过来不断推动着人类社会的发展，社会为离散数学培养专业化的人才，人才攻克各种难题并将其应用到社会生产中，这便形成了一个良好的循环。目前而言，图论对人们生活的影响越来越大，将实际生活中的问题抽象成数学问题的思维也愈发重要，因此我们仍需善于观察、善于总结，不断为社会做出自己的贡献。
参考文献（略）
