图的邻接矩阵及其应用数学专业本科生学年论文.doc

学 年 论 文 题 目： 图的邻接矩阵及其应用 学 院： 数学与信息科学学院 专 业： 数学与应用数学 学生姓名： ****** 学 号： ************ 指导教师： ****** 图的邻接矩阵及其应用 摘要:文章介绍了邻接矩阵的定义及一个重要的定理,揭示了Ak 在图论中的实际意义,并运用邻接矩阵的方法解决了锁具装箱和商人过河两个问题[1],使复杂的问题简单易懂,且容易推广,体现出了邻接矩阵在实际生活中的应用价值;另外对邻接矩阵在图的最小生成树和关键路径等算法分析上的应用作了一定的探讨[2]. 关键词:图;有向图;无向图;连通图;邻接矩阵;最小生成树;关键路径 1.图论中邻接矩阵（Adjacency Matrix）的定义 图的邻接矩阵[3],是表示顶点之间相邻关系的矩阵[4]. 设G=(V,E)是一个图，其中V={v1,v2,…,vn}.G的邻接矩阵是一个具有下列性质的n阶方阵: ⑴ 图而言,邻接矩阵一定是对称的,而且对角线一定为零,有向图则不一定如此； ⑵ 向图中,任一顶点i的度为第i列所有元素的和；在有向图中顶点i的出度为第i行所有元素的和,而入度为第i列所有元素的和. 如下图[5]中无向图G 5 和有向图G 6 的邻接矩阵分别为A l和A 2: 2.图论中邻接矩阵的一个重要定理 设G是一个图, V(G)为G 的顶点集, E (G)为G 的边集。G中有n个顶点v1，v2，…，vn ，A=(aij)n×n为G 的邻接距阵,其中 则我们可得到如下定理： 定理1 设A(G) 为图G的邻接距阵,则G中从顶点vi到顶点vj,长度为k的道路的条数为Ak中的i行j列元素. 证 对 k用数学归纳法k =1时,显然结论成立;假设 k时,定理成立,考虑 k +1的情形.记 Al的i行 j列元素为A(1)ij≥2,因为A1#A=A1+1,所以 （1） 而从vi到vj长为 k +1的道路无非是从vi经 k步到某顶点vl(1≤l≤n),再从vl走一步到vj;由归纳假设从vi到vl长为 k的道路共计aijk而从vl到vj长为 1的道路为aij条,所以长为k+1的从vi经过k步到vl再经过一步到vj的道路共有 条,即定理得证. 3.图论中邻接矩阵的应用 3.1锁具装箱问题 某厂生产一种弹子锁具, 每个锁具的钥匙有5个槽,每个槽的高度从{1,2,3,4,5,6}6个数(单位从略) 中任取一数.由于工艺及其他原因,制造锁具时对5个槽的高度还有两个限制:至少有3个不同的数,相邻两槽的高度之差不能为5,满足以上条件制造出来的所有互不相同的锁具称为一批.销售部门在一批锁具中随意地取每60个装一箱出售.问每一批锁具有多少个,装多少箱. 锁具装箱这个问题是一个排列组合的数学问题,但在这里我们用图论中的邻接矩阵方法来解决这个问题.每把锁都有5个槽,每个槽有6个高度,至少有三个不同高度的槽,且相邻槽高差不为5.我们先求出无相邻高差为5的锁具数量,再减去仅有一个两个槽高的锁具数目.先计算由1, 2, 3, 4, 5, 6构成无1, 6相邻的情况的数目.为此,构造一个6节点的图:将1, 2, 3, 4, 5, 6这6 个数作为6个节点,当两个数字可以相邻时,这两个节点之间加一条边,每个节点有自己到自己的一条边.我们得到了锁具各槽之间的关系示意图(图1) 1 2 6 3 5 4 图1 该图的邻接矩阵为: 邻接矩阵A的所有元素之和表示两个槽高无1,6相邻的锁具的个数,每个无1, 6相邻的5 位数与图1中长度为4的一条链一一对应,如12345,11111,22335等.A的k 次方Ak 中各元素之和就是长度为k 的链的个数.事实上,从这个具体问题可以看出,A2中第i行第j列的元素指从i开始经过两条边到达j的链数,即从i开始经过一条边到k,再从k经过一条边达到j, i和j就决定了中间顶点k的数目.于是,利用Matlab就很容易得到 将A4 中元素求和可得相邻高差不为5的锁具数为6306把,但这6306把锁具中包含了仅有一个两个槽高的锁具,需要从其中减去,需减去的锁具的个数为 其中,第一个6仅有1个槽高的锁具; 为1, 2, 3, 4, 5,6这6个数中取两个的取法,但扣除1, 6这一种取法; ( 25-2)是5个槽