图的邻接矩阵及应用

图的邻接矩阵及应用

[摘 要]  图在现实生活中的应用无处不在，诸如运筹学，信息论，控制论，博弈论，计算机科学等都是以图来解决实际问题和理论问题的。特别是计算机的诞生使得图论本身也得到了很大的发展。本文从图的基本问题路径问题开始，用探究的方式从邻接矩阵的角度总结出了一般性结论，并用归纳法做了严格的证明。在此基础上，给出了图的连通性等价条件，给出了具体的判定图的连通性的方法，并给出了具体的例子，说明了用邻接矩阵的方法研究图的路径问题和连通性问题可靠有效。

[关键词] 邻接矩阵  可达矩阵  连通性

在现实世界中有许多现象、许多事物、许多状态是用某种图形来描述的。因此在很早人们就对图有广泛的研究，使得图的理论十分丰富。随着计算机科学的发展，图论本身更得到了充分的发展。在图的问题中，图的连通性和两点间路径是一个基本的且在实际中经常遇到的问题，对这个问题的研究有多种方法，本文从图的邻接矩阵的角度对这个问题进行了探究。

一.图的概念及性质