图论中邻接矩阵的应用

《图论中邻接矩阵的应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第20卷第4期张家口职业技术学院学报Vo.l20No.42007年12月JournalofZhangjiakouVocationalCollegeofTechnologyDecember,2007图论中邻接矩阵的应用刘亚国(河源职业技术学院,广东河源517000)K摘要:本文介绍了邻接矩阵的定义及一个重要定理,揭示了A在图论中的实际意义;并运用邻接矩阵巧妙地解决了锁具装箱和商人过河两个问题。运用邻接矩阵的方法解决问题,简单易懂且容易推广,具有实际应用价值。关键词:图论;邻接矩阵;顶点;边集;路径中图分类号:O151.21文献标识码:A文章编号:1008-81

2、56(2007)04-0078-031.引言首先引入图论中邻接矩阵的定义;然后介绍关于邻接矩阵的一个重要定理。定义:G是一个图,V(G)为G的顶点集,E(G)为G的边集。设G中有n个顶点v1,v2,,vn;A=(aij)n@n为G的邻接矩阵,其中k定理:设A(G)为图G的邻接矩阵,则G中从顶点vi到顶点vj,长度为k的道路的条数为A中的i行j列元素。证:对k用数学归纳法。k=1时,显然结论成立;假设k时定理成立,考虑k+1的情形。l(l)ll+1记A的i行j列元素为aijl2,因为A#A=A,所以l+1lllaij=ai1a1j+ai2a2j+,+aina

3、nj而从v到v长k+1的道路无非是从v经k步到某顶v1[l[n,再从v走一步到v;由归纳假设从v到v长为k的ijilljilk(k)道路共计ail条,而从vl到vj长为1的道路为alj条,所以长为k+1的从vi经k步到vl再一步到vj的道路共有ailalj条,故nk+1(k)从vi经k+1步到vj的路径共有aij=Eailalj条。l=12.邻接矩阵的应用2.1锁具装箱问题(1994年全国大学生数学建模竞赛试题B题)某厂生产一种弹子锁具,每个锁具的钥匙有5个槽,每个槽的高度从{1,2,3,4,5,6}6个数(单位略)中任取一数。由于工艺及其他原因,制造锁具时

4、对5个槽的高度还有两个限制:至少有3个不同的数,相邻两槽的高度之差不能为5,满足以上条件制造出来的所有互不相同的锁具称为一批。销售部门在一批锁具中随意地取每60个装一箱出售。问每一批锁具有多少个,装多少箱?锁具装箱的这个问题是一个排列组合的数学问题,但在这里我们用图论中的邻接矩阵方法来解决这个问题。每把锁都有5个槽,每个槽有6个高度,至少有三个不同高度的槽。且相邻槽高差不为5。我们先求出无相邻高差为5的锁具数量,再减去仅有一个、两个槽高的锁具数目。先计算由1,2,3,4,5,6构成无1,6相邻的情况的数目。为此,构造一个6节点的图:将1,2,3,4,5,6这

5、6个数作为6个节点,当两个数字可以相邻时,这两个节点之间加一条边,每个节点有自己到自己的一条边。我们得到了锁具各槽之间的关系示意图(图1):收稿日期:2007-10-21作者简介:刘亚国(1979-),男,湖北孝感人,河源职业技术学院助教。研究方向:高职基础数学与应用及数学模型。#78#2007年12月刘亚国图论中邻接矩阵的应用第4期111110111111111111该图的邻接矩阵为A=111111111111011111邻接矩阵A的所有元素之和表示两个槽高无1,6相邻的锁具的个数,每个无1,6相邻的5位数与图1中长度为4的一k条链1-1对应,如12345

6、,11111,22335等。A的k次方A中各元素之和就是长度为k的链的个数。事实上,从这个具体问2题可以看出,A中第i行第j列的元素指从i开始经过两条边到达j的链数,即从i开始经过一条边到k,再从k经过一条边达到j,i和j就决定了中间顶点k的数目。于是,利用Matlab就很容易得到1411651651651651401651941941941941654165194194194194165A=1651941941941941651651941941941941651401651651651651414将A中元素求和可得相邻高差不为5的锁具数为6306把。但这

7、6306把锁具中包含了仅有一个、两个槽高的锁具,需要从其中减去。需减去的锁具的个数为256+(C6-1)(2-2)=42625其中,第一个6仅有1个槽高的锁具;C6为1,2,3,4,5,6这6个数中取两个的取法,但扣除1,6这一种取法;(2-2)5是5个槽高每个都有两种选择2,再减去都取相同数字的两种情况。最后得到一批锁具的个数为6306-426=5880,总共装98箱。这样,就用图论的知识成功地解决了一批锁具的数量问题,这个方法比用别的方法简单,且容易推广。2.2商人过河问题三名商人各带一个随从乘船渡河,现有一只小船只能容纳两个人,由他们自己划行,若在河的

8、任一岸的随从人数多于商人,他们就可能抢劫财物。但如何