论文总字数：4377字

摘 要

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

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得其所定义的邻接矩阵为：

，

根据性质2.4，得：

.

矩阵中的元素全为非零元素，易得图1为连通图. 且第行第列的元素的大小表示的是节点到节点间连通的路径数.

同理，对图2所示的有向图，对应的无向图的节点，其所定义的邻接矩阵为：

，

根据性质2. 4,得：

，

可见矩阵中的元素中存在零元素，即图2为非连通图. 同时，第行第列元素表示节点和节点间连通的路径数.

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

设图为任意的简单图可以是完全的,也可以是不完全的. 图有个结点,且其边的集合为. 求出图的最小生成树的算法有两种，分别为克鲁斯卡尔算法和普利姆算法. 使用克鲁斯卡尔算法求出最小生成树的过程中，图的存贮结构采用边集数组，且权值相等的边在数组中排列的次序可以是任意的. 该方法对于边相对比较多的并不是很实用. 而若使用普利姆算法计算最小生成树，图的存贮结构采用邻接矩阵，对于边数较多的图也能较易算出.

现在具体介绍一下普利姆算法. 在该算法执行过程中我们使用桶存放最小生成树的边,桶存放最小生成树的结点,一个计数器记录桶中边的数目,一个计数器记录桶的结点的数目. 开始时，桶桶计数器都是空的.

算法的步骤：

1）写出图的邻接矩阵,对于无向图的矩阵以对角线为轴对称,我们只取其对角线以上部份的三角形各元素. 在所有矩阵元素不为的边中,选最小权边放入桶中，该边的两端点放入桶，并记， 若有两个（或两个以上）最小权边，其权值相等，任选其一.

2）矩阵中，将边对应元素改为，对结点所对应的行与列上的矩阵元素做“乘2的模4运算”.

3）检查若有不为0的元素，则转第四步. 否则算法结束. 此时若. 则桶中各边构成最小生成树. ，则没有最小生成树.

4）将邻接矩阵中,值为的各元素对应边作为候选边. 在候选边中找出最小权边，若有两个或两个以上最小权边任取其一. 将该边放入桶，并将其在桶外的端点放入桶. 同时：.

5）将边对应元素改为0，将新入桶的结点对应的行列的矩阵元素中做“乘2的模4运算”.

6）转第三步.

在关于算法的叙述中应说明两点：

1）算法中规定，即“乘2的模4运算”它的含义是对一个变量乘以2，如果乘

积等于4，则改该变量的值为0.

2）因为在步骤3检查矩阵，如有不为0的元素，才转4，所以在第4步中邻接矩阵中必有值为2的元素. 这是因为当一条边进人E桶，它的两端点进人桶，与该两端点邻接而尚未进入桶的各边对应的矩阵元素值原来为1经乘2后，其值必为2. 另一方面，某一条边成为候选边，则它的矩阵元素值为2，如在下一步它未被选中其值不变，如被选中它的值才会因为乘2的模4运算而变为0. 所以，只要最小生成树最后未被求出在步骤4，矩阵中必有值为2的元素.

3. 3 公交线路选择问题

例2 简化的公交网见右图一，图中有两条公交线路，实线表示第一条线路，依次经过站点1,3,4,5，虚线表示第二条线路，依次经过站点2,3,5. 以简化城市公交网的信息为依据，在任意两个站点中，求出换乘次数最少的出行路线.

解 依据性质2.1，建立图一的邻接矩阵:

剩余内容已隐藏，请支付后下载全文，论文总字数：4377字