.浅谈图论中邻接矩阵的应用摘 要 使用邻接矩阵求解有关实际问题符合数学中数形结合的思想，对于更好地理解问题，思考问题从而求解问题具有现实意义。图论知识的应用是相当广泛的，它是数学的重要分支，使今年来较为活跃的数学分支。这个问题其实也是一个数学游戏问题，是源于生活，高于生活。图论作为组合数学的一分支，与其他数学分支，如矩阵论，概率论，拓扑学数值分析都有着重要的联系。 关键字 邻接矩阵、算法、连通性、最小生成树1、引言首先介绍图论中邻接矩阵的一个重要定理:G是一个图,V (G)为 G的顶点集, E(G)为 G的边集。设G中有 n个顶点，v1,v2,vn;A=(aij)nn为 G的邻接距阵, 其中 定理 1:设 A (G)为图 G的邻接距阵,则 G中从顶点 vi 到顶点 vj,长度为 k的道路的Ak条数为中的 i行 j列元素。证:对 k用数学归纳法k =1时,显然结论成立;假设 k时,定理Al.A= Al+1成立,考虑 k +1的情形。记 Al的 i行 j列元素为l2,因为所以 (1)
