图的邻接矩阵及其应用开题报告

全文总字数：2888字

1. 研究目的与意义

图论知识的应用是相当广泛的，它是数学的重要分支，是近年来较为活跃的数学分支。

这个问题其实也是一个数学游戏问题，是源于生活，高于生活。

图论作为组合数学的一分支，与其他数学分支，如矩阵论，概率论，拓扑学数值分析都有着重要的联系。

2. 国内外研究现状分析

岳秋菊与朱正平讨论了基于图的邻接矩阵求其距离矩阵的算法与实现。

如果采用手工求解图中任意两顶点间的距离，计算量大且繁琐。

本文给出了根据图的邻接矩阵的各次幂求解图的距离矩阵的算法，从而实现了完全应用程序求解，在很大程度上解决了上述问题所遇到的难点，尤其是图中顶点较多时使该问题变得非常容易求解。

3. 研究的基本内容与计划

本课题研究的关键问题是：（1）揭示了矩阵在图论中的实际意义,并运用邻接矩阵的方法解决了锁具装箱和商人过河两个问题；（2）另外对邻接矩阵在图的最小生成树和关键路径等算法分析上的应用作了一定的探讨。

解决问题的思路是：首先介绍图论中邻接矩阵的相关概念，归纳总结邻接矩阵的相关性质定理；然后给出具体实例，刻画数学模型；最后根据邻接矩阵的相关性质定理分析问题，解决问题。

4. 研究创新点

1、详细阐述如何运用邻接矩阵的方法解决锁具装箱和商人过河两个问题，另外对邻接矩在图的最小生成树和关键路径等算法分析上的应用作了一定的探讨。

2、原理、方法和论证分析相结合。