基于最省刻度尺构造极小优美图的图论方法 |
| |
引用本文: | 唐保祥,任韩.基于最省刻度尺构造极小优美图的图论方法[J].厦门大学学报(自然科学版),2024(2):339-344. |
| |
作者姓名: | 唐保祥 任韩 |
| |
作者单位: | 1. 天水师范学院数学与统计学院;2. 华东师范大学数学科学学院 |
| |
基金项目: | 国家自然科学基金(11171114); |
| |
摘 要: | 目的]利用最省刻度尺的已有研究成果研究极小优美图的构造方法.方法]对任意正整数n≥2,在长度是n的无刻度直尺上最少刻多少个刻度,就能度量1-n的所有长度,这就是最省刻度的尺子问题.给定正整数n,存在m个整数组成的集合{ai},满足0=a12<…m=n,使得任意整数s(0≤s≤n)均可表示成该集合中两个元素的差aj-ai,则称{ai}为n上的受限差基.根据极小优美图和受限差基的定义,将极小优美图问题等效为最省刻度尺问题进而得到极小优美图的构造方法.结果]由n≥5时Kn不是优美图和n≥1时图K4+Kn,n是优美图的结论,得到了边数是6至82的极小优美图顶点数的上下界;用构造方法给出了图K3∨K1,3,n-3e,K3,n∨K3-e和K2,3,n
|
关 键 词: | 最省刻度尺 优美图 联图 极小优美图 优美标号 |
|
|