论文编号:YYSX233 论文字数:4991,页数:09
图的邻接矩阵及应用 [摘 要] 图在现实生活中的应用无处不在,诸如运筹学,信息论,控制论,博弈论,计算机科学等都是以图来解决实际问题和理论问题的。特别是计算机的诞生使得图论本身也得到了很大的发展。本文从图的基本问题路径问题开始,用探究的方式从邻接矩阵的角度总结出了一般性结论,并用归纳法做了严格的证明。在此基础上,给出了图的连通性等价条件,给出了具体的判定图的连通性的方法,并给出了具体的例子,说明了用邻接矩阵的方法研究图的路径问题和连通性问题可靠有效。[关键词] 邻接矩阵 可达矩阵 连通性
在现实世界中有许多现象、许多事物、许多状态是用某种图形来描述的。因此在很早人们就对图有广泛的研究,使得图的理论十分丰富。随着计算机科学的发展,图论本身更得到了充分的发展。在图的问题中,图的连通性和两点间路径是一个基本的且在实际中经常遇到的问题,对这个问题的研究有多种方法,本文从图的邻接矩阵的角度对这个问题进行了探究。