基于最省刻度尺构造极小优美图的图论方法OA北大核心CSTPCD

[目的]利用最省刻度尺的已有研究成果研究极小优美图的构造方法.[方法]对任意正整数n≥2,在长度是n的无刻度直尺上最少刻多少个刻度,就能度量1-n的所有长度,这就是最省刻度的尺子问题.给定正整数n,存在m个整数组成的集合{a_(i)},满足0=a_(1)<a_(2)<…<a_(m)=n,使得任意整数s(0≤s≤n)均可表示成该集合中两个元素的差a_(j)-a_(i),则称{a_(i)}为n上的受限差基.根据极小优美图和受限差基的定义,将极小优美图问题等效为最省刻度尺问题进而得到极小优美图的构造方法.[结果]由n≥5时K n不是优美图和n≥1时图K 4+K n,n是优美图的结论,得到了边数是6至82的极小优美图顶点数的上下界;用构造方法给出了图K_(3)∨K 1,3,n-3 e,K_(3,n)∨K_(3-e)和K_(2,3,n)∨K_(3)-7e的优美标号,从而证明了这三类图都是优美图,并且当0≤n≤9时,K_(3)∨K_(1,3,,n)-3 e和K_(2,3,n)∨K_(3)-7e都是极小优美图,当0≤n≤8时,K_(3,n)∨K_(3-e)都是极小优美图,由此给出了29组最省刻度尺的刻度值.[结论]最省刻度尺可以为构造极小优美图提供新的研究思路.