锁具装箱问题中锁具总数的图论算法

　 锁具装箱问题中锁具总数的图论算法 杨华康　任国鹏 (云南大学数学系, 昆明 650091) 摘要　本文为 1994 年全国大学生数学建模竞赛B 题 (锁具装箱) 中关于锁具总数的求解提供 一种简便易行的图论算法. 只需具备最基本的图论知识, 即可掌握该算法, 而运用该算法, 计算量 将比现有各种求解算法少得多. 关键词　锁具总数　图论算法 1994 年全国大学生数学建模竞赛B 题 (锁具装箱) 中关于锁具总数的问题可叙述如下 ( [ 1 ]) : 某厂生产一种弹子锁具, 每个锁具的钥匙有 5 个槽, 每个槽的高度从{1, 2, 3, 4, 5, 6}中任 取一数. 由于工艺及其它原因, 制造锁具时对 5 个槽的高度还有两个限制: (1)至少有 3 个不同 的数; (2) 相邻两槽的高度之差不能为 5. 满足以上条件制造出来的所有互不相同的锁具称为 一批. 我们的问题是如何确定每一批锁具的个数 x ? 目前, 求解上述问题的方法有两种, 一种是计算机枚举, 另一种是排列组合计数 ( [ 2 ], [ 3 ]). 这两种方法计算量都比较大, 特别, 针对槽高的限制 (2) 运用加法原理时, 不易排除重复 计数的各种可能情形. 本文提出一种简便易行的图论算法, 只需具备最基本的图论知识即可掌 握该算法. 而运用该算法, 计算量将比现有各种求解方法要少得多, 即使用笔算也能迅速得到 正确的解答. 易见, x = x 1- x 2, 其中, x 1= 相邻两槽高度之差不为 5 的锁具数, 即: 满足限制条件 (2) 的 锁具数; x 2= 相邻两槽高度之差不为 5 且槽高仅有 1 个或 2 个的锁具数, 即: 满足限制条件 (2) 但不满足限制条件 (1)的锁具数. 我们用图论方法计算 x 1 和 x 2. 本文所用的图论术语和结论见[ 4 ] 图 1 设G= (V , E )为无向图,V = {v 1, v 2, ⋯, v n}为顶点集, E 为边集. 令: A = {a ij }n×n , 其中 a ij = 0, 若 v iv j∈E , 1, 其它, 称A 为G 的邻接矩阵. 基本引理　令 A k = A ×A ×⋯×A k次 = {a (k)ij }n×n , 则 a (k )ij = G 中以 v i, v j 为端点的长度为 k 的道路数. 为利用上述引理计算 x 1 和 x 2, 我们构造无向图 G = (V , E )如下 (如图 1 所示) V = {1, 2, 3, 4, 5, 6}, E = { ij û i, j∈V 且û i- j û≠5}. 在G 中, 每一条长度为 4 的道路对应于一个相 　收稿日期: 1998204213 第 15 卷第 2 期 1999 年 4 月 　 工　科　数　学 JOU RNAL O F M A TH EM A T ICS FOR T ECHNOLO GY　 V o l. 15,N o. 2 A p r. 1999 邻两槽高度之差不为 5 的锁具, 即: 满足限制条件 (2) 的锁具. 反之, 亦然. 于是, 可通过G 的邻 接矩阵A 计算 x 1, 具体步骤如下: 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 2= 5 5 5 5 5 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 4 5 5 5 5 5 , A 4= 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 , 因此, x 1= ∑ 6 i= 1 ∑ 6 j = 1 a (4) ij = 6306. 又令 x 2= y 1+ y 2+ y 3+ y 4+ y 5+ y 6, 其中, y i= 满足限制条件 (2)但不满足限制条件 (1)且首位为 i 的锁具数, ( i= 1, 2, 3, 4, 5, 6). 显 然, y 1= y 6, y 3= y 4= y 5= y 2, 我们只需计算 y 1 和 y 2. 计算 y 1 可分别考虑槽高只有 1, 12, 13, 14, 15 的情形. 若只有 1, 这样的锁具数只有 1 个; 若只有 1 和 i ( i= 2, 3, 4, 5) , 这样的锁具数= G 中以 1 和 i 为顶点, 长度为 3 的道路数, 此数可通过A 的子矩阵A 1i= 第 1 行 第 i 行 1 1 1 1 ( i= 2, 3, 4, 5)计算得到. 事实上, 因为 A 21i= 2 2 2 2 , 　A 31i= 4 4 4 4 　 ( i= 2, 3, 4, 5) , 所以 y 1= 1+ (4+ 4+ 4+ 4- 1)×4= 61. 同理, 计算 y 2 时应考虑槽高只有 2, 21, 22, 23, 24, 25, 26 的情形, 类似计算可得 y 2= 1+ (4+ 4+ 4+ 4+ 4- 1)×5= 76. 于是, x 2= 61×2+ 76×4= 426, 　x = 6306- 426= 5880. 我们给出的上述算法显然具有既易理解又易操作的优点. 特别对于限制条件相同而槽数 改变时, 上述算法一样可以使用, 因而, 上述算法还具有很好的可扩展性. 参　考　文　献 1　1994 年全国大学生数学建模竞赛 试题 中考模拟试题doc幼小衔接 数学试题 下载云南高中历年会考数学试题下载N4真题下载党史题库下载 2　1994 年全国大学生数学建模竞赛参考 答案 八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案 3　黄宗虎, 李波, 李春福. 关于锁具装箱的数学模型. 数学的实践与认识, 1995 年第 1 期 4　李尚志主编. 数学建模竞赛教程 P314- P331. 江苏教育出版社, 1996 年 6 月第 1 版 011 　　　　　　　　　　　　　　工科数学　　　　　　　　　　　　　　第 15 卷 A Graph ic A lgor ithm to F ind the Tota l of the L ocks in Problem B of Ch inese M athematica l Con test in M odel ing (1994) Y ang H uakang　R en Guop eng (D epartm ent of M athem atics, Yunnan U niversity, Kunm ing 650091) Abstract　 In th is paper, w e p ropo se a graph ic algo rithm to find the to ta l of the lock s in p rob lem B of Ch inese M athem atical Contest in M odeling (1994) , If the reader has the basic know ledge abou t Graph T heo2 ry he can m aster th is algo rithm and th is algo rithm takes less computation tim e than the o ther p resen t m eth2 ods. Key words　the to ta l of the lock s, graph ic algo rithm. 111第 2 期　　　　　　　杨华康等: 锁具装箱问题中锁具总数的图论算法