图论中邻接矩阵的应用

第 24卷 　第 2期 2008年 4月 　 　　　 　 　 　 忻 州 师 范 学 院 学 报 JOURNAL OF X INZHOU TEACHERS UN IVERSITY 　　　　　　 Vol. 24　No. 2　 Ap r. 2008　 图论中邻接矩阵的应用 刘亚国 (河源职业技术学院 ,广东 河源 517000) 摘 　要 :文章介绍了邻接矩阵的定义及一个重要的定理 ,揭示了 Ak 在图论中的实际意义 , 并运用邻接矩阵的方法巧妙的解决了锁具装箱和商人过河两个问题 ,使复杂的问题简单易懂 , 且容易推广 ,达到了事半功倍的效果 ,体现出了邻接矩阵在实际生活中的应用价值。 关键词 :图 ;邻接矩阵 ;顶点 ;边 ; 路径 中图分类号 : O151. 21　文献标识码 : A 　文章编号 : 1671 - 1491 ( 2008) 02 - 0018 - 02 1　引言 首先介绍图论中邻接矩阵的一个重要定理 : G是一个图 , V (G)为 G的顶点集 , E (G)为 G的边集。设 G中有 n个顶点 v1 , v2 , ⋯, vn; A = ( aij ) n ×n为 G的邻接距阵 , 其中 aij = 1 vi vj ∈ E (G) 0 vi vj | E (G) 　i, j = 1, 2, ⋯, n 　　定理 1:设 A (G)为图 G的邻接距阵 ,则 G中从顶点 vi到 顶点 vj,长度为 k的道路的条数为 A k 中的 i行 j列元素。 证 :对 k用 数学 数学高考答题卡模板高考数学答题卡模板三年级数学混合运算测试卷数学作业设计案例新人教版八年级上数学教学计划 归纳法 k = 1时 ,显然结论成立 ;假设 k时 ,定理成立 ,考虑 k + 1 的情形 . 记 A l的 i行 j列元素为 a ( l)ij l≥2,因为 A l·A =A l + 1 ,所以 a ( l+1) ij = a l i1 a1 j + a l i2 a2 j + ⋯ + alin an j (1) 　　而从 vi到 vj长 k + 1的道路无非是从 vi经 k步到某顶点 vl (1≤l≤n) ,再从 vl走一步到 vj;由归纳假设从 vi到 vl长为 k 的道路共计 akil条 ,而从 vl到 vj长为 1的道路为 aij条 ,所以长 为 k + 1的从 vi经 k步到 vl再一步到 vj的道路共有 a ( k)ij alj条 , 故从 vi经 k + 1步到 vj的路径共有 a ( k +1)ij = ∑ n l = 1 a ( k) il alj条。 2　邻接矩阵的应用 2. 1　锁具装箱问题 某厂生产一种弹子锁具 ,每个锁具的钥匙有 5个槽 ,每 个槽的高度从 { 1, 2, 3, 4, 5, 6} 6个数 (单位略 )中任取一数。 由于工艺及其他原因 ,制造锁具时对 5个槽的高度还有两个 限制 :至少有 3个不同的数 ,相邻两槽的高度之差不能为 5, 满足以上条件制造出来的所有互不相同的锁具称为一批。 销售部门在一批锁具中随意地取每 60个装一箱出售。问每 一批锁具有多少个 ,装多少箱。 ( 1994年全国大学生数学建 模竞赛试题 B 题 ) 锁具装箱这个问题是一个排列组合的数学问题 ,但在这 里我们用图论中的邻接矩阵方法来解决这个问题。 每把锁都有 5个槽 ,每个槽有 6个高度 ,至少有三个不 同高度的槽。且相邻槽高差不为 5。我们先求出无相邻高 差为 5的锁具数量 ,再减去仅有一个、两个槽高的锁具数目。 先计算由 1, 2, 3, 4, 5, 6构成无 1, 6相邻的情况的数目。为 此 ,构造一个 6节点的图 :将 1, 2, 3, 4, 5, 6这 6个数作为 6 个节点 ,当两个数字可以相邻时 ,这两个节点之间加一条边 , 每个节点有自己到自己的一条边。我们得到了锁具各槽之 间的关系示意图 (见图 1)。 图 1　锁具各槽间的关系示意图 该图的邻接矩阵为 收稿日期 : 2007 - 10 - 24 作者简介 :刘亚国 (1979 - ) ,男 ,湖北孝感人 ,河源职业技术学院助教 ,从事基础数学与应用及数学模型研究。 A = 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 　　邻接矩阵 A的所有元素之和 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示两个槽高无 1, 6相邻 的锁具的个数 ,每个无 1, 6相邻的 5位数与图 1中长度为 4 的一条链 1 - 1对应 ,如 12345, 11111, 22335等。A的 k次方 Ak 中各元素之和就是长度为 k的链的个数。事实上 ,从这 个具体问题可以看出 , A2 中第 i行第 j列的元素指从 i开始 经过两条边到达 j的链数 ,即从 i开始经过一条边到 k,再从 k经过一条边达到 j, i和 j就决定了中间顶点 k的数目。于 是 ,利用 M atlab就很容易得到 A4 = 141 165 165 165 165 140 165 194 194 194 194 165 165 194 194 194 194 165 165 194 194 194 194 165 165 194 194 194 194 165 140 165 165 165 165 141 　　将 A4 中元素求和可得相邻高差不为 5的锁具数为 6306 把。但这 6306把锁具中包含了仅有一个、两个槽高的锁具 , 需要从其中减去。需减去的锁具的个数为 6 + (C26 - 1) (25 - 2) = 426 　　其中 ,第一个 6仅有 1个槽高的锁具 ; C26 为 1, 2, 3, 4, 5, 6这 6个数中取两个的取法 ,但扣除 1, 6这一种取法 ; ( 25 - 2)是 5个槽高每个都有两种选择 25 ,再减去都取相同数字 的两种情况。 最后得到一批锁具的个数为 6306 - 426 = 5880,总共装 98箱。这样 ,就用图论的知识成功地解决了一批锁具的数 量问题 ,这个方法比用别的方法简单 ,且容易推广。 2. 2　商人过河问题 三名商人各带一个随从乘船渡河 ,现有一只小船只能容 纳两个人 ,由他们自己划行 ,若在河的任一岸的随从人数多 于商人 ,他们就可能抢劫财物。但如何乘船渡河由商人决 定 ,试给出一个商人安全渡河的 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 。 下面分析及求解 假设渡河是从南岸到北岸 , (m , n)表示南岸有 m 个商 人 , n个随从 ,全部的允许状态共有 10个 v1 = (3, 3) ; v2 = (3, 2) ; v3 = (3, 1) ; v4 = (3, 0) v5 = (2, 2) ; v6 = (1, 1) ; v7 = (0, 3) ; v8 = (0, 2) v9 = (0, 1) ; v10 = (0, 0) 　　以 V = { v1 , v2 , ⋯, v10 }为顶点集 ,考虑到奇数次渡河及 偶数次渡河的不同 ,我们建立两个邻接距阵 A = A1 A2 0 A3 　B = AT 其中 A1 = 0 1 1 0 1 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 ; A2 = 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 A3 = 0 0 0 1 1 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 　　其中 A表示从南岸到北岸渡河的图的邻接距阵 , B = AT 表示从北岸到南岸渡河的图的邻接距阵。 由定理 1,我们应考虑最小的 k, s· t (AB ) kA 中 1行 10 列的元素不为 0,此时 2k + 1即为最少的渡河次数 ,而矩阵 (AB ) k 中 1行 10列的元素为最佳的路径数目。 经过计算 K = 5时 , (AB ) 5A的第 1行 10列元素为 2,所 以需 11次渡河 ,有两条最佳路径。 最后我们用图解法来描述 : 前面我们已求出问题的 10种允许状态 ,允许决策向量 集合 D = { ( u, v) : u + v = 1, 2} ,状态转移方程为 Sk + 1 = Sk + ( - 1) k dk ,如图 2,标出 10种允许状态 ,找出从 s1 经由允许 状态到原点的路径 ,该路径还要满足奇数次向左 ,向下 ;偶数 次向右 ,向上。 图 2　坐标平面示意图 由图 3可得这样的过河策略 ,共分 11次决策 ,于应用 邻接矩阵所求的结果吻合。 图 3　状态转移线路图 3　结论 使用邻接矩阵描述方便直观 ,使问题变的简单易懂 ,应 用邻接矩阵的方法不仅能够说明 vi 到 vj的路径的长度为 k 时 ,是否可行 ,而且还能反映出可行的路径条数 ,从而能够寻 找出最合实际的路径或最短路径 ,是一种简 (下转第 24页 ) 91　第 2期 　　　　　　　　　　　　　　　　　刘亚国 :图论中邻接矩阵的应用 参考文献 : [ 1 ]　徐卫明 , 赵成平.一道概率题的探索与引伸 [ J ]. 数学 通讯 , 2006, (3) : 13. [ 2 ]　复旦大学编. 概率论 [M ]. 北京 :高等教育出版社 , 1979. The Sk illful Proofs on the Con jecture L IU Zhi - gao (Anhu i U niversity of Technology, M a’anshan 243011, Ch ina) Abstract: The conjecture, which if the p robability of an event is p then the expectation of the experiment timesξwhere the event exactly occurred the m th m p in a sequence of independent trials, is respectively p roved skillfully by p robability generating function and decom2 posed sum formula. Furthermore, it is p roved that the variance of theξ is m (1 - p) p2 . Key words: random variable; expectation; generating function (上接第 19页 ) 单且便于计算机求解的方法。 (责编 :唐晓燕 ) 参考文献 : [ 1 ]　阮哓青 ,周义仓. 数学建模引论 [M ]. 北京 :高等教育 出版社 , 2005. [ 2 ]　胡运权. 运筹学 教程 人力资源管理pdf成真迷上我教程下载西门子数控教程protel99se入门教程fi6130z安装使用教程 [M ]. 北京 :清华大学出版社 , 1998. [ 3 ]　王朝瑞. 图论 [M ]. 北京 :国防工业出版社 , 1985. Adjacen t M a tr ix Applica tion in Graph Theory L IU Ya - guo (Heyuan V oca tiona l Techn ica l College, Heyuan 517000, Ch ina) Abstract: Introduced adjacent matrix’s definition and an important theorem, have p romulgated in the graph theory Ak p ractical signifi2 cance, and crossed river two questions using adjacent matrix’s method ingenious solution locking device kto p revent going in packing and the merchant, caused the comp lex question simp le easy to understand, and easy to p romote, has achieved the twice the result with half the effort effect, manifested the adjacent matrix in the p ractical life app lication value. Key words: chart; adjacent matrix; apex; side; way 42 　　　　　　　　　　　　　　 　忻 州 师 范 学 院 学 报　　　　　　　　　　　　　　　　　第 24卷