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

第 15 卷第 2 期 工　科　数　学 V o l. 15,N o. 2 1999 年 4 月 　JOU RN A L O F M A TH EM A T IC S FO R T ECHN OL O GY 　 A p r. 1999 　 锁具装箱问题中锁具总数的图论算法 杨华康　任国鹏 (云南大学数学系, 昆明 65009 1) ( ) 摘要　本文为 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 ] 设 = ( ,