浅谈图论中邻接矩阵的应用.doc

《浅谈图论中邻接矩阵的应用.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、浅谈图论中邻接矩阵的应用[摘要]使用邻接矩阵求解有关实际问题符合数学中数形结合的思想，对于更好地理解问题，思考问题从而求解问题具有现实意义。图论知识的应用是相当广泛的，它是数学的重要分支，使今年来较为活跃的数学分支。这个问题其实也是一个数学游戏问题，是源于生活，高于生活。图论作为组合数学的一分支，与其他数学分支，如矩阵论，概率论，拓扑学数值分析都有着重要的联系。[关键字]邻接矩阵、算法、连通性、最小生成树1、引言首先介绍图论中邻接矩阵的一个重要定理:G是一个图,V(G)为G的顶点集,E(G)为G的边集。设G中有n个顶点，v1,v2,…,vn;A=(

2、aij)n×n为G的邻接距阵,其中定理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,因为所以(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的道路共有条故从vi经k+1步到vj的路径共有1

3、、邻接矩阵现实问题中的运用锁具装箱问题某厂生产一种弹子锁具,每个锁具的钥匙有5个槽,每个槽的高度从{1,2,3,4,5,6}6个数(单位略)中任取一数由于工艺及其他原因,制造锁具时对5个槽的高度还有两个限制:至少有3个不同的数,相邻两槽的高度之差不能为5,满足以上条件制造出来的所有互不相同的锁具称为一批。销售部门在一批锁具中随意地取每60个装一箱出售。问每一批具有多少个,装多少箱。分析：锁具装箱这个问题是一个排列组合的数学问题,但在这里我们用图论中的邻接矩阵方法来解决这个问题。每把锁都有5个槽,每个槽有6个高度,至少有三个不同高度的槽。且相邻槽高差

4、不为。我们先求出无相邻高5差为5的锁具数量,再减去仅有一个、两个槽高的锁具数目。先计算由1,2,3,4,5,6构成无1,6相邻的情况的数目。为此,构造一个6节点的图:将1,2,3,4,5,6这6个数作为6个节点,当两个数字可以相邻时,这两个节点之间加一条边,每个节点有自己到自己的一条边。我们得到了锁具各槽之间的关系示意图(见图1)。由图我们可以试着画出这个图的邻接矩阵来：邻接矩阵A的所有元素之和表示两个槽高无1,6相邻的锁具的个数,每个无1,6相邻的5位数与图1中长度为4的一条链1-1对应,如12345,11111,22335等。A的k次方中各元素

5、之和就是长度为k的链的个数。事实上,从这2个具体问题可以看出,A中第i行第j列的元素指从i开始经过两条边到达j的链数,即从i开始经过一条边到k,再从k经过一条边达到j,i和j就决定了中间顶点k的数目。于是,利用Matlab就很容易得到。将该矩阵中的元素求和可得相邻高差不为5的锁具数为6306把。把。但这6306把锁具中包含了仅有一个、两个槽高的锁具,需要从其中减去。需减去的锁具的个数为6+(C62-1)(25-2)=426其中,第一个6仅有1个槽高的锁具;C62为1,2,3,4,5,6这6个数中取两个的取法,但扣除1,6这一种取法。最后得到一批锁具

6、的个数为6306-426=5880,总共装98箱。这样,就用图论的知识成功地解决了一批锁具的数量问题,这个方法比用别的方法简单,且容易推广。问题求解反思：使用邻接矩阵求解有关实际问题符合数学中数形结合的思想，对于更好地理解问题，思考问题从而求解问题具有现实意义。图论知识的应用是相当广泛的，它是数学的重要分支，使今年来较为活跃的数学分支。这个问题其实也是一个数学游戏问题，是源于生活，高于生活。图论作为组合数学的一分支，与其他数学分支，如矩阵论，概率论，拓扑学数值分析都有着重要的联系。课本中也列举几种图论的矩阵表示法，如关联矩阵，邻接矩阵。从矩阵的角度

7、分析了图的顶点度的问题等相关知识。对于这样的一个问题我们可以类似的联想到还有一个比较有特色的问题就是商人过河问题：三名商人各带一个随从乘船渡河,现有一只小船只能容纳两个人,由他们自己划行,若在河的任一岸的随从人数多于商人,他们就可能抢劫财物。但如何乘船渡河由商人决定,试给出一个商人安全渡河的方案。同样我们也可以用矩阵的方法加以解决（本题求解将留给读者思考，不作详述）。3、基于邻接矩阵图的连通性判定性原则图的连通性判定准则：对于矩阵如果存在如下公式;那么可以做出如下判断如果矩阵中的元素全部为非零元素，则图G为连通图；否则如果矩阵S中存在t(t1)个零

8、元素，则图G为非连通图。（证明从略）在上述准则中，对于无向图，A为图G的节点邻接矩阵；对于有向图，A为图G对应的无向图的节