邻接矩阵在现实问题中的应用

开篇：润墨网以专业的文秘视角，为您筛选了一篇邻接矩阵在现实问题中的应用范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要：本文首先介绍了邻接矩阵和图论的基础知识，然后具体论述了邻接矩阵在现实问题中的应用.

关键词：邻接矩阵；图；算法

随着现代科学技术的迅速发展，邻接矩阵得到了广泛的应用，它对解决实际问题有着重要的实践意义.本文从邻接矩阵和图论的概念入手，探讨邻接矩阵在现实问题中的应用.

一.邻接矩阵在实际问题中的应用

（一）基础知识

图的概念：一个图是指一个有序三元组，是非空的顶点集，是不与相交的边集，是关联函数，它使的每条边对应于的无序顶点对（不必相异）.若是一条边，而和是使的顶点，则称连接和；顶点和称为的端点.

邻接矩阵的概念：邻接矩阵是表示顶点之间相邻关系的矩阵.设是一个图，为的顶点集，为的边集。设中有个顶点，，，…，；为的邻接距阵，其中

下面介绍图论中邻接矩阵的一个重要定理：

引理 1设为图的邻接距阵，则中从顶点 到顶点 ，长度为的道路的条数为中的行列元素.

（二）邻接矩阵在现实问题中的应用

三名商人各带一个随从乘船渡河，现有一只小船只能容纳两个人，由他们自己划行，若在河的任一岸的随从人数多于商人，他们就可能抢劫财物.但如何乘船渡河由商人决定，试给出一个商人安全渡河的方案.

分析及求解：假设渡河是从南岸到北岸，表示南岸有个商人，个随从，全部的允许状态共有10个：；；；；

；；；；；

以{，…，}为顶点集，考虑到奇数次过河及偶数次的不同，我们建立两个邻接矩阵；.

其中；；

.

其中表示从南岸到北岸过河的图的邻接矩阵，表示从北岸到南岸过河的图的邻接矩阵.

由引理1，我们应考虑最小的中1行10列的元素不为0，此时即为最少的过河次数，而矩阵中1行10列的元素是最佳的路径数目.经过计算时，的1行10列元素为2，所以需过河11次，有两条最佳路径.

由下图可得这样的过河策略，与应用邻接矩阵所求的结果吻合.

三.总结

使用邻接矩阵求解有关实际问题符合数学中数形结合的思想，具有现实意义.邻接矩阵在图论中的应用是它的多种应用之一，我们可以利用它分析、处理、优化有关实际问题，同时邻接矩阵在生活中也有重要用途，可以为我们解决生活及工作中很多现实问题提供思路和途径.

参考文献：

[1]刘亚国.图论邻接矩阵的运用[J].沂州师范学院学报，2008，24（4）：1-5.

[2]李朝鹏.基于图形处理器的邻接矩阵算法[J].科技信息，2010，12（10）：14-14.

[3]贾进章等.基于邻接矩阵图的连通性判定性原则[J].科技信息，2003，23，（2）：134-136.

[4]卢建立，杨明波.图论中矩阵的可实现性[J].数学的实践与认识，2005，35（5）：182-186.

[5]谢政，李建平.网络算法与复杂性理论[M].北京：国防科技大学出版社，1995：7-8.

作者简介：刘亚珍（1991.7-），女，河南新密人，本科，信息与计算科学专业。