第20卷第4期 2007年12月
张家口职业技术学院学报
JournalofZhangjiakouVocationalCollegeofTechnology
Vo.l20 No.4 December,2007
图论中邻接矩阵的应用
刘亚国
(河源职业技术学院,广东河源517000)
摘要:本文介绍了邻接矩阵的定义及一个重要定理,揭示了AK在图论中的实际意义;并运用邻接矩阵巧妙地解决了锁具装箱和商人过河两个问题。运用邻接矩阵的方法解决问题,简单易懂且容易推广,具有实际应用价值。
关键词:图论;邻接矩阵;顶点;边集;路径
中图分类号:O151.21 文献标识码:A 文章编号:1008-8156(2007)04-0078-03
1.引言
首先引入图论中邻接矩阵的定义;然后介绍关于邻接矩阵的一个重要定理。
定义:G是一个图,V(G)为G的顶点集,E(G)为G的边集。设G中有n个顶点v1,v2,,vn;A=(aij)n@n为G的邻接矩阵,其中
定理:设A(G)为图G的邻接矩阵,则G中从顶点vi到顶点vj,长度为k的道路的条数为Ak中的i行j列元素。证:对k用数学归纳法。
k=1时,显然结论成立;假设k时定理成立,考虑k+1的情形。记Al的i行j列元素为a(ijl)l\2,因为Al#A=Al+1,所以
1
al+=ali1a1j+ali2a2j+,+alinanjij
而从vi到vj长k+1的道路无非是从vi经k步到某顶vl1[
n
l[n,再从vl走一步到vj;由归纳假设从vi到vl长为k的
道路共计akil条,而从vl到vj长为1的道路为alj条,所以长为k+1的从vi经k步到vl再一步到vj的道路共有a(ilk)alj条,故从vi经k+1步到vj的路径共有a
2.邻接矩阵的应用
2.1锁具装箱问题(1994年全国大学生数学建模竞赛试题B题)
某厂生产一种弹子锁具,每个锁具的钥匙有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):
k+1
ij
=
Ea
l=1
(k)il
alj条。
收稿日期:2007-10-21
作者简介:刘亚国(1979-),男,湖北孝感人,河源职业技术学院助教。研究方向:高职基础数学与应用及数学模型。#78#
2008 年 4 月 JOURNAL OF X I ZHOU TEACHERS UN I ERSITY N V 图论中邻接矩阵的应用刘亚国 (河源职业技术学院 ,广东 河源 517000) 摘 : 文章介绍了邻接...
4 . December, 2007 图论中邻接矩阵的应用刘亚国 (河源职业技术学院 ,广东河源 517000 ) 摘要 : 本文介绍了邻接矩阵的定义及一个重要定理 ,揭示了 A K 在...
浅谈图论中邻接矩阵的应用 [摘要] 使用邻接矩阵求解有关实际问题符合数学中数形结合的思想,对于更好地理解问 题,思考问题从而求解问题具有现实意义。图论知识的应用...
图论中邻接矩阵的应用_理学_高等教育_教育专区 暂无评价0人阅读0次下载举报文档 图论中邻接矩阵的应用_理学_高等教育_教育专区。aaa...
2 图论中邻接矩阵的应用_IT/计算机_专业资料。维普资讯 http://www.cqvip.com 第2 O卷第 4期 200 7年l 2月 张家 口职 业技 术学 院学报 ...
图论中邻接矩阵的应用_专业资料。文章介绍了邻接矩阵的定义及一个重要的定理,揭示了A^k在图论中的实际意义,并运用邻接矩阵的方法巧妙的解决了锁具装箱和商人过河...
本科学生毕业论文(设计)开题报告题目 邻接矩阵在图论中的应用 姓专学学 名业号院 XX 数学与应用数学 XXX 数学科学 XXX 指导教师 淮北师范大学教务处制 一、本...
矩阵在图论中的应用一, 无向图的邻接矩阵 , v p } ,边集为 E (G ) = {e1 , e2 , , eq } ,则图 定义 1:设图 G 顶点集合为 V (G ) = {...
图论中矩阵的可实现性_理学_高等教育_教育专区。数学 模型 建立 比赛 论文 ... 图论中邻接矩阵的应用 7页 1下载券 图论中邻接矩阵的应用 5页 1下载券...
图论的应用姓名:张斌斌 学号:S120932 专业:应用数学 摘要:图论起源于 18 世纪...中,网 络被抽象为一个图论中定义的有向或无向图, 并利用图的节点邻接矩阵...
热门文档