非连通图及的优美性*

孙彩云, 王 涛

(华北科技学院，河北 三河 065201)

图的标号问题起始于1966年Rosa的著名的优美树猜想。图的标号问题是组合数学的热门课题之一，它不仅属于图论领域，也属于设计理论范畴。图的优美标号问题在编码设计、通讯网络及雷达脉冲等领域有着重要应用[1-4]。近年来，对连通图及非连通图的优美性问题研究都受到关注[5-10]。本文给出了两类非连通图优美性的证明。

以下所讨论的图G(V,E)均为简单无向图，设V=V(G)为图G的顶点集，E=E(G)为图G的边集，|A|为集合A的阶数，[a]为不超过实数a的最大整数。

定义1 设图G=(V,E)，如果对于每一个v∈V，存在一个非负整数f(v)(称为顶点V的标号)，且满足：

(i)∀u,v∈V，如果u≠v，则f(u)≠f(v)；

(ii) max{f(v)|v∈V}=|E|；

(iii) ∀u1v1,u2v2∈E，若u1v1≠u2v2，则f′(u1v1)≠f′(u2v2)， 其中，f′(u1v1)=|f(u1)-f(v1)|。则称图G是优美图，f是G的一个优美标号。

由定义知：如果G是优美图，则V(G)→{0,1,2,…,|E|}是一个单射；E(G)→{1,2,…,|E|}是一个双射。

① 当n为偶数时，n=2s=a，b=n-1，

令f(x0)=0，f(x1)=s，

令f(yj)=

f(ya)=2s；

令f(z1)=s-1，f(z2)=4n-s-3，

f(zk)=

其中，f(z3)=f(z2)-(2s-1)=4n-3s-2

=2n+s-2，

f(z4)=f(z3)+(2s-2)=

f(z2)-(2s-1)+(2s-2)=f(z2)-1,

f(z5)=f(z4)-(2s-3)=f(z2)-(2s-2),

f(zn)=f(zn-1)+1；

(i)由于f(x0)

f′(x0x1)=s，f′(x1x2)=5n-s-3，f′(xixi+1)=4n-i-2(i=2,3,…,n-1)，

f′(yjyj+1)=3n-j-3(j=1,2,3,…,n-2)，

f′(x0yj)=

f′(x0ya)=2s=n

f′(yn-2yn-1)=2n-1；

f′(z1z2)=4n-s-3-(s-1)=3n-2，

f′(zkzk+1)=

其中f′(zn-1zn)=1，从而

f′(zn-1zn)

f′(x0x1)

f′(x0ya)

f′(x2x3)

f′(yn-2yn-1)

f′(yn-1yn)

…

f′(x0y1)

f′(x0xa-2)<…

②当n为奇数时，n=2s+1=a+1，n=b，

令f(x0)=0，f(x1)=s，

令f(yj)=

令f(z1)=4n-s-4，f(z2)=s-1，f(z3)=2n+s-2,

f(zk)=

其中，f(z4)=f(z3)+(2s-1)=2n+3s-3，

f(z5)=f(z3)+1,f(z6)=f(z3)+2s-2,

f(zn)=f(zn-1)-1；

(i)由于f(x0)

f′(x0yj)=

f′(x0yb)=f′(x0yn)=2s,f′(yayb)=5n-4s-3,

f′(yjyj+1)=3n-j-2(j=2,3,…,n-2)，

其中f′(x0y1)=n+s，f′(x0ya)=5n-2s-3，

f′(y1y2)=4n-2s+4，f′(yn-2yn-1)=2n；

f′(z1z2)=4n-2s-3，f′(z2z3)=2n-1,

f′(zkzk+1)=

这就是《老人与海》最富哲理的人物语言，也是小说想要揭示的主题。主人公桑提亚哥很“背运”，连续84天没有捕到鱼。他是“背运”，但他不屈服，努力战胜困难，他是一个胜利者，一个敢于挑战自己的胜利者。

图1 优美标号

① 当n为偶数时，n=2s=a，b=n-1，

令f(x0)=0，

其中，f(xa)=5n-1-s，f(xb)=2n-s-1

令f(yj)=

其中，f(yb)=4n-1，f(ya)=2n-1；

令f(z0)=4n-2,f(z1)=n-1，f(zk)=3n+k-3,k=2,3,…,n。

f′(xixi+1)=4n-i-1(i=1,2,3,…,n-1)，

f′(yjyj+1)=3n-j-1(j=1,2,3,…,n-1)，

f′(x0yj)=

f′(z0z1)=3n-1，f′(z0zk)=n-k+1，(k=2,3,…,n)

从而

f′(z0zn)

② 当n为奇数时，n=2s+1=a+1，n=b，

令f(x0)=0，f(x1)=1，f(x2)=5n-2，

其中，f(xa)=n+s-3，f(xb)=4n+s-2；

令

其中，f(ya)=4n-2，f(yb-2)=2n-3，

其中，f(zn)=f(zb)=4n-b；

(i)由于f(x0)

f′(x0x1)=1，f′(x1x2)=5n-3，f′(x2x3)=2，

f′(xixi+1)=4n-i(i=3,…,n-1)，

其中，f′(x0yb)=f′(x0yn)=2n；

f′(yjyj+1)=3n-j-1 (j=1,2,3,…,n-2)，f′(yn-1yn)=2n-2；

从而

图2 优美标号

参考文献：

[1]MA K J. Graceful graph [M]. Beijing：Peking University Press, 1991．

[2]ACHARYA B D，HEGED S M. Arithmetic graphs[J].J Gragh Theory, 1990, 14(3):275-299.

[3]MARTIN GARDNER. Mathematical games [J]. Scientific American, 1972, 22(6): 625-645.

[4]ECKIER A R. The construction of missile guidance codes resistant to random interference [J]. Bell Syst Technical J, 1960, 39: 973-994.

[5]刘瑞芹，张昆龙．非连通并图的优美标号研究[J]．合肥工业大学学报：自然科学版, 2009, 32(6): 940-944．

[7]王涛，李德明．和轮相关图的优美性[J]. 中山大学学报：自然科学版, 2011, 50(6): 16-19．

[9]魏丽侠，贾治中．非连通图G1 UG2及G1 UG2 UK2的优美性[J]. 应用数学学报, 2005, 28(4): 689-694．