最省刻度尺设计的组合差集递推算法.pdf

浙江大学学报（理学版）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 的所有长度，这便是至今未解决的最省刻度尺问题。阐明了最省刻度尺与极小优美图之间的关系，给出了计算最省刻度尺的所有最省刻度值的组合差集递推算法，得到长度为 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 Sciences，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 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 calculating 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 scales 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，其设计算法的计算量与n！有关，随n的增大陡然增大。事实上，最省刻度尺设计等同于极小优美图构造。优美图研究的理论成果已被广泛应用于通信网络寻址、编码设计、数据库管理、X射线密码技术、天文学、晶体结构中原子位置的测定、导弹控制、雷达、物流运输等方面。但是，目前尚未查阅到将优美图用于最省刻度尺设计的研究。对一般图优美性的研究至今没有系统化的理论，已经证明判定任意一个图是否为优美图是一个NP-难问题。图优美性的研究方法多为构造法2-14，但未查阅到通过构造极DOI：10.3785/j.issn.1008-9497.2024.02.006收稿日期：20220704；修回日期：20230316；接受日期：20230323；出版日期：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)|，使得对任意的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 个刻度的直尺共有 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|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，所以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。算法完成后，得到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算法实例例如，有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。采用优美标号算法，得到有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的 基 础 图 就 是 优 美图，该图顶点的所有数就是图的优美标号，|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。因此，极小优美图的顶点数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每行中含有子集 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，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唐保祥，等：最省刻度尺设计的组合差集递推算法第 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中任何一个数的最大数。构造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，35；（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算法分析对于优美标号算法，要得到长度为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，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，21，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，31，32，33，34，35，36，370，6，13，19，26，33，34，35，36，37，380，6，13，20，27，34，35，36，37，38，380，5，11，16，23，30，36，37，38，39，40每组中的刻度数889999991010101010101011111111所有不同的刻度组数184944460166561262 036890304120201022 678974362100181浙 江 大 学 学 报（理学版）第 51 卷度尺的所有最省刻度数，所需计算量为n！。对于组合差集递推算法，假设最省刻度数为m，首先要生成集合 1，2，n-1 的所有m元子集，运算量为()n-1m；其 次 逐 一 检 查 每 个m元 子 集 在 集 合 0，1，2，n 的二元子集，而在集合 0，1，2，n 的二元子集中共有()n+12个数对，即使检查了每个m元子集的()n+12个数对，运算量也为()n-1m()n+12。组合差集递推算法与优美标号算法的最大运算量之比为n+12m！(n-m-1)！1，随着n的增 大，该 比 值 减 小，例 如，当n=9时，m=5，n+12m！(n-m-1)！=0.006 9。事实上，不会查遍多个m元子集的()n+12个数对。因此，显著提高了组合差集递推算法的效率。6模型推广挖掘由组合差集递推算法计算出的长度为340的所有最省刻度数据，得到定理 2对任意的m，n Z+，完全 4部图K1，1，m，n是优美图。证 明 设K1，1，m，n的 顶 点 集 为V(K1，1，m，n)=x，y，ui，vj|i=1，2，n；j=1，2，m，显然|E(K1，1，m，n)|=mn+2(m+n)+1，|V(K1，1，m，n)|=m+n+2。定义图K1，1，m，n的优美标号为：(x)=0，(ui)=i，i=1，2，n，(vj)=(j+1)n+2j，j=1，2，m，(y)=mn+2(m+n)+1，图K1，1，m，n的优美标号如图 3所示。由的 定 义 知，顶 点V(K1，1，m，n)的 标 号 为S=0，1，n，(j+1)n+2j，mn+2(m+n)+1|j=1，2，m，所 以 映 射：V(K1，1，m，n)S是单射。映射导出的边标号生成的子集分别为：A1=(ui)-(x)|i=1，2，n=1，2，n，A2=(vj)-(x)|j=1，2，m=2n+2，3n+4，(m+1)n+2m，A3=(vj)-(ui)|j=1，2，m；i=1，2，n=(j+1)n+2j-i|i=1，2，n；j=1，2，m=2n+1，2n，n+2 3n+3，3n+2，2n+4 (m+1)n+2m-1，(m+1)n+2m-2，mn+2m，A4=(y)-(ui)|i=1，2，n=mn+2(m+n)，mn+2(m+n)-1，mn+2m+n+1，A5=(y)-(vj)|j=1，2，m=mn+2m-1，mn+2m-n-3，n+1，A6=(y)-(x)=mn+2(m+n)+1。由i=16Ai=1，2，mn+2(m+n)，知映射导出的映射：E(K1，1，m，n)i=16Ai是双射，故是图K1，1，m，n的优美标号，K1，1，m，n是优美图。定理 3边数为x的极小优美图的顶点数为f(x)，则 8x+1+12 f(x)2(x+3-1)，其中，x表示大于等于x的最小整数。证明假设有x条边的极小优美图有f(x)个顶点，优美标号函数给f(x)个顶点的标号分别为a1，a2，af(x)，则(f(x)2)x，所以f(x)8x+1+12 。此 外，优 美 图K1，1，m，n的 边 数 为mn+2(m+n)+1，顶点数为m+n+2。因为(m+n)2-(m-n)2=4mn，所以当m+n给定，且m=n时，4mn取最小值。因此，当图K1，1，m，n的顶点数m+n+2固定，且m=n时，mn+2(m+n)+1取最大值，为n2+4n+1，对应的图K1，1，n，n即为极小优美图，其顶点数为2n+2。图 3图 K1，1，m，n的优美标号Fig.3Graceful labeling of the graph K1，1，m，n182唐保祥，等：最省刻度尺设计的组合差集递推算法第 2期由定理 1，知f(x)是x的单调递增函数，且当x增加 1时，f(x)至多增加 1。因为n2+4n+1=14()2n+22+(2n+2)-2，即图K1，1，n，n的顶点数f(x)与边数x的关系为x=14f2(x)+f(x)-2，故f(x)=2(x+3-1)，所以f(x)满足 8x+1+12 f(x)2(x+3-1)。由定理3，得到有682条边的极小优美图的顶点数的上下界，见表 3。结合表 2，得到长度为 4182 的最省刻度尺的一组最省刻度值，见表 4。7结 语具 有n条 边 的 优 美 图 的 顶 点 数f(n)的 下 界 8n+1+12 是由f(n)个顶点的完全图Kf(n)推得的，所以当n越大时，f(n)的真实值一般大于下界 8n+1+12 ；而顶点数f(n)的上界 2（n+3-1）是由特殊优美图K1，1，n，n的顶点与边 的 关 系 估 算 得 到 的。当n=0，1，2，3，4，5，6，7时，K1，1，n，n是极小优美图，当n 8时，图K1，1，n，n不一定是极小优美图，所以f(n)的上界 2（n+3-1）随着n的增大逐渐大于f(n)的真实值。求长度为n、至少有f(n)（含直尺的 2 个端点）个刻度，且能度量1，2，n中任意长度的直尺，等价于构造具有n条边、f(n)个顶点的极小优美图。假设长度为n、至少具有f(n)个刻度的直尺（包括直尺的两个端点）可以度量1，2，n中任意长度的直尺，且度量方式共有g(n)种，那么这把直尺就对应了g(n)个不同的极小优美图。因此，构造极小优美图是最省刻度尺设计的一种有效方法。表 3有 682条边的极小优美图的顶点数 f（x）的上下界Table 3Upper and lower bounds on the number of vertices f（x）for minimal graceful graphs with x edgesx678910111213141516171819202122232425f（x）的上下界4f（6）45f（7）55f（8）55f（9）56f（10）66f（11）66f（12）66f（13）66f（14）76f（15）76f（16）77f（17）77f（18）87f（19）87f（20）88f（21）88f（22）88f（23）98f（24）98f（25）9x2627282930313233343536373839404142434445f（x）的上下界8f（26）98f（27）98f（28）109f（29）109f（30）109f（31）109f（32）109f（33）109f（34）109f（35）109f（36）1010f（37）1110f（38）1110f（39）1110f（40）1210f（41）1210f（42）1210f（43）1210f（44）1210f（45）12x4647484950515253545556575859606162636465f（x）的上下界11f（46）1211f（47）1311f（48）1311f（49）1311f（50）1311f（51）1311f（52）1311f（53）1311f（54）1411f（55）1412f（56）1412f（57）1412f（58）1412f（59）1412f（60）1412f（61）1412f（62）1512f（63）1512f（64）1512f（65）15x6667686970717273747576777879808182f（x）的上下界12f（66）1513f（67）1513f（68）1513f（69）1513f（70）1613f（71）1613f（72）1613f（73）1613f（74）1613f（75）1613f（76）1613f（77）1613f（78）1614f（79）1714f（80）1714f（81）1714f（82）17183浙 江 大 学 学 报（理学版）第 51 卷表 4长度为 4182的最省刻度尺的一组最省刻度值Table 4Scale data for the most scale-saving rulers with lengths from 41 to 82直尺长度414243444546474849505152535455565758596061626364656667686970717273747576777879808182其中一组包括两端点的最省刻度数值0，1，4，10，16，22，28，34，36，39，410，1，2，3，19，24，28，32，36，39，420，1，3，6，13，20，27，34，38，42，430，1，2，3，4，10，16，22，28，34，39，440，1，2，3，4，5，12，20，26，33，39，450，6，13，20，27，34，41，42，43，44，45，460，1，2，3，4，10，17，24，31，36，42，470，1，2，3，23，24，29，33，37，41，45，480，1，2，3，24，29，30，34，38，42，46，490，1，3，6，13，20，27，34，41，45，49，500，1，2，3，4，5，6，7，16，26，34，43，510，1，2，3，4，10，17，24，31，36，42，47，520，7，15，23，31，39，47，48，49，50，51，52，530，1，2，3，4，5，6，14，23，32，39，47，540，1，2，3，4，5，12，20，28，36，42，49，550，1，2，3，27，28，33，37，41，45，49，53，560，1，3，6，13，20，27，34，41，48，52，56，570，1，2，3，27，32，36，40，44，48，52，55，580，1，2，3，4，5，12，20，28，36，42，49，55，590，1，2，3，4，10，17，24，30，37，44，49，55，600，1，2，3，4，5，6，14，23，32，39，47，54，610，1，2，3，4，5，6，14，23，31，40，47，55，620，1，2，3，4，5，6，14，23，32，41，48，56，630，1，3，6，13，20，27，34，41，48，55，59，63，640，1，6，14，22，30，38，46，54，56，58，61，63，650，1，2，3，31，36，40，44，48，52，56，60，63，660，1，2，3，4，5，12，19，26，33，40，47，54，61，670，1，2，3，4，10，17，24，31，38，45，52，57，63，680，1，2，5，12，19，26，33，40，47，54，61，63，67，690，1，2，3，4，5，6，14，23，32，41，48，56，63，700，1，3，6，13，20，27，34，41，48，55，62，66，70，710，1，2，6，14，22，30，38，46，54，62，65，69，71，720，1，6，14，22，30，38，46，54，62，64，66，69，71，730，1，2，3，35，40，44，48，52，56，60，64，68，71，740，1，2，3，4，10，17，24，31，38，45，52，59，64，70，750，1，2，5，12，19，26，33，40，47，54，61，68，70，74，760，1，2，3，4，5，6，14，22，30，38，46，54，62，70，770，1，3，6，13，20，27，34，41，48，55，62，69，73，77，780，1，2，3，4，5，12，20，28，36，44，52，60，66，73，790，1，2，3，4，5，6，14，23，32，40，49，58，65，73，800，1，2，3，4，5，6，7，16，26，36，46，56，64，73，810，1，2，3，39，44，48，52，56，60，64，68，72，76，79，82最省刻度数111111121212121212121313131313131313141414141414141415151515151515151616161616161616184唐保祥，等：最省刻度尺设计的组合差集递推算法第 2期参考文献（References）：1曾令辉.省刻度问题初探 J.数学通报，2001（10）：36-37.ZENG L H.A preliminary probe into the problem of the question of ruler with least number of scalesJ.Mathematical Bulletin，2001（10）：36-37.2马克杰.优美图 M.北京：北京大学出版社，1991.MA K J.Graceful GraphM.Beijing：Peking University Press，1991.3唐保祥.2类包含 K4的优美图及其注记 J.河北师范大 学 学 报（自 然 科 学 版），2001，25（3）：304-305.DOI：10.3969/j.issn.1000-5854.2001.03.007TANG B X.Two kinds of graceful graphs including K4 and their labelingJ.Journal of Hebei Normal University（Natural Science Edition），2001，25（3）：304-305.DOI：10.3969/j.issn.1000-5854.2001.03.0074唐保祥，任韩.优美图所有优美标号的生成算法 J.天津师范大学学报（自然科学版），2010，30（4）：5-8.DOI：10.3969/j.issn.1671-1114.2010.04.002TANG B X，REN H.Generating algorithm for all graceful labeling of graceful graphJ.Journal of Tianjin Normal University（Natural Science Edition），2010，30（4）：5-8.DOI：10.3969/j.issn.1671-1114.2010.04.0025PEREIRA J，SINGH T，ARUMUGAM S.Edge consecutive gracefulness of a graph J.Discrete Applied Mathematics，2020，280：214-220.DOI：10.1016/j.dam.2018.09.0196LLADO A，MOKHTAR H，SERRA O，et al.Distance-constrained labellings of Cartesian products of graphs J.Discrete Applied Mathematics，2021，304：375-383.DOI：10.1016/j.dam.2021.08.0127DEEN M，ELMAHDY G.New classes of graphs with edge-graceful labeling J.AIMS Mathematics，2021，7（3）：3554-3589.DOI：10.3934/math.20221978DEEN M Z.Edge-graceful labeling for some cyclic-related graphs J.Advances in Mathematical Physics，2019，93：1245-1260.DOI：10.1155/2020/62732459牟亚蓉，刘信生，姚兵.基于含圈非连通图优美性的拓扑图密码 J.华东师范大学学报（自然科学版），2020（1）：51-57.DOI：10.3969/j.issn.1000-5641.201811045MU Y R，LIU X S，YAO B.Topological graph passwords based on the gracefulness of disconnected graphs with circles J.Journal of East China Normal University（Natural Science），2020，45（1）：51-57.DOI：10.3969/j.issn.1000-5641.20181104510魏众德，李敬文，武永兰.双圈图的优美性 J.吉林大学学报（理学版），2019，57（1）：42-48.DOI：10.13413/ki.jdxblxb.2017490WEI Z D，LI J W，WU Y L.Gracefulness of bicyclic graphsJ.Journal of Jilin University（Natural Science Edition），2019，57（1）：42-48.DOI：10.13413/ki.jdxblxb.201749011把丽娜，刘倩，刘信生，等.完全二部图优美性质探索 J.大连理工大学学报，2017，57（6）：657-662.DOI：10.7511/dllgxb201706016BA L N，LIU Q，LIU X S，et al.Exploration of gracefulness of some complete bipartite graphsJ.Journal of Dalian University Technology，2017，57（6）：657-662.DOI：10.7511/dllgxb20170601612唐保祥，任韩.两类图及其冠的优美标