摘要：本文介绍了邻接矩阵的定义并从图的连通性、最小生成树和一些实际问题方面讨论了邻接矩阵在图论中的应用。 

毕业论文关键词：邻接矩阵，图的连通性，数形结合，数学模型，最小生成树72562

Abstract：In this paper, we introduced the definition of adjacency matrix and discussed its applications in graph theory about connexity of graph, minimum spanning tree and some practical problems。

Keywords：adjacency matrix , connexity of graph, number shape union, mathematical model , minimum spanning tree

目录

1 引言 4

2 预备知识 4

3 邻接矩阵的一些应用 5

3。1 邻接矩阵在图的连通性问题中的应用 5

3。2 邻接矩阵在最小生成树问题中的应用 6

3。3 公交线路选择问题 7

3。4 商人过河问题 8

结论 10

参考文献 11

1 引言

     邻接矩阵的应用十分广泛，在图论及其他方面有着重要应用。 图论是数学的重要分支与其他数学分支，如矩阵论，概率论，拓扑学数值分析都有着重要的联系。 本文在已有文献的基础上，介绍了邻接矩阵的定义及邻接矩阵的几个重要的性质,揭示了 在图论中的实际意义。并运用邻接矩阵求解了相关问题。 

    本文将从最小生成树，图的连通性判别等方面来讨论邻接矩阵在图论中的应用，使复杂的问题简单易懂,且容易推广,达到了事半功倍的效果,并运用邻接矩阵的方法巧妙的解决了公交线路选择问题和商人过河两个问题,体现出了邻接矩阵在实际生活中的应用价值。使用邻接矩阵求解有关实际问题符合数学中数形结合的思想，对于更好地理解问题，思考问题从而求解问题具有现实意义。 

2 预备知识

    性质2。1[1]  邻接矩阵是表示顶点之间相邻关系的矩阵，那么，设 是一个无向图， 为 的顶点集, 为 的边集。 设 中有 个顶点 …, ;  为 的邻接矩阵，其中

无向图的邻接矩阵是一个元素为 和 的对称矩阵，对角线上的元素都为 。 文献综述

性质2。2[2]  设 为图 的邻接距阵，则 中从顶点 到顶点 ,长度为 的道路的条数为 中的 元 。 

    性质2。3[2]  若 是一个有向图，则邻接矩阵 的各行元素之和为相应顶点的出度，各列元素之和为入度。 

    性质2。4[4]  邻接矩阵的图的连通性判定准则：对于矩阵如果存在如下公式：设

则 中的 元 为顶点 到顶点 长度为小于或等于 的道路的条数。 若 ，说明从顶点 到顶点 无通路。 如果矩阵 中的元素全部为非零元素，则图 为连通图。 

    在上述准则中，对于无向图， 为图 的节点邻接矩阵；对于有向图， 为图 对应的无向图的节点邻接矩阵。 

3 邻接矩阵的一些应用

3。 1 邻接矩阵在图的连通性问题中的应用

    例1 运用邻接矩阵的图的连通性判定准则，判定下面的图1和图2是否为连通图。 

    解 对图1所示的有向图所对应的无向图的节点，根据性质2。1得其所定义的邻接矩阵为：