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

doi:10.3785/j.issn.1008-9497.2024.02.006

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

唐保祥^,^,¹, 任韩²

1.天水师范学院数学与统计学院，甘肃天水 741001

2.华东师范大学数学科学学院，上海 200062

A recursive algorithm of combinatorial difference set design for least scale number on ruler

TANG Baoxiang^,^,¹, REN Han²

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

收稿日期: 2022-07-04 修回日期: 2023-03-16 接受日期: 2023-03-23

基金资助:

国家自然科学基金资助项目. 11171114

Received: 2022-07-04 Revised: 2023-03-16 Accepted: 2023-03-23

作者简介 About authors

唐保祥（1961—），ORCID：https：//orcid.org/0000-0002-1631-1482，男，本科，教授，主要从事图论与组合数学研究，E-mail：zhangmingtnx0618@sina.com. , E-mail：zhangmingtnx0618@sina.com

摘要

在长度为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.

Keywords： ruler with least number of scales ; graceful labeling ; minimal graceful graph ; graceful labeling algorithm ; combinatorial difference recursive algorithm

PDF (672KB) 元数据多维度评价相关文章导出 EndNote| Ris| Bibtex 收藏本文

本文引用格式

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

TANG Baoxiang, REN Han. A recursive algorithm of combinatorial difference set design for least scale number on ruler. Journal of Zhejiang University(Science Edition)[J], 2024, 51(2): 178-185 doi:10.3785/j.issn.1008-9497.2024.02.006

0　引言

设 $m$ ， $n$ 为正整数，其中 $n \geq 2$ ，在长为 $n$ 的直尺上添加 $m$ 个刻度（包括直尺两端的刻度），使得可以度量 $1$ 到 $n$ 之间的任何整数长度的尺寸，求 $m$ 的最小值。该最省刻度尺问题的一般情形至今未得到解决^［1］，其设计算法的计算量与 $n$ ！有关，随 $n$ 的增大陡然增大。事实上，最省刻度尺设计等同于极小优美图构造。

优美图研究的理论成果已被广泛应用于通信网络寻址、编码设计、数据库管理、 $X$ 射线密码技术、天文学、晶体结构中原子位置的测定、导弹控制、雷达、物流运输等方面。但是，目前尚未查阅到将优美图用于最省刻度尺设计的研究。对一般图优美性的研究至今没有系统化的理论，已经证明判定任意一个图是否为优美图是一个 $N P$ -难问题。图优美性的研究方法多为构造法^［2-14］，但未查阅到通过构造极小优美图来设计最省刻度尺的有关文献。在文献［1］中，长度为28，34，42，48，49，56，58的最省刻度尺的最省刻度数据均有误。本文试图利用构造极小优美图的思想，得到最省刻度尺的组合差集递推算法。

1　研究方法

定义1　设图 $G = (V, E)$ ，若存在单射 $θ : V (G) \to$ $\{0,1, 2, \dots, |E (G)|\}$ ，使得对任意的 $e = u v \in$ $E (G)$ ，由 $θ^{'} (e)$ $= |θ (u) - θ (v)|$ 导出双射 $θ^{'} : E (G) \to$ ${1,2, \dots,$ $|E (G)|}$ ，则称 $G$ 为优美图，称 $θ$ 为图 $G$ 的优美标号，称 $θ^{'}$ 为由 $θ$ 导出的边标号^［2］。

定义2　在给定边数的优美图中，称顶点数最少的优美图为极小优美图^［3-4］。

根据极小优美图的定义，一把有 $m$ 个刻度的最省刻度直尺的度量方式，对应为一个有 $m$ 个顶点、 $n$ 条边的图。在 $n$ 条边的每对顶点上，2个数对中的大数与小数之差恰为 $1,2, \dots, n$ ，对应的图恰为极小优美图。反过来，一个有 $m$ 个顶点、 $n$ 条边的极小优美图，对应为一把有 $m$ 个刻度、长度为 $n$ 个单位的最省刻度尺。

例如，长度为9个单位的直尺，最少刻度数为5（含2个端点），5个刻度的直尺共有4种，如图1所示，其度量方式有8种：

图1

新窗口打开| 下载原图ZIP| 生成PPT

图1 长度为9的最省刻度尺的4种刻度

Fig1 4 different scale values for the ruler with least number of scales with a length of 9

（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所示。

图2

新窗口打开| 下载原图ZIP| 生成PPT

图2 9条边的所有极小优美图

Fig.2 All minimal graceful graphs with 9 edges

定义3　设集合 $N = \{0,1, 2, \dots, n\}$ ，如果 $0 \leq i_{j} \leq$ $n - j$ ， $j = 1,2, \dots, n$ ，则称排列 $i_{1} i_{2} \dots i_{n}$ 为 $N$ 上的 $n$ 元优美排列^［4］。

2　优美标号算法

设简单图 $G = (V, E)$ 为有 $n$ 条边的优美图， $θ$ 为 $G$ 的优美标号， $θ$ 导出的双射 $θ^{'}$ 使得边 $e_{i}$ 满足 $θ^{'} (e_{i}) = |θ (u) - θ (v)| = i,$ $i = 1,2, \dots, n$ 。令 $a_{i} =$ $m i n \{θ (u), θ (v)\}$ ，则 $a_{1} a_{2} \dots a_{n}$ 是集合 $N =$ ${0,1,$ $2, \dots, n}$ 的优美排列。事实上，不妨设 $a_{i} = θ (v)$ ，因为 $θ (u) - θ (v) = i$ ，所以 $0 \leq a_{i} \leq$ $n - i$ ， $i = 1,2, \dots, n$ ，故 $a_{1} a_{2} \dots a_{n}$ 是集合 $N$ 的优美排列。显然，有 $n$ 条边的优美图 $G$ 的优美标号的集合与集合 $N$ 的优美排列集合之间存在一个双射。有 $n$ 条边的优美图，优美标号生成算法如下：

2.1　算法流程

步骤1　置 $a_{1} = 0, a_{2} = 0, \dots ， a_{n} = 0$ ，令 $θ^{'} = {(a_{i},$ $a_{i} + i) | i = 1,2, \dots, n}$ ；

步骤2　若 $a_{1} = n - 1, a_{2} = n - 2, \dots,$ $a_{n} = 0$ ，令 $θ^{'} = {(a_{i}, a_{i} + i) | i = 1,2, \dots, n}$ ，算法停止。否则，设 $j$ 是使 $a_{i} < n - i$ 成立的最大整数，置 $a_{1} = a_{1}$ ， $a_{2} =$ $a_{2}, \dots, a_{j - 1}$ $= a_{j - 1}, a_{j} =$ $a_{j} + 1$ ， $a_{j + 1} = 0,$ $\dots, a_{n} = 0,$ 令 $θ^{'} = {(a_{i}, a_{i} + i) |$ $i = 1,2, \dots,$ $n}$ ，转步骤 $2$ 。

算法完成后，得到 $n$ ！个优美标号，每个优美标号的集合为 ${a_{i}, a_{i} + i | i = 1,2,$ $\dots, n} 。$ 将由优美标号导出的边标号 $θ^{'}$ 写成二元关系式，即 $θ^{'} = {(a_{i}, a_{i}$ $+ i) | i = 1,2, \dots, n}$ ，对应的优美图就是二元关系 $θ^{'}$ 的基础图。

2.2　算法实例

例如，有3条边的优美图，优美标号生成过程如下：

（1） $a_{1} = 0, a_{2} = 0, a_{3} = 0$ ； ${θ_{1}}^{'} : 0,1 | 0,2 | 0,3 ；$

（2）因为 $a_{2} < 3 - 2$ ，所以 $a_{1} = 0$ ， $a_{2} = 0 + 1$ ， $a_{3} = 0$ ； ${θ_{2}}^{'} : 0,1 | 1,3 | 0,3$ ；

（3）因为 $a_{1} < 3 - 1$ ，所以 $a_{1} = 0 + 1$ ， $a_{2} = 0$ ， $a_{3} = 0$ ； ${θ_{3}}^{'} : 1,2 | 0,2 | 0,3$ ；

（4）因为 $a_{2} < 3 - 2$ ，所以 $a_{1} = 1$ ， $a_{2} = 0 + 1$ ， $a_{3} = 0$ ； ${θ_{4}}^{'} : 1,2 | 1,3 | 0,3$ ；

（5）因为 $a_{1} < 3 - 1$ ，所以 $a_{1} = 1 + 1$ ， $a_{2} = 0$ ， $a_{3} = 0$ ； ${θ_{5}}^{'} : 2,3 | 0,2 | 0,3$ ；

（6）因为 $a_{2} < 3 - 2$ ，所以 $a_{1} = 2$ ， $a_{2} = 0 + 1$ ， $a_{3} = 0$ ； ${θ_{6}}^{'} : 2,3 | 1,3 | 0,3$ 。

采用优美标号算法，得到有 $n$ 条边的所有优美图的优美标号，以及有 $n$ 条边的所有极小优美图的优美标号，从而得到长度为 $n$ 的最省刻度尺的最省刻度值以及所有的度量方式。显然，该算法的运算量为 $n$ ！，并非有效算法。

3　组合差集递推算法

3.1　模型的建立

有 $m$ 个顶点、 $n$ 条边的优美图的标号为 $i$ 的边，其两端点上的数对恰为取自集合｛0，1，2， $\dots, n$ ｝的第 $i$ 行上的某数对（ $i = 1,2, \dots, n$ ），如表1所示，这 $n$ 个数对形成的数的集合中恰有 $m$ 个不同的数。

表1 集合｛0，1，2，…，n｝的所有二元子集

Table 1 A subset of all 2 elements of set ｛0，1，2，…，n｝

（0，1）	（1，2）	（2，3）	（3，4）	…
（0，2）	（1，3）	（2，4）	…	（n-2，n）
（0，3）	（1，4）	…	（n-3，n）
…	…	…
（0，n-1）	（1，n）
（0，n ）

新窗口打开| 下载CSV

表1的每行恰取一数对 $(a_{i}, b_{i})$ ，得到二元关系： $R = {(a_{i}, b_{i}) | i = 1,2, \dots, n}$ ， $R$ 的基础图就是优美图，该图顶点的所有数就是图的优美标号， $|a_{i} - b_{i}|$ $(i = 1,$ $2, \dots, n)$ 就是导出的边标号。

于是，求有 $m$ 个刻度、长度为 $n$ 的最省刻度尺的刻度值，即为求集合 ${a_{i}, b_{i} | i = 1,2, \dots,$ $n}$ 的元素个数 $m$ 的最小值。

3.2　求解理论

定理1　极小优美图的顶点数 $f (x)$ 是边数 $x$ 的单调递增函数，当边数增加1时，顶点数至多增加1。

证明　假设边数为 $x_{0}$ 的极小优美图 $G_{0}$ 的顶点数为 $f (x_{0})$ ，因为优美标号 $θ$ 函数使得必有一个顶点 $v_{0}$ 的标号为 $0$ ，所以再给顶点 $v_{0}$ 添加一条悬挂边 $v_{0} u_{0}$ ，得到图 $G_{1}$ ，将顶点 $u_{0}$ 标号为 $x_{0} + 1$ ，图 $G_{1}$ 显然是优美图。所以，当边数为 $x_{0}$ 的极小优美图的顶点数为 $f (x_{0})$ 时，边数为 $x_{0} + 1$ 的极小优美图的顶点数至多为 $f (x_{0}) + 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$ ，对每个二元子集 ${a_{1}, a_{2}}$ ，划去表 $1$ 每行中含有子集 ${a_{1}, a_{2}}$ 的数对，如果表 $1$ 中每行至少剩余一个数对，则长度为 $4$ 的最省刻度尺上的刻度数集合为 ${0,1, 2,3, 4} - {a_{1}, a_{2}}$ 。

易知，二元子集 ${1,2},$ ${1,3},$ ${2,3}$ 都不能满足：划去表 $1$ 每行中含有子集 ${a_{1}, a_{2}}$ 的数对，使得表 $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$ ；

步骤2　生成集合 ${1,2, \dots, n - 1}$ 的 $r$ 元子集 ${1,2,$ $\dots, r}$ ，划去表 $1$ 每行中含有子集 ${1,2, \dots, r}$ 的数对，如果表1中每行至少剩余一个数对，输出最省刻度直尺上的刻度数集合： ${0,1, \dots, n} - {1,2, \dots, r}$ ；

步骤3　一般地，对 $r$ 元子集 ${c_{1}, c_{2}, \dots, c_{r}}$ ，划去表 $1$ 每行中含有子集 ${c_{1}, c_{2}, \dots,$ $c_{r}}$ 的数对，如果表1中每行至少剩余一个数对，输出最省刻度尺上的刻度数集合： ${0,1, 2, \dots, n} - {c_{1}, c_{2}, \dots, c_{r}}$ ；如果 $c_{1} = n - r,$ $c_{2} = n - r + 1, \dots,$ $c_{r} = n - 1,$ 则算法结束；否则，令 $j$ 是使 $c_{j} + 1 \leq n - 1$ 且 $c_{j} + 1$ 不是 $c_{1}, c_{2}, \dots, c_{r}$ 中任何一个数的最大数。构造 $r$ 元子集 ${c_{1}, c_{2}, \dots,$ $c_{j - 1}, c_{j} + 1, c_{j} + 2, \dots, c_{j} + r - j + 1}$ ，转步骤 $3$ 。

如果3个步骤执行完毕，仍没有得到长度为 $n$ 的最省刻度尺的最省刻度值，则令 $r = n - m$ ，再次执行上述算法，直至得到长度为 $n$ 的最省刻度尺的所有最省刻度值。

4　计算结果

用组合差集递推算法，得到了长度为 $3$ ~ $40$ 的最省刻度尺的所有最省刻度值。

例如，长度为 $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。

采用组合差集递推算法，得到长度为 $3$ ~ $40$ 的最省刻度尺的所有最省刻度数。鉴于数据较多，仅给出其中一组最省刻度，以及对应长度刻度尺所有最省刻度数，见表2。

表2 长度为3~40的最省刻度尺的最省刻度

Table 2 Scale data for the most scale-saving rulers with lengths from 3 to 40

长度	其中的一组最省刻度	每组中的刻度数	所有不同的刻度组数	长度	其中的一组最省刻度	每组中的刻度数	所有不同的刻度组数
3	0，2，3	3	2	22	0，4，9，14，19，20，21，22	8	18
4	0，2，3，4	4	3	23	0，2，5，8，12，21，22，23	8	4
5	0，3，4，5	4	4	24	0，6，12，19，20，21，22，23，24	9	944
6	0，2，5，6	4	2	25	0，6，13，20，21，22，23，24，25	9	460
7	0，4，5，6，7	5	12	26	0，5，11，16，22，23，24，25，26	9	166
8	0，3，6，7，8	5	8	27	0，5，11，17，23，24，25，26，27	9	56
9	0，3，7，8，9	5	4	28	0，2，4，6，7，18，19，37，28	9	12
10	0，4，7，8，9，10	6	38	29	0，2，5，8，11，15，27，28，29	9	6
11	0，4，8，9，10，11	6	30	30	0，6，13，18，25，26，27，28，29，30	10	2 036
12	0，4，9，10，11，12	6	14	31	0，6，13，19，26，27，28，29，30，31	10	890
13	0，3，7，11，12，13	6	6	32	0，6，13，20，27，28，29，30，31，32	10	304
14	0，5，10，11，12，13，14	7	130	33	0，5，11，17，23，29，30，31，32，33	10	120
15	0，5，11，12，13，14，15	7	80	34	0，3，6，10，14，19，31，32，33，34	10	20
16	0，4，8，13，14，15，16	7	32	35	0，2，8，10，17，19，30，31，34，35	10	10
17	0，4，9，14，15，16，17	7	12	36	0，1，5，9，16，23，30，33，35，36	10	2
18	0，6，13，14，15，16，17，18	8	500	37	0，7，15，23，31，32，33，34，35，36，37	11	2 678
19	0，5，10，15，16，17，18，19	8	326	38	0，6，13，19，26，33，34，35，36，37，38	11	974
20	0，5，10，16，17，18，19，20	8	150	39	0，6，13，20，27，34，35，36，37，38，38	11	362
21	0，5，11，17，18，19，20，21	8	66	40	0，5，11，16，23，30，36，37，38，39，40	11	100

新窗口打开| 下载CSV

5　算法分析

对于优美标号算法，要得到长度为 $n$ 的最省刻度尺的所有最省刻度数，所需计算量为 $n!$ 。对于组合差集递推算法，假设最省刻度数为 $m$ ，首先要生成集合 ${1,2, \dots, n - 1}$ 的所有 $m$ 元子集，运算量为 $(\begin{matrix} n - 1 \\ m \end{matrix})$ ；其次逐一检查每个 $m$ 元子集在集合 ${0,1, 2, \dots, n}$ 的二元子集，而在集合 ${0,1, 2, \dots, n}$ 的二元子集中共有 $(\begin{matrix} n + 1 \\ 2 \end{matrix})$ 个数对，即使检查了每个 $m$ 元子集的 $(\begin{matrix} n + 1 \\ 2 \end{matrix})$ 个数对，运算量也为 $(\begin{matrix} n - 1 \\ m \end{matrix}) \times (\begin{matrix} n + 1 \\ 2 \end{matrix})$ 。组合差集递推算法与优美标号算法的最大运算量之比为 $\frac{n + 1}{2 m! (n - m - 1)!} ≪ 1$ ，随着 $n$ 的增大，该比值减小，例如，当 $n = 9$ 时， $m = 5$ ， $\frac{n + 1}{2 m! (n - m - 1)!} = 0.006 \dot{9}$ 。事实上，不会查遍多个 $m$ 元子集的 $(\begin{matrix} n + 1 \\ 2 \end{matrix})$ 个数对。因此，显著提高了组合差集递推算法的效率。

6　模型推广

挖掘由组合差集递推算法计算出的长度为 $3$ ~ $40$ 的所有最省刻度数据，得到

定理2　对任意的 $m, n \in Z^{+}$ ，完全4部图 $K_{1,1, m, n}$ 是优美图。

证明　设 $K_{1,1, m, n}$ 的顶点集为 $V (K_{1,1, m, n}) = {x, y, u_{i}, v_{j} | i = 1,2, \dots, n;$ $j = 1,2, \dots, m}$ ，显然 $|E (K_{1,1, m, n})| =$ $m n +$ $2 (m + n) + 1$ ， $|V (K_{1,1, m, n})| =$ $m + n + 2$ 。

定义图 $K_{1,1, m, n}$ 的优美标号 $θ$ 为：

θ (x) = 0

，　

θ (u_{i}) = i, i = 1,2, \dots, n

，

θ (v_{j}) = (j + 1) n + 2 j, j = 1,2, \dots, m

，

θ (y) = m n + 2 (m + n) + 1

，

图 $K_{1,1, m, n}$ 的优美标号 $θ$ 如图3所示。

图3

新窗口打开| 下载原图ZIP| 生成PPT

图3 图K_1，1，_m_，_n 的优美标号 $θ$

Fig.3 Graceful labeling $θ$ of the graph K_1，1，_m_，_n

由 $θ$ 的定义知，顶点 $V (K_{1,1, m, n})$ 的标号为 $S =$ ${0,1, \dots, n, (j + 1) n + 2 j, m n +$ $2 (m + n) + 1 |$ $j = 1,2, \dots, m}$ ，所以映射 $θ : V (K_{1,1, m, n}) \to S$ 是单射。

映射 $θ$ 导出的边标号 $θ^{'}$ 生成的子集分别为：

A_{1} = {θ (u_{i}) - θ (x) | i = 1,2, \dots, n} =

{1,2, \dots, n}

，

\begin{array}{l} A_{2} = {θ (v_{j}) - θ (x) | j = 1,2, \dots, m} = \\ {2 n + 2,3 n + 4, \dots, (m + 1) n + 2 m} ， \end{array}

\begin{array}{l} A_{3} = {θ (v_{j}) - θ (u_{i}) | j = 1,2, \dots m; i = 1,2, \dots, n} = {(j + 1) n + 2 j - i | i = 1,2, \dots, n; j = 1,2, \dots, m} = {2 n + 1,2 n, \dots, n + 2} ⋃ \\ {3 n + 3,3 n + 2, \dots, 2 n + 4} ⋃ \dots ⋃ \\ {(m + 1) n + 2 m - 1, (m + 1) n + \\ 2 m - 2, \dots, m n + 2 m}, \end{array}

A_{4} = {θ (y) - θ (u_{i}) | i = 1,2, \dots, n} = {m n + 2 (m + n), m n + 2 (m + n) - 1, \dots, m n + 2 m + n + 1},

\begin{array}{l} A_{5} = {θ (y) - θ (v_{j}) | j = 1,2, \dots, m} = \\ {m n + 2 m - 1, m n + 2 m - n - 3, \dots, n + 1}, \end{array}

A_{6} = {θ (y) - θ (x)} = {m n + 2 (m + n) + 1} 。

由 $\cup_{i = 1}^{6} A_{i} = {1,2, \dots, m n + 2 (m + n)}$ ，知映射 $θ$ 导出的映射 $θ^{'} : E (K_{1,1, m, n}) \to \cup_{i = 1}^{6} A_{i}$ 是双射，故 $θ$ 是图 $K_{1,1, m, n}$ 的优美标号， $K_{1,1, m, n}$ 是优美图。

定理3　边数为 $x$ 的极小优美图的顶点数为 $f (x)$ ，则

$\{\frac{\sqrt[]{8 x + 1} + 1}{2}\} \leq f (x)$ $\leq \{2 (\sqrt[]{x + 3} - 1)\}$ ，其中， $\{x\}$ 表示大于等于 $x$ 的最小整数。

证明　假设有 $x$ 条边的极小优美图有 $f (x)$ 个顶点，优美标号 $θ$ 函数给 $f (x)$ 个顶点的标号分别为 $a_{1}, a_{2}, \dots, a_{f (x)}$ ，则 $(\begin{matrix} f (x) \\ 2 \end{matrix}) \geq x,$ 所以

f (x) \geq \{\frac{\sqrt[]{8 x + 1} + 1}{2}\}

。

此外，优美图 $K_{1,1, m, n}$ 的边数为 $m n + 2 (m + n) + 1$ ，顶点数为 $m + n + 2$ 。因为 ${(m + n)}^{2} -$ ${(m - n)}^{2} = 4 m n$ ，所以当 $m + n$ 给定，且 $m = n$ 时， $4 m n$ 取最小值。因此，当图 $K_{1,1, m, n}$ 的顶点数 $m + n + 2$ 固定，且 $m = n$ 时， $m n + 2 (m + n) + 1$ 取最大值，为 $n^{2} + 4 n + 1$ ，对应的图 $K_{1,1, n, n}$ 即为极小优美图，其顶点数为 $2 n + 2$ 。

由定理1，知 $f (x)$ 是 $x$ 的单调递增函数，且当 $x$ 增加1时， $f (x)$ 至多增加1。因为

n^{2} + 4 n + 1 = \frac{1}{4} {(2 n + 2)}^{2} + (2 n + 2) - 2

，

即图 $K_{1,1, n, n}$ 的顶点数 $f (x)$ 与边数 $x$ 的关系为 $x = \frac{1}{4} f^{2} (x) + f (x) - 2$ ，故 $f (x) =$ $2 (\sqrt[]{x + 3} - 1)$ ，所以 $f (x)$ 满足

\{\frac{\sqrt[]{8 x + 1} + 1}{2}\} \leq f (x) \leq {2 (\sqrt[]{x + 3} - 1)}

。

由定理 $3$ ，得到有 $6 ~ 82$ 条边的极小优美图的顶点数的上下界，见表3。

表3 有6~82条边的极小优美图的顶点数f （x）的上下界

Table 3 Upper and lower bounds on the number of vertices f （x） for minimal graceful graphs with x edges

x	f （x）的上下界	x	f （x）的上下界	x	f （x）的上下界	x	f （x）的上下界
6	4≤f（6）≤4	26	8≤f（26）≤9	46	11≤f（46）≤12	66	12≤f（66）≤15
7	5≤f（7）≤5	27	8≤f（27）≤9	47	11≤f（47）≤13	67	13≤f（67）≤15
8	5≤f（8）≤5	28	8≤f（28）≤10	48	11≤f（48）≤13	68	13≤f（68）≤15
9	5≤f（9）≤5	29	9≤f（29）≤10	49	11≤f（49）≤13	69	13≤f（69）≤15
10	6≤f（10）≤6	30	9≤f（30）≤10	50	11≤f（50）≤13	70	13≤f（70）≤16
11	6≤f（11）≤6	31	9≤f（31）≤10	51	11≤f（51）≤13	71	13≤f（71）≤16
12	6≤f（12）≤6	32	9≤f（32）≤10	52	11≤f（52）≤13	72	13≤f（72）≤16
13	6≤f（13）≤6	33	9≤f（33）≤10	53	11≤f（53）≤13	73	13≤f（73）≤16
14	6≤f（14）≤7	34	9≤f（34）≤10	54	11≤f（54）≤14	74	13≤f（74）≤16
15	6≤f（15）≤7	35	9≤f（35）≤10	55	11≤f（55）≤14	75	13≤f（75）≤16
16	6≤f（16）≤7	36	9≤f（36）≤10	56	12≤f（56）≤14	76	13≤f（76）≤16
17	7≤f（17）≤7	37	10≤f（37）≤11	57	12≤f（57）≤14	77	13≤f（77）≤16
18	7≤f（18）≤8	38	10≤f（38）≤11	58	12≤f（58）≤14	78	13≤f（78）≤16
19	7≤f（19）≤8	39	10≤f（39）≤11	59	12≤f（59）≤14	79	14≤f（79）≤17
20	7≤f（20）≤8	40	10≤f（40）≤12	60	12≤f（60）≤14	80	14≤f（80）≤17
21	8≤f（21）≤8	41	10≤f（41）≤12	61	12≤f（61）≤14	81	14≤f（81）≤17
22	8≤f（22）≤8	42	10≤f（42）≤12	62	12≤f（62）≤15	82	14≤f（82）≤17
23	8≤f（23）≤9	43	10≤f（43）≤12	63	12≤f（63）≤15
24	8≤f（24）≤9	44	10≤f（44）≤12	64	12≤f（64）≤15
25	8≤f（25）≤9	45	10≤f（45）≤12	65	12≤f（65）≤15

新窗口打开| 下载CSV

结合表2，得到长度为41~82的最省刻度尺的一组最省刻度值，见表4。

表4 长度为41~82的最省刻度尺的一组最省刻度值

Table 4 Scale data for the most scale-saving rulers with lengths from 41 to 82

直尺长度	其中一组包括两端点的最省刻度数值	最省刻度数
41	0，1，4，10，16，22，28，34，36，39，41	11
42	0，1，2，3，19，24，28，32，36，39，42	11
43	0，1，3，6，13，20，27，34，38，42，43	11
44	0，1，2，3，4，10，16，22，28，34，39，44	12
45	0，1，2，3，4，5，12，20，26，33，39，45	12
46	0，6，13，20，27，34，41，42，43，44，45，46	12
47	0，1，2，3，4，10，17，24，31，36，42，47	12
48	0，1，2，3，23，24，29，33，37，41，45，48	12
49	0，1，2，3，24，29，30，34，38，42，46，49	12
50	0，1，3，6，13，20，27，34，41，45，49，50	12
51	0，1，2，3，4，5，6，7，16，26，34，43，51	13
52	0，1，2，3，4，10，17，24，31，36，42，47，52	13
53	0，7，15，23，31，39，47，48，49，50，51，52，53	13
54	0，1，2，3，4，5，6，14，23，32，39，47，54	13
55	0，1，2，3，4，5，12，20，28，36，42，49，55	13
56	0，1，2，3，27，28，33，37，41，45，49，53，56	13
57	0，1，3，6，13，20，27，34，41，48，52，56，57	13
58	0，1，2，3，27，32，36，40，44，48，52，55，58	13
59	0，1，2，3，4，5，12，20，28，36，42，49，55，59	14
60	0，1，2，3，4，10，17，24，30，37，44，49，55，60	14
61	0，1，2，3，4，5，6，14，23，32，39，47，54，61	14
62	0，1，2，3，4，5，6，14，23，31，40，47，55，62	14
63	0，1，2，3，4，5，6，14，23，32，41，48，56，63	14
64	0，1，3，6，13，20，27，34，41，48，55，59，63，64	14
65	0，1，6，14，22，30，38，46，54，56，58，61，63，65	14
66	0，1，2，3，31，36，40，44，48，52，56，60，63，66	14
67	0，1，2，3，4，5，12，19，26，33，40，47，54，61，67	15
68	0，1，2，3，4，10，17，24，31，38，45，52，57，63，68	15
69	0，1，2，5，12，19，26，33，40，47，54，61，63，67，69	15
70	0，1，2，3，4，5，6，14，23，32，41，48，56，63，70	15
71	0，1，3，6，13，20，27，34，41，48，55，62，66，70，71	15
72	0，1，2，6，14，22，30，38，46，54，62，65，69，71，72	15
73	0，1，6，14，22，30，38，46，54，62，64，66，69，71，73	15
74	0，1，2，3，35，40，44，48，52，56，60，64，68，71，74	15
75	0，1，2，3，4，10，17，24，31，38，45，52，59，64，70，75	16
76	0，1，2，5，12，19，26，33，40，47，54，61，68，70，74，76	16
77	0，1，2，3，4，5，6，14，22，30，38，46，54，62，70，77	16
78	0，1，3，6，13，20，27，34，41，48，55，62，69，73，77，78	16
79	0，1，2，3，4，5，12，20，28，36，44，52，60，66，73，79	16
80	0，1，2，3，4，5，6，14，23，32，40，49，58，65，73，80	16
81	0，1，2，3，4，5，6，7，16，26，36，46，56，64，73，81	16
82	0，1，2，3，39，44，48，52，56，60，64，68，72，76，79，82	16

新窗口打开| 下载CSV

7　结语

具有 $n$ 条边的优美图的顶点数 $f (n)$ 的下界 $\{\frac{\sqrt[]{8 n + 1} + 1}{2}\}$ 是由 $f (n)$ 个顶点的完全图 $K_{f (n)}$ 推得的，所以当 $n$ 越大时， $f (n)$ 的真实值一般大于下界 $\{\frac{\sqrt[]{8 n + 1} + 1}{2}\}$ ；而顶点数 $f (n)$ 的上界 ${2 （ \sqrt[]{n + 3} - 1 ）}$ 是由特殊优美图 $K_{1,1, n, n}$ 的顶点与边的关系估算得到的。当 $n = 0,1, 2,3, 4,5, 6,7$ 时， $K_{1,1, n, n}$ 是极小优美图，当 $n \geq 8$ 时，图 $K_{1,1, n, n}$ 不一定是极小优美图，所以 $f (n)$ 的上界 ${2 （ \sqrt[]{n + 3} - 1 ）}$ 随着 $n$ 的增大逐渐大于 $f (n)$ 的真实值。

求长度为 $n$ 、至少有 $f (n)$ （含直尺的2个端点）个刻度，且能度量 $1,2, \dots,$ $n$ 中任意长度的直尺，等价于构造具有 $n$ 条边、 $f (n)$ 个顶点的极小优美图。假设长度为 $n$ 、至少具有 $f (n)$ 个刻度的直尺（包括直尺的两个端点）可以度量 $1,2, \dots, n$ 中任意长度的直尺，且度量方式共有 $g (n)$ 种，那么这把直尺就对应了 $g (n)$ 个不同的极小优美图。因此，构造极小优美图是最省刻度尺设计的一种有效方法。

http://dx.doi.org/10.3785/j.issn.1008-9497.2024.02.006

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

曾令辉

省刻度问题初探

［J］. 数学通报， 2001 （10）： 36-37.

[本文引用: 2]

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]

[2]

马克杰

. 优美图［M］. 北京：北京大学出版社， 1991.

[本文引用: 2]

K J

. Graceful Graph［M］. Beijing： Peking University Press， 1991.

[本文引用: 2]

[3]

唐保祥

2类包含K₄的优美图及其注记

［J］. 河北师范大学学报（自然科学版）， 2001， 25（3）： 304-305. DOI：10.3969/j.issn.1000-5854.2001.03.007

[本文引用: 1]

TANG

B X

Two kinds of graceful graphs including K₄ 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

[本文引用: 1]

[4]

唐保祥，任韩.

优美图所有优美标号的生成算法

［J］. 天津师范大学学报（自然科学版）， 2010， 30（4）： 5-8. DOI：10.3969/j.issn.1671-1114.2010.04.002

[本文引用: 2]

TANG

B X

， REN

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

[本文引用: 2]

[5]

PEREIRA

， SINGH

， ARUMUGAM

Edge consecutive gracefulness of a graph

［J］. Discrete Applied Mathematics， 2020， 280： 214-220. DOI：10.1016/j.dam.2018.09.019

[6]

LLADO

， MOKHTAR

， SERRA

， 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

[7]

DEEN

， ELMAHDY

New classes of graphs with edge δ-graceful labeling

［J］. AIMS Mathematics， 2021， 7（3）： 3554-3589. 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

[9]

牟亚蓉，刘信生，姚兵.

基于含圈非连通图优美性的拓扑图密码

［J］. 华东师范大学学报（自然科学版）， 2020 （1）： 51-57. DOI：10.3969/j.issn.1000-5641. 201811045

Y R

， LIU

X S

， YAO

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

[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

[11]

把丽娜，刘倩，刘信生，等.

完全二部图优美性质探索

［J］. 大连理工大学学报， 2017， 57（6）： 657-662. DOI：10.7511/dllgxb201706016

L N

， 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

[12]

唐保祥，任韩.

两类图及其冠的优美标号

［J］.东北师大学报（自然科学版）， 2017， 49（3）： 158-160. DOI：10.16163/j.cnki.22-1123/n.2017.03.031

TANG

B X

， REN

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

[13]

唐保祥，任韩.

2类优美图的冠的优美标号

［J］. 中山大学学报（自然科学版）， 2015， 54（5）： 24-27.

TANG

B X

， REN

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

[本文引用: 1]

TANG

B X

， REN

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

[本文引用: 1]

省刻度问题初探

2001

... 设

m

，

n

为正整数，其中

n \geq 2

，在长为

n

的直尺上添加

m

个刻度（包括直尺两端的刻度），使得可以度量

1

到

n

之间的任何整数长度的尺寸，求

m

的最小值.该最省刻度尺问题的一般情形至今未得到解决^［1］，其设计算法的计算量与

n

！有关，随

n

的增大陡然增大.事实上，最省刻度尺设计等同于极小优美图构造. ...

... 优美图研究的理论成果已被广泛应用于通信网络寻址、编码设计、数据库管理、

X

射线密码技术、天文学、晶体结构中原子位置的测定、导弹控制、雷达、物流运输等方面.但是，目前尚未查阅到将优美图用于最省刻度尺设计的研究.对一般图优美性的研究至今没有系统化的理论，已经证明判定任意一个图是否为优美图是一个

N P

-难问题.图优美性的研究方法多为构造法^［2-14］，但未查阅到通过构造极小优美图来设计最省刻度尺的有关文献.在文献［1］中，长度为28，34，42，48，49，56，58的最省刻度尺的最省刻度数据均有误.本文试图利用构造极小优美图的思想，得到最省刻度尺的组合差集递推算法. ...

省刻度问题初探

2001

... 设

m

，

n

为正整数，其中

n \geq 2

，在长为

n

的直尺上添加

m

个刻度（包括直尺两端的刻度），使得可以度量

1

到

n

之间的任何整数长度的尺寸，求

m

的最小值.该最省刻度尺问题的一般情形至今未得到解决^［1］，其设计算法的计算量与

n

！有关，随

n

的增大陡然增大.事实上，最省刻度尺设计等同于极小优美图构造. ...

... 优美图研究的理论成果已被广泛应用于通信网络寻址、编码设计、数据库管理、

X

N P

1991

... 优美图研究的理论成果已被广泛应用于通信网络寻址、编码设计、数据库管理、

X

N P

... 定义1　设图

G = (V, E)

，若存在单射

θ : V (G) \to

\{0,1, 2, \dots, |E (G)|\}

，使得对任意的

e = u v \in

E (G)

，由

θ^{'} (e)

= |θ (u) - θ (v)|

导出双射

θ^{'} : E (G) \to

{1,2, \dots,

|E (G)|}

，则称

G

为优美图，称

θ

为图

G

的优美标号，称

θ^{'}

为由

θ

导出的边标号^［2］. ...

1991

... 优美图研究的理论成果已被广泛应用于通信网络寻址、编码设计、数据库管理、

X

N P

... 定义1　设图

G = (V, E)

，若存在单射

θ : V (G) \to

\{0,1, 2, \dots, |E (G)|\}

，使得对任意的

e = u v \in

E (G)

，由

θ^{'} (e)

= |θ (u) - θ (v)|

导出双射

θ^{'} : E (G) \to

{1,2, \dots,

|E (G)|}

，则称

G

为优美图，称

θ

为图

G

的优美标号，称

θ^{'}

为由

θ

导出的边标号^［2］. ...

2类包含K₄的优美图及其注记

2001

... 定义2　在给定边数的优美图中，称顶点数最少的优美图为极小优美图^［3-4］. ...

2类包含K₄的优美图及其注记

2001

... 定义2　在给定边数的优美图中，称顶点数最少的优美图为极小优美图^［3-4］. ...

优美图所有优美标号的生成算法

2010

... 定义2　在给定边数的优美图中，称顶点数最少的优美图为极小优美图^［3-4］. ...

... 定义3　设集合

N = \{0,1, 2, \dots, n\}

，如果

0 \leq i_{j} \leq

n - j

，

j = 1,2, \dots, n

，则称排列

i_{1} i_{2} \dots i_{n}

为

N

上的

n

元优美排列^［4］. ...

优美图所有优美标号的生成算法

2010

... 定义2　在给定边数的优美图中，称顶点数最少的优美图为极小优美图^［3-4］. ...

... 定义3　设集合

N = \{0,1, 2, \dots, n\}

，如果

0 \leq i_{j} \leq

n - j

，

j = 1,2, \dots, n

，则称排列

i_{1} i_{2} \dots i_{n}

为

N

上的

n

元优美排列^［4］. ...

Edge consecutive gracefulness of a graph

2020

Distance-constrained labellings of Cartesian products of graphs

2021

New classes of graphs with edge δ-graceful labeling

2021

Edge δ-graceful labeling for some cyclic-related graphs

2019

基于含圈非连通图优美性的拓扑图密码

2020

基于含圈非连通图优美性的拓扑图密码

2020

双圈图的优美性

2019

双圈图的优美性

2019

完全二部图优美性质探索

2017

完全二部图优美性质探索

2017

两类图及其冠的优美标号

2017

两类图及其冠的优美标号

2017

2类优美图的冠的优美标号

2015

2类优美图的冠的优美标号

2015

3类特殊图的优美性

2014

... 优美图研究的理论成果已被广泛应用于通信网络寻址、编码设计、数据库管理、

X

N P

3类特殊图的优美性

2014

... 优美图研究的理论成果已被广泛应用于通信网络寻址、编码设计、数据库管理、

X

N P

〈

〉