Please wait a minute...
浙江大学学报（理学版）
浙江大学学报（理学版）  2024, Vol. 51 Issue (2): 178-185    DOI: 10.3785/j.issn.1008-9497.2024.02.006
数学与计算机科学     
最省刻度尺设计的组合差集递推算法
唐保祥1(),任韩2
1.天水师范学院 数学与统计学院，甘肃 天水 741001
2.华东师范大学 数学科学学院，上海 200062
A recursive algorithm of combinatorial difference set design for least scale number on ruler
Baoxiang TANG1(),Han REN2
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
 全文: PDF(672 KB)   HTML( 2 )
摘要：

在长度为n（n≥2为正整数）的直尺上最少刻多少个刻度就能度量1到n的所有长度，这便是至今未解决的最省刻度尺问题。阐明了最省刻度尺与极小优美图之间的关系，给出了计算最省刻度尺的所有最省刻度值的组合差集递推算法，得到长度为3~40的最省刻度尺的所有最省刻度值，同时，结合图论模型，给出了长度为41~82的最省刻度尺的最省刻度值。
关键词： 最省刻度尺;  优美标号;  极小优美图;  优美标号算法;  组合差集递推算法    
Abstract:

For a positive integer n≥2, 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 algorithm
收稿日期: 2022-07-04 出版日期: 2024-03-08
CLC:  O 157  
基金资助: 国家自然科学基金资助项目(11171114)
作者简介: 唐保祥（1961—），ORCID：https：//orcid.org/0000-0002-1631-1482，男，本科，教授，主要从事图论与组合数学研究，E-mail：zhangmingtnx0618@sina.com.
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
唐保祥
任韩

引用本文:

唐保祥,任韩. 最省刻度尺设计的组合差集递推算法[J]. 浙江大学学报（理学版）, 2024, 51(2): 178-185.

Baoxiang TANG,Han REN. A recursive algorithm of combinatorial difference set design for least scale number on ruler. Journal of Zhejiang University (Science Edition), 2024, 51(2): 178-185.

链接本文:

https://www.zjujournals.com/sci/CN/10.3785/j.issn.1008-9497.2024.02.006    或    https://www.zjujournals.com/sci/CN/Y2024/V51/I2/178

图1  长度为9的最省刻度尺的4种刻度
图2  9条边的所有极小优美图
（0，1）（1，2）（2，3）（3，4）…（ n-1，n ）
（0，2）（1，3）（2，4）…（n-2，n）
（0，3）（1，4）…（n-3，n）
………
（0，n-1）（1，n）
（0，n ）
表1  集合｛0，1，2，…，n｝的所有二元子集
长度其中的一组最省刻度

每组

中的

刻度数

所有不同的刻度组数长度其中的一组最省刻度

每组

中的

刻度数

所有不同的刻度组数
30，2，332220，4，9，14，19，20，21，22818
40，2，3，443230，2，5，8，12，21，22，2384
50，3，4，544240，6，12，19，20，21，22，23，249944
60，2，5，642250，6，13，20，21，22，23，24，259460
70，4，5，6，7512260，5，11，16，22，23，24，25，269166
80，3，6，7，858270，5，11，17，23，24，25，26，27956
90，3，7，8，954280，2，4，6，7，18，19，37，28912
100，4，7，8，9，10638290，2，5，8，11，15，27，28，2996
110，4，8，9，10，11630300，6，13，18，25，26，27，28，29，30102 036
120，4，9，10，11，12614310，6，13，19，26，27，28，29，30，3110890
130，3，7，11，12，1366320，6，13，20，27，28，29，30，31，3210304
140，5，10，11，12，13，147130330，5，11，17，23，29，30，31，32，3310120
150，5，11，12，13，14，15780340，3，6，10，14，19，31，32，33，341020
160，4，8，13，14，15，16732350，2，8，10，17，19，30，31，34，351010
170，4，9，14，15，16，17712360，1，5，9，16，23，30，33，35，36102
180，6，13，14，15，16，17，188500370，7，15，23，31，32，33，34，35，36，37112 678
190，5，10，15，16，17，18，198326380，6，13，19，26，33，34，35，36，37，3811974
200，5，10，16，17，18，19，208150390，6，13，20，27，34，35，36，37，38，3811362
210，5，11，17，18，19，20，21866400，5，11，16，23，30，36，37，38，39，4011100
表2  长度为3~40的最省刻度尺的最省刻度
图3  图K1，1，m，n 的优美标号θ
xf （x）的上下界xf （x）的上下界xf （x）的上下界xf （x）的上下界
64≤f（6）≤4268≤f（26）≤94611≤f（46）≤126612≤f（66）≤15
75≤f（7）≤5278≤f（27）≤94711≤f（47）≤136713≤f（67）≤15
85≤f（8）≤5288≤f（28）≤104811≤f（48）≤136813≤f（68）≤15
95≤f（9）≤5299≤f（29）≤104911≤f（49）≤136913≤f（69）≤15
106≤f（10）≤6309≤f（30）≤105011≤f（50）≤137013≤f（70）≤16
116≤f（11）≤6319≤f（31）≤105111≤f（51）≤137113≤f（71）≤16
126≤f（12）≤6329≤f（32）≤105211≤f（52）≤137213≤f（72）≤16
136≤f（13）≤6339≤f（33）≤105311≤f（53）≤137313≤f（73）≤16
146≤f（14）≤7349≤f（34）≤105411≤f（54）≤147413≤f（74）≤16
156≤f（15）≤7359≤f（35）≤105511≤f（55）≤147513≤f（75）≤16
166≤f（16）≤7369≤f（36）≤105612≤f（56）≤147613≤f（76）≤16
177≤f（17）≤73710≤f（37）≤115712≤f（57）≤147713≤f（77）≤16
187≤f（18）≤83810≤f（38）≤115812≤f（58）≤147813≤f（78）≤16
197≤f（19）≤83910≤f（39）≤115912≤f（59）≤147914≤f（79）≤17
207≤f（20）≤84010≤f（40）≤126012≤f（60）≤148014≤f（80）≤17
218≤f（21）≤84110≤f（41）≤126112≤f（61）≤148114≤f（81）≤17
228≤f（22）≤84210≤f（42）≤126212≤f（62）≤158214≤f（82）≤17
238≤f（23）≤94310≤f（43）≤126312≤f（63）≤15
248≤f（24）≤94410≤f（44）≤126412≤f（64）≤15
258≤f（25）≤94510≤f（45）≤126512≤f（65）≤15
表3  有6~82条边的极小优美图的顶点数f （x）的上下界
直尺长度其中一组包括两端点的最省刻度数值最省刻度数
410，1，4，10，16，22，28，34，36，39，4111
420，1，2，3，19，24，28，32，36，39，4211
430，1，3，6，13，20，27，34，38，42，4311
440，1，2，3，4，10，16，22，28，34，39，4412
450，1，2，3，4，5，12，20，26，33，39，4512
460，6，13，20，27，34，41，42，43，44，45，4612
470，1，2，3，4，10，17，24，31，36，42，4712
480，1，2，3，23，24，29，33，37，41，45，4812
490，1，2，3，24，29，30，34，38，42，46，4912
500，1，3，6，13，20，27，34，41，45，49，5012
510，1，2，3，4，5，6，7，16，26，34，43，5113
520，1，2，3，4，10，17，24，31，36，42，47，5213
530，7，15，23，31，39，47，48，49，50，51，52，5313
540，1，2，3，4，5，6，14，23，32，39，47，5413
550，1，2，3，4，5，12，20，28，36，42，49，5513
560，1，2，3，27，28，33，37，41，45，49，53，5613
570，1，3，6，13，20，27，34，41，48，52，56，5713
580，1，2，3，27，32，36，40，44，48，52，55，5813
590，1，2，3，4，5，12，20，28，36，42，49，55，5914
600，1，2，3，4，10，17，24，30，37，44，49，55，6014
610，1，2，3，4，5，6，14，23，32，39，47，54，6114
620，1，2，3，4，5，6，14，23，31，40，47，55，6214
630，1，2，3，4，5，6，14，23，32，41，48，56，6314
640，1，3，6，13，20，27，34，41，48，55，59，63，6414
650，1，6，14，22，30，38，46，54，56，58，61，63，6514
660，1，2，3，31，36，40，44，48，52，56，60，63，6614
670，1，2，3，4，5，12，19，26，33，40，47，54，61，6715
680，1，2，3，4，10，17，24，31，38，45，52，57，63，6815
690，1，2，5，12，19，26，33，40，47，54，61，63，67，6915
700，1，2，3，4，5，6，14，23，32，41，48，56，63，7015
710，1，3，6，13，20，27，34，41，48，55，62，66，70，7115
720，1，2，6，14，22，30，38，46，54，62，65，69，71，7215
730，1，6，14，22，30，38，46，54，62，64，66，69，71，7315
740，1，2，3，35，40，44，48，52，56，60，64，68，71，7415
750，1，2，3，4，10，17，24，31，38，45，52，59，64，70，7516
760，1，2，5，12，19，26，33，40，47，54，61，68，70，74，7616
770，1，2，3，4，5，6，14，22，30，38，46，54，62，70，7716
780，1，3，6，13，20，27，34，41，48，55，62，69，73，77，7816
790，1，2，3，4，5，12，20，28，36，44，52，60，66，73，7916
800，1，2，3，4，5，6，14，23，32，40，49，58，65，73，8016
810，1，2，3，4，5，6，7，16，26，36，46，56，64，73，8116
820，1，2，3，39，44，48，52，56，60，64，68，72，76，79，8216
表4  长度为41~82的最省刻度尺的一组最省刻度值
1 曾令辉. 省刻度问题初探［J］. 数学通报， 2001 （10）： 36-37.
ZENG L H. A preliminary probe into the problem of the question of ruler with least number of scales［J］. Mathematical Bulletin， 2001 （10）： 36-37.
2 马克杰. 优美图［M］. 北京： 北京大学出版社， 1991.
MA K J. Graceful Graph［M］. Beijing： Peking University Press， 1991.
3 唐保祥. 2类包含K4的优美图及其注记［J］. 河北师范大学学报（自然科学版）， 2001， 25（3）： 304-305. DOI：10.3969/j.issn.1000-5854.2001.03.007
TANG B X. Two kinds of graceful graphs including K4 and their labeling［J］. Journal of Hebei Normal University （Natural Science Edition）， 2001， 25（3）： 304-305. DOI：10.3969/j.issn.1000-5854. 2001.03.007
doi: 10.3969/j.issn.1000-5854. 2001.03.007
4 唐保祥， 任韩. 优美图所有优美标号的生成算法［J］. 天津师范大学学报（自然科学版）， 2010， 30（4）： 5-8. DOI：10.3969/j.issn.1671-1114.2010.04.002
TANG B X， REN H. Generating algorithm for all graceful labeling of graceful graph［J］. Journal of Tianjin Normal University （Natural Science Edition）， 2010， 30（4）： 5-8. DOI：10.3969/j.issn. 1671-1114.2010.04.002
doi: 10.3969/j.issn. 1671-1114.2010.04.002
5 PEREIRA 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.019
doi: 10.1016/j.dam.2018.09.019
6 LLADO 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.012
doi: 10.1016/j.dam.2021.08.012
7 DEEN M， ELMAHDY G. New classes of graphs with edge δ-graceful labeling［J］. AIMS Mathematics， 2021， 7（3）： 3554-3589. DOI：10.3934/math.2022197
doi: 10.3934/math.2022197
8 DEEN M Z. Edge δ-graceful labeling for some cyclic-related graphs［J］. Advances in Mathematical Physics， 2019， 93： 1245-1260. DOI：10.1155/2020/6273245
doi: 10.1155/2020/6273245
9 牟亚蓉， 刘信生， 姚兵. 基于含圈非连通图优美性的拓扑图密码［J］. 华东师范大学学报（自然科学版）， 2020 （1）： 51-57. DOI：10.3969/j.issn.1000-5641. 201811045
MU 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. 201811045
doi: 10.3969/j.issn.1000-5641. 201811045
10 魏众德， 李敬文， 武永兰. 双圈图的优美性［J］. 吉林大学学报（理学版）， 2019， 57（1）： 42-48. DOI：10. 13413/j.cnki.jdxblxb.2017490
WEI Z D， LI J W， WU Y L. Gracefulness of bicyclic graphs［J］. Journal of Jilin University （Natural Science Edition）， 2019， 57（1）： 42-48. DOI：10. 13413/j.cnki.jdxblxb.2017490
doi: 10. 13413/j.cnki.jdxblxb.2017490
11 把丽娜， 刘倩， 刘信生， 等. 完全二部图优美性质探索［J］. 大连理工大学学报， 2017， 57（6）： 657-662. DOI：10.7511/dllgxb201706016
BA L N， LIU Q， LIU X S， et al. Exploration of gracefulness of some complete bipartite graphs［J］. Journal of Dalian University Technology， 2017， 57（6）： 657-662. DOI：10.7511/dllgxb201706016
doi: 10.7511/dllgxb201706016
12 唐保祥， 任韩. 两类图及其冠的优美标号［J］.东北师大学报（自然科学版）， 2017， 49（3）： 158-160. DOI：10.16163/j.cnki.22-1123/n.2017.03.031
TANG B X， REN H. The graceful labeling of two kinds graphs and its coronas［J］. Journal of Northeast Normal University （Natural Science Edition）， 2017， 49（3）： 158-160. DOI：10.16163/j.cnki.22-1123/n.2017.03.031
doi: 10.16163/j.cnki.22-1123/n.2017.03.031
13 唐保祥，任韩. 2类优美图的冠的优美标号［J］. 中山大学学报（自然科学版）， 2015， 54（5）： 24-27.
TANG B X， REN H. Graceful labeling of the crown for two kinds of graceful graphs ［J］. Acta Scientiarum Naturalium Universitatis Sunyatseni， 2015， 54（5）：24-27.
14 唐保祥， 任韩. 3类特殊图的优美性［J］. 武汉大学学报（理学版）， 2014， 60（6）： 553-556. DOI： 10. 14188/j.1671-8836.2014.06.001
TANG B X， REN H. The gracefulness of three types special graphs［J］. Journal of Wuhan University （Natural Science Edition）， 2014， 60（6）： 553-556. DOI：10.14188/j.1671-8836.2014.06.001
doi: 10.14188/j.1671-8836.2014.06.001
[1] 吴寒,刘奋进,尚凡琦,周艳红,阮昊桐. 可交换图的一些注记[J]. 浙江大学学报（理学版）, 2024, 51(2): 172-177.
[2] 郭育红. 与有序分拆的分部量1相关的恒等式及组合证明[J]. 浙江大学学报（理学版）, 2023, 50(3): 261-265.