非连通图及的优美性*

2014-03-23 06:41孙彩云
关键词:胜利者标号奇数

孙彩云, 王 涛

(华北科技学院,河北 三河 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.

猜你喜欢
胜利者标号奇数
奇数凑20
奇数与偶数
Chapter 2 A cheerful chat
三条路的笛卡尔乘积图的L(1,2)-标号数
关于奇数阶二元子集的分离序列
几种叉积图的平衡指标集
哲 理漫 画
基于路P8m+4t+2的交错标号的图S(4m+1,4(t+1),4m-1)的优美标号*
胜利者和失败者
奇偶性 问题