(21)--第五讲 弹子锁具个数数学建模与系统仿真.pdf

弹子锁具个数

问题：某厂生产一种弹子锁具，每个锁具的钥匙有5个

槽，每个槽的高度从{1，2，3，4，5，6)中任取一

数．由于工艺及其它原因，制造锁具时对5个槽的高度

有两个限制：

(1)至少有3个不同的数；

(2)相邻两槽的高度之差不能为5．

满足以上条件制造出来的所有互不相同的锁具称

为一批．我们的问题是如何确定每一批锁具的个数?

该问题用图论中的邻接矩阵解决较为简单

易见，x=t-s，其中，t代表相邻两槽高度之差不为5

的锁具数，即：满足限制条件(2)的锁具数，s代表相

邻两槽高度之差不为5且槽高仅有1个或2个的锁具数，

即：满足限制条件(2)但不满足限制条件(1)的锁具

数．

我们用图论方法计算t和s.

65

构造无向图14

23

GV，E,V{1,2,3,4,5,6},E{iji,jV且ij5}



在G中每一条长度为4的道路对应于一个相邻两槽

高度之差不超过5的锁具，即满足限制条件（2）的锁

具，反之亦然，于是可以通过G的邻接矩阵A来计算t的

值.

定理：A=(aij)n×n（n为结点数）是图G=（V,E)的邻接矩阵，

lll

则A的幂A=(aij)n×n中的元素aij等于图G的第i个顶点到第j个

顶点且长为l的道路的个数。

111110555554141165165165165140



111111

555555165194194194194165

A1111112555555165194194194194165

A4

111111555555A

165194194194194165

111111555555

165194194194194165

011111455555



140165165165165141