最省刻度尺设计的组合差集递推算法.pdf
《最省刻度尺设计的组合差集递推算法.pdf》由会员分享,可在线阅读,更多相关《最省刻度尺设计的组合差集递推算法.pdf(8页珍藏版)》请在咨信网上搜索。
1、浙江大学学报(理学版)Journal of Zhejiang University(Science Edition)http:/ 51 卷第 2 期2024 年 3月Vol.51 No.2Mar.2024 最省刻度尺设计的组合差集递推算法唐保祥1,任韩2(1.天水师范学院 数学与统计学院,甘肃 天水 741001;2.华东师范大学 数学科学学院,上海 200062)摘要:在长度为 n(n2 为正整数)的直尺上最少刻多少个刻度就能度量 1 到 n 的所有长度,这便是至今未解决的最省刻度尺问题。阐明了最省刻度尺与极小优美图之间的关系,给出了计算最省刻度尺的所有最省刻度值的组合差集递推算法,得到长度
2、为 340 的最省刻度尺的所有最省刻度值,同时,结合图论模型,给出了长度为4182的最省刻度尺的最省刻度值。关键词:最省刻度尺;优美标号;极小优美图;优美标号算法;组合差集递推算法中图分类号:O 157;TP 301.4 文献标志码:A 文章编号:10089497(2024)0217808TANG Baoxiang1,REN Han2(1.School of Mathematics and Statistics,Tianshui Normal University,Tianshui 741001,Gansu Province,China;2.School of Mathematics Scie
3、nces,East China Normal University,Shanghai 200062,China)A recursive algorithm of combinatorial difference set design for least scale number on ruler.Journal of Zhejiang University(Science Edition),2024,51(2):178185Abstract:For a positive integer n2,what is the minimum number of ticks to be engraved
4、on an unscaled ruler of length n to measure all lengths from 1 to n.This is an unsolved problem of ruler with least number of scales.This paper clarifies the relationship between ruler with the least number of scales and the minimal graceful graph,and a combined difference recursive algorithm for ca
5、lculating all the least scale values of ruler with the least number of scales is given.This algorithm calculates that the length is 3 to all the minimum scale values of the most scale-saving ruler of 40,and combined with the graph theory model,the minimum scale values of ruler with least number of s
6、cales with lengths from 41 to 82 are given.Key Words:ruler with least number of scales;graceful labeling;minimal graceful graph;graceful labeling algorithm;combinatorial difference recursive algorithm0引 言设m,n为正整数,其中n 2,在长为n的直尺上添加m个刻度(包括直尺两端的刻度),使得可以度量1到n之间的任何整数长度的尺寸,求m的最小值。该最省刻度尺问题的一般情形至今未得到解决1,其设计算
7、法的计算量与n!有关,随n的增大陡然增大。事实上,最省刻度尺设计等同于极小优美图构造。优美图研究的理论成果已被广泛应用于通信网络寻址、编码设计、数据库管理、X射线密码技术、天文学、晶体结构中原子位置的测定、导弹控制、雷达、物流运输等方面。但是,目前尚未查阅到将优美图用于最省刻度尺设计的研究。对一般图优美性的研究至今没有系统化的理论,已经证明判定任意一个图是否为优美图是一个NP-难问题。图优美性的研究方法多为构造法2-14,但未查阅到通过构造极DOI:10.3785/j.issn.1008-9497.2024.02.006收稿日期:20220704;修回日期:20230316;接受日期:2023
8、0323;出版日期:20240325.基金项目:国家自然科学基金资助项目(11171114).作者简介:唐保祥(1961),ORCID:https:/orcid.org/0000-0002-1631-1482,男,本科,教授,主要从事图论与组合数学研究,E-mail:.唐保祥,等:最省刻度尺设计的组合差集递推算法第 2期小优美图来设计最省刻度尺的有关文献。在文献1 中,长度为 28,34,42,48,49,56,58 的最省刻度尺的最省刻度数据均有误。本文试图利用构造极小优美图的思想,得到最省刻度尺的组合差集递推算法。1研究方法定义1设图G=(V,E),若存在单射:V(G)0,1,2,|E(G
9、)|,使得对任意的e=uv E(G),由(e)=|(u)-(v)|导 出 双 射:E(G)1,2,|E(G)|,则称G为优美图,称为图G的优美标号,称为由导出的边标号2。定义 2在给定边数的优美图中,称顶点数最少的优美图为极小优美图3-4。根据极小优美图的定义,一把有m个刻度的最省刻度直尺的度量方式,对应为一个有m个顶点、n条边的图。在n条边的每对顶点上,2个数对中的大数与小数之差恰为1,2,n,对应的图恰为极小优美图。反过来,一个有m个顶点、n条边的极小优美图,对应为一把有m个刻度、长度为n个单位的最省刻度尺。例如,长度为 9 个单位的直尺,最少刻度数为 5(含 2 个端点),5 个刻度的直
10、尺共有 4 种,如图 1 所示,其度量方式有 8种:(a)0,1|0,2|6,9|2,6|1,6|0,6|2,9|1,9|0,9|;(b)0,1|7,9|1,4|0,4|4,9|1,7|0,7|1,9|0,9|;(c)0,1|7,9|4,7|0,4|4,9|1,7|0,7|1,9|0,9|;(d)1,2|0,2|6,9|2,6|1,6|0,6|2,9|1,9|0,9|;(e)7,8|7,9|0,3|3,7|3,8|3,9|0,7|0,8|0,9|;(f)8,9|0,2|2,5|5,9|0,5|2,8|2,9|0,8|0,9|;(g)8,9|0,2|5,8|5,9|0,5|2,8|2,9|0,8
11、|0,9|;(h)8,9|7,9|0,3|3,7|3,8|3,9|0,7|0,8|0,9|。8 种度量方式对应的有 5 个顶点、9 条边的 8 个极小优美图如图 2所示。定 义 3 设 集 合N=0,1,2,n,如 果0 ijn-j,j=1,2,n,则称排列i1i2in为N上的n元优美排列4。2优美标号算法设简单图G=(V,E)为有n条边的优美图,为G的 优 美 标 号,导 出 的 双 射使 得 边ei满 足(ei)=|(u)-(v)|=i,i=1,2,n。令ai=min(u),(v),则a1a2an是 集 合N=0,1,2,n 的优美排列。事实上,不妨设ai=(v),因为(u)-(v)=i,
12、所以0 ain-i,i=1,2,n,故a1a2an是集合N的优美排列。显然,有n条边的优美图G的优美标号的集合与集合N的优美排列集合之间存在一个双射。有n条边的优美图,优美标号生成算法如下:2.1算法流程步 骤 1 置a1=0,a2=0,an=0,令=(ai,ai+i)|i=1,2,n;步骤 2若a1=n-1,a2=n-2,an=0,令=(ai,ai+i)|i=1,2,n,算 法 停 止。否则,设j是 使ai n-i成 立 的 最 大 整 数,置a1=a1,a2=a2,aj-1=aj-1,aj=aj+1,aj+1=0,an=0,令=(ai,ai+i)|i=1,2,n,转步骤2。算法完成后,得到
13、n!个优美标号,每个优美标号的集合为 ai,ai+i|i=1,2,n。将由优美标号 导 出 的 边 标 号写 成 二 元 关 系 式,即图 29条边的所有极小优美图Fig.2All minimal graceful graphs with 9 edges图 1长度为 9的最省刻度尺的 4种刻度Fig14 different scale values for the ruler with least number of scales with a length of 9179浙 江 大 学 学 报(理学版)第 51 卷=(ai,ai+i)|i=1,2,n,对应的优美图就是二元关系的基础图。2.2
14、算法实例例如,有3条边的优美图,优美标号生成过程如下:(1)a1=0,a2=0,a3=0;1:0,1|0,2|0,3;(2)因 为a2 3-2,所 以a1=0,a2=0+1,a3=0;2:0,1|1,3|0,3;(3)因 为a1 3-1,所 以a1=0+1,a2=0,a3=0;3:1,2|0,2|0,3;(4)因 为a2 3-2,所 以a1=1,a2=0+1,a3=0;4:1,2|1,3|0,3;(5)因 为a1 3-1,所 以a1=1+1,a2=0,a3=0;5:2,3|0,2|0,3;(6)因 为a2 3-2,所 以a1=2,a2=0+1,a3=0;6:2,3|1,3|0,3。采用优美标号
15、算法,得到有n条边的所有优美图的优美标号,以及有n条边的所有极小优美图的优美标号,从而得到长度为n的最省刻度尺的最省刻度值以及所有的度量方式。显然,该算法的运算量为n!,并非有效算法。3组合差集递推算法3.1模型的建立有m个 顶 点、n条 边 的 优 美 图 的 标 号 为i的边,其 两 端 点 上 的 数 对 恰 为 取 自 集 合0,1,2,n的第i行上的某数对(i=1,2,n),如表 1 所示,这n个数对形成的数的集合中恰有m个不同的数。表 1的每行恰取一数对(ai,bi),得到二元关系:R=(ai,bi)|i=1,2,n,R的 基 础 图 就 是 优 美图,该图顶点的所有数就是图的优美
16、标号,|ai-bi|(i=1,2,n)就是导出的边标号。于是,求有m个刻度、长度为n的最省刻度尺的刻度值,即为求集合 ai,bi|i=1,2,n 的元素个数m的最小值。3.2求解理论定理 1极小优美图的顶点数f(x)是边数x的单调递增函数,当边数增加 1时,顶点数至多增加 1。证明假设边数为x0的极小优美图G0的顶点数为f(x0),因为优美标号函数使得必有一个顶点v0的标号为0,所以再给顶点v0添加一条悬挂边v0u0,得到图G1,将顶点u0标号为x0+1,图G1显然是优美图。所以,当边数为x0的极小优美图的顶点数为f(x0)时,边数为x0+1的极小优美图的顶点数至多为f(x0)+1。因此,极小
17、优美图的顶点数f(x)是边数x的单调递增函数,且当边数增加 1时,顶点数至多增加 1。3.3递推算法显然,长度为3的最省刻度尺共有2种不同的刻 度:0,2,3和0,1,3。每 种 有3个 刻 度,即 集 合 1,2,3 中分别缺少了元素1和 2。根据最省刻度尺与极小优美图的关系,长度为4的最省刻度尺的最省刻度数至多为4。假设长度为4的最省刻度尺的最省刻度数为3,由于最省刻度包括端点0和4,且这2 个数不可或缺,也就是集合 1,2,3 中缺少2个元素。基于此,首先生成集合 1,2,3 的所有二元子集:1,2,1,3,2,3。然后,在表 1 中取n=4,对每个二元子集 a1,a2,划去表1每行中含
18、有子集 a1,a2的数对,如果表1中每行至少剩余一个数对,则 长 度 为4的 最 省 刻 度 尺 上 的 刻 度 数 集 合 为 0,1,2,3,4-a1,a2。易知,二元子集 1,2,1,3,2,3 都不能满足:划去表1每行中含有子集 a1,a2的数对,使得表1中每行至少剩余一个数对。所以,长度为4的最省刻度尺的最省刻度数一定为4。因此,可得集合 1,2,3 的所有一元子集:1,2,3。对每个一元子集 b,在表1中划去含有 b 的数对,至少有一行没有剩余数对,说明长度为4的最省刻度尺的最省刻度数为4。此时,得到长度为4的最省刻度尺的所有3个最省刻度:0,2,3,4;0,1,3,4;0,1,2
19、,4。因为长度为4的最省刻度尺的最省刻度数为4,所以长度为5的最省刻度尺的最省刻度数至多为5。将上述方法一般化,即已知长度为n-1的最省刻度尺的最省刻度数为m,从而可得长度为n的最省刻度尺的所有最省刻度值。这就是组合差集递推算法的思想。3.4算法流程步骤 1令r=n-m+1;表 1集合 0,1,2,n 的所有二元子集Table 1A subset of all 2 elements of set 0,1,2,n(0,1)(0,2)(0,3)(0,n-1)(0,n)(1,2)(1,3)(1,4)(1,n)(2,3)(2,4)(3,4)(n-3,n)(n-2,n)(n-1,n)180唐保祥,等:最
20、省刻度尺设计的组合差集递推算法第 2期步骤 2生成集合 1,2,n-1 的r元子集 1,2,r,划去表1每行中含有子集 1,2,r 的数对,如果表 1中每行至少剩余一个数对,输出最省 刻 度 直 尺 上 的 刻 度 数 集 合:0,1,n-1,2,r;步骤 3一般地,对r元子集 c1,c2,cr,划去表1每行中含有子集 c1,c2,cr的数对,如果表 1 中每行至少剩余一个数对,输出最省刻度尺上的刻度数集合:0,1,2,n-c1,c2,cr;如果c1=n-r,c2=n-r+1,cr=n-1,则算法结束;否 则,令j是 使cj+1 n-1且cj+1不 是c1,c2,cr中任何一个数的最大数。构造
21、r元子集 c1,c2,cj-1,cj+1,cj+2,cj+r-j+1,转步骤3。如果 3个步骤执行完毕,仍没有得到长度为n的最省刻度尺的最省刻度值,则令r=n-m,再次执行上述算法,直至得到长度为n的最省刻度尺的所有最省刻度值。4计算结果用组合差集递推算法,得到了长度为340的最省刻度尺的所有最省刻度值。例如,长度为35的最省刻度尺共有10组不同的最省刻度值,每组最省刻度值中都有10个刻度数,这10组不同的最省刻度值分别为:(1)0,2,8,10,17,19,30,31,34,35;(2)0,2,5,8,11,14,18,33,34,35;(3)0,2,5,7,13,19,25,31,34,3
22、5;(4)0,1,5,12,19,26,29,32,34,35;(5)0,1,5,12,16,26,29,32,34,35;(6)0,1,4,10,16,22,28,30,33,35;(7)0,1,4,5,16,18,25,27,33,35;(8)0,1,3,6,9,19,23,30,34,35;(9)0,1,3,6,9,16,23,30,34,35;(10)0,1,2,17,21,24,27,30,33,35。采用组合差集递推算法,得到长度为340的最省刻度尺的所有最省刻度数。鉴于数据较多,仅给出其中一组最省刻度,以及对应长度刻度尺所有最省刻度数,见表 2。5算法分析对于优美标号算法,要得到
23、长度为n的最省刻表 2长度为 340的最省刻度尺的最省刻度Table 2Scale data for the most scale-saving rulers with lengths from 3 to 40长度3456789101112131415161718192021其中的一组最省刻度0,2,30,2,3,40,3,4,50,2,5,60,4,5,6,70,3,6,7,80,3,7,8,90,4,7,8,9,100,4,8,9,10,110,4,9,10,11,120,3,7,11,12,130,5,10,11,12,13,140,5,11,12,13,14,150,4,8,13,14
24、,15,160,4,9,14,15,16,170,6,13,14,15,16,17,180,5,10,15,16,17,18,190,5,10,16,17,18,19,200,5,11,17,18,19,20,21每组中的刻度数3444555666677778888所有不同的刻度组数23421284383014613080321250032615066长度22232425262728293031323334353637383940其中的一组最省刻度0,4,9,14,19,20,21,220,2,5,8,12,21,22,230,6,12,19,20,21,22,23,240,6,13,20,2
25、1,22,23,24,250,5,11,16,22,23,24,25,260,5,11,17,23,24,25,26,270,2,4,6,7,18,19,37,280,2,5,8,11,15,27,28,290,6,13,18,25,26,27,28,29,300,6,13,19,26,27,28,29,30,310,6,13,20,27,28,29,30,31,320,5,11,17,23,29,30,31,32,330,3,6,10,14,19,31,32,33,340,2,8,10,17,19,30,31,34,350,1,5,9,16,23,30,33,35,360,7,15,23,3
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 刻度尺 设计 组合 差集递推 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。