搜索
数理与信息工程学院课程论文课程名称图论及其应用题目图论中邻接矩阵的应用姓名沈海华朱国淼学号0620012306200129专业信息与计算科学06（1）指导老师卜月华浅谈图论中邻接矩阵的应用[摘要]使用邻接矩阵求解有关实际问题符合数学中数形结合的思想，对于更好地理解问题，思考问题从而求解问题具有现实意义。图论知识的应用是相当广泛的，它是数学的重要分支，使今年来较为活跃的数学分支。这个问题其实也是一个数学游戏问题，是源于生活，高于生活。图论作为组合数学的一分支，与其他数学分支，如矩阵论，概率论，拓扑学数值分析都有着重要的联系。[关键字]邻接矩阵、算法、连通性、最小生成树1、引言首先介绍图论中邻接矩阵的一个重要定理:G是一个图,V(G)为G的顶点集,E(G)为G的边集。设G中有n个顶点，v1,v2,…,vn;A=(aij)n×n为G的邻接距阵,其中njiGEvvGEvvajijiij,...,2,1,)(0)(1定理1:设A(G)为图G的邻接距阵,则G中从顶点vi到顶点vj,长度为k的道路的Ak条数为中的i行j列元素。证:对k用数学归纳法k=1时,显然结论成立;假设k时,定理Al.A=Al+1成立,考虑k+1的情形。记Al的i行j列元素为l≥2,因为所以njlinjlijlilijaaaaaaa...2211)1((1)而从vi,vj到长k+1的道路无非是从vi经k步到某顶点vl(1≤l≤n),再从vl走一步到vj;由归纳假设从vl到vj长为k的道路共计而从vl到vj长为1的道路为aij条,所以长为k+1的vl经过k部到vi再一步到vj的道路共有nlljkillijaaa1)()1(条故从vi经k+1步到vj的路径共有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)。由图我们可以试着画出这个图的邻接矩阵来：111110111111111111111111111111011111A邻接矩阵A的所有元素之和表示两个槽高无1,6相邻的锁具的个数,每个无1,6相邻的5位数与图1中长度为4的一条链1-1对应,如12345,11111,22335等。A的k次方中各元素之和就是长度为k的链的个数。事实上,从这2个具体问题可以看出,A中第i行第j列的元素指从i开始经过两条边到达j的链数,即从i开始经过一条边到k,再从k经过一条边达到j,i和j就决定了中间顶点k的数目。于是,利用Matlab就很容易得到。1411651651651651401651941941941941651651941941941941651651941941941941651651941941941941651401651651651651414A将该矩阵中的元素求和可得相邻高差不为5的锁具数为6306把。把。但这6306把锁具中包含了仅有一个、两个槽高的锁具,需要从其中减去。需减去的锁具的个数为6+(C62-1)(25-2)=426其中,第一个6仅有1个槽高的锁具;C62为1,2,3,4,5,6这6个数中取两个的取法,但扣除1,6这一种取法。最后得到一批锁具的个数为6306-426=5880,总共装98箱。这样,就用图论的知识成功地解决了一批锁具的数量问题,这个方法比用别的方法简单,且容易推广。问题求解反思：使用邻接矩阵求解有关实际问题符合数学中数形结合的思想，对于更好地理解问题，思考问题从而求解问题具有现实意义。图论知识的应用是相当广泛的，它是数学的重要分支，使今年来较为活跃的数学分支。这个问题其实也是一个数学游戏问题，是源于生活，高于生活。图论作为组合数学的一分支，与其他数学分支，如矩阵论，概率论，拓扑学数值分析都有着重要的联系。课本中也列举几种图论的矩阵表示法，如关联矩阵，邻接矩阵。从矩阵的角度分析了图的顶点度的问题等相关知识。对于这样的一个问题我们可以类似的联想到还有一个比较有特色的问题就是商人过河问题：三名商人各带一个随从乘船渡河,现有一只小船只能容纳两个人,由他们自己划行,若在河的任一岸的随从人数多于商人,他们就可能抢劫财物。但如何乘船渡河由商人决定,试给出一个商人安全渡河的方案。同样我们也可以用矩阵的方法加以解决（本题求解将留给读者思考，不作详述）。3、基于邻接矩阵图的连通性判定性原则图的连通性判定准则：对于矩阵如果存在如下公式;11mkkmmijASS那么可以做出如下判断如果矩阵中的元素全部为非零元素，则图G为连通图；否则如果矩阵S中存在t(t1)个零元素，则图G为非连通图。（证明从略）在上述准则中，对于无向图，A为图G的节点邻接矩阵；对于有向图，A为图G对应的无向图的节点邻接矩阵。对于图所示的有向图，对应的无向图的节点，其所定义的邻接矩阵为：0100001011000001100110100011010000101A根据图的连通性判定准则，621181818421425757401818576061571818576160571818405757422141818182161111mkkAS可见该矩阵中的全部元素为非零元素，即图1为连通图。同时，第i行第j列元素表示i节点和j节点间连通的路径数。对于图1所示的有向图，对应于无向图的节点的邻接矩阵为：0100001000000001100010100011010000102A根据图的连通性判定原则：2300003200000023242912002423291200292930170012121761122mkkAS可见该矩阵中的全部元素存在零元素，即图2为非连通图。同时，第i行第j列元素表示i节点和j节点间连通的路径数。定理求解反思：利用图论和集合论的知识，对节点邻接矩阵进行深入分析，提出了有向图和无向图的连通性判定推则及图中任意两节点间不连通的判定准则：对路径及节点邻接矩阵的概念进行了更为严格的数学描述；确定了路径的极限长度。文中提出的图的连通性判定准则具有程序思想简单、逻辑性强、方便快捷的优点，对于图的连通性判定、连通块的划分等都具有指导意义。对于这样的方法判定图的连通性简洁，明了，易于接受。基于课本中未能涉及此类定理求解图的连通性问题，但是我们需要有意识地去研究类似的定理对于我们在平时作业过程中可能需要做出的快速反应。对于我们学习本课程我们需要将自己看成是一支“快速反应部队”。那么对于这类定理的应用是至关重要的。此定理对于连通性的判定和连通块的划分具有指导意义。4、求最小生成树的邻接矩阵法求最小生成树的邻接矩阵法如下：设图G为任意的简单图可以是完全的,也可以是不完全的.图G有个n结点,且其边的集合为{（v1,v2），（v1,v3），…，（vn-1,vn）}。在该算法执行过程中我们使用一个桶存放最小生成树的边一个桶存放最小生成树的结点一个计数器记录桶中边的数目开始时桶桶计数器都是空的。算法的步骤：1)写出图G的邻接矩阵M,对于无向简单图G矩阵M以对角线为轴对称,我们只取其对角线以上部份的三角形各元素.在所有矩阵元素不为0的边中,选最小权边（vi,vj）放入E桶中，该边的两端点vi,vj放入V桶，并记工=1，若有两个（或两个以上）最小权边，其权值相等，任选其一。2)矩阵M中，将（vi,vj）边对应元素改为0，对vi,vj结点所对应的行与列上的矩阵元素做“乘2的模4运算”。3)检查若有不为0的元素，则转第四步。否则算法结束。此时若I=n-1.则E桶中各边构成最小生成树。I《n-1，则没有最小生成树。4)将邻接矩阵M中,值为2的各元素对应边作为候选边.在候选边中找出最小权边（vi,vj），若有两个或两个以上最小权边任取其一。将该边放入E桶，并将其在V桶外的端点vi+1放入V桶。同时：I=I+1。5)将（vi,vj）边对应元素改为0，将新入V桶的结点vi+1对应的M行列中做“乘2的模4运算”。6)转第三步。在关于算法的叙述中应说明两点：第一、算法中规定即乘2的模4运算它的含义是对一个变量乘以2如果乘积等于4，则改该变量的值为0。第二、因为在步骤3检查矩阵，如有不为0的元素，才转4，所以在第4步中邻接矩阵中必有值为2的元素.这是因为当一条边进人E桶，它的两端点进人V桶，与该两端点邻接而尚未进入E桶的各边对应的矩阵元素值原来为1经乘2后，其值必为2。另一方面某一条边成为候选边，则它的矩阵元素值为2，如在下一步它未被选中其值不变，如被选中它的值才会因为乘2的模4运算而变为0.所以只要最小生成树最后未被求出在步骤4，矩阵中必有值为2的元素。该算法求解反思：1、本算法在此虽然为涉及具体题目，但是这样的算法在实际问题的求解中是非常奏效的。通俗易懂，便于检验。这样对于运用计算机程序加以运算提供可能。2、该算法有其简便之处，每次选最小权边2时，仅在部份元素中选取，就是说只矩阵元素为2时对应边才是候选边。5、结束语图论〔GraphTheory〕是数学的一个分支。它以图为研究对象。图论题目的求解多以证明题为主，我们在求解过程中往往是应用已知的定理，分析题目的真正内涵加以解决。但是我们在做题过程中，往往会碰到这样那样的阻力和障碍，这时，我们可以利用已知的定理，做好事先的判断。这于我们之前学习的理念相契合，叫源于课本，高于课本。要将课外的精妙定理转化为现实的应用，毕竟课本的篇幅有限加上考虑到广大同学的接受程度，所以尽管这个知识点很好但是还是得考虑到大众的接受程度。在阅读课本的过程中，我们发现了一个现象。课本的知识点讲解的很透彻详尽，一旦运用到实际就束手无策。所以我们在学习图论的课程过程中，不应拘泥于课本知识，这也是老师第一堂课给了我们诸多参考书目的一个重要内容。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过，作为一门古老而经典的课程来说，学习者需要有不同的眼光去看待这门课程。矩阵的运用对于更好地理解题意，加深对题目的理解具有重要意义。另外有关问题的矩阵求法，前人总结的经验和定理，我们需要有效地运用与传承。矩阵如果运用好了，在一定程度上会带来我们求解问题的便利，实际上也提供了我们解决问题的一条捷径。参考文献：[1]刘亚国，图论邻接矩阵的运用[M].沂州师范学院学报，2008（4）24[2]贾进章、刘进等，基于邻接矩阵图的连通性判定性原则[M]，2003（2）[3]刘育刚，求最小生成树的邻接矩阵法[M]。哈尔滨船舶工程学院学报1989（6）10[4]谢政,李建平.网络算法与复杂性理论[M].北京：国防科技大学出版社,1995.7-8.[5]胡运权.运筹学教程[M].北京:清华大