0 引 言

在当今图论学科中，图的标号是相当活跃的一个分支，这是因为它有很广泛的应用，诸如：编码理论、雷达、通讯网络、射电天文学等方面^[1~4]．文献^[5]给出了著名的优美树猜想：每一棵树都有一个优美标号．如果这个猜想被解决，人们就可以解决著名的Ringel-Kotzig分解猜想：对预先给定的一棵n+1个顶点的树T,每一个2n+1个顶点的完全图K_2n+1都可被分解成2n+1个同构于树T的子图．到目前为止，优美树猜想仍然没有被完全解决，这使得优美树猜想至今仍然是一个吸引人解决的问题，由于不断地对这个猜想进行研究、实验、进攻，导致了各种图的标号与着色技术迅速发展^[6~8]．本文论及的图均为简单、无向图．为了便于叙述，引入记号［1,m］(m≥1)表示由1与m之间的自然数构成的集合，未说明的相关术语和符号均采用于文献^[9]．

定义1 设G是有n个顶点的简单图，如果存在映射f:V(G)→{0,1,…,|E(G)|}，使对不同的顶点x,y∈V(G)，满足f(x)≠f(y)，G的每一条边uv的标号定义为f(uv)=|f(u)－f(v)|，且G的边标号互不相同，则称G是优美图，f是G的一个优美标号．

定义2 如果一棵具有n个顶点且有完美匹配M的树T有一个优美标号f，使对每条边uv∈M,总有f(u)+f(v)=n－1，则称T是强优美树，f是T的一个强优美标号．设T的顶点二部划分为(X,Y)，若对任意的x∈X,y∈Y,都有f(x)<f(y)，不妨记作f(X)<f(Y)，则称T是集有序强优美树，f是T的一个集有序强优美标号．

定义3 设G是有p个顶点q条边的(p,q)-图，如果存在一个映射f:V(G)→［0,k+(q－1)d］，使得边标号集合

称f是图G的一个(k,d)-优美标号．如果G有完美匹配M和一个(k,d)-优美标号f，使得对每条边uv∈M,总有f(u)+f(v)=k+(q－1)d，则称G是(k,d)-强优美图，f是G的一个(k,d)-强优美标号．若G是具有顶点二部划分(X,Y)的二分图，且对任意的x∈X,y∈Y,都有f(x)<f(y)，不妨记作f(X)<f(Y)，则称G是集有序(k,d)-强优美图，f是G的一个集有序(k,d)-强优美标号．

在本文的研究中需用到一个原则，即：将一棵强优美树T的顶点集合V(T)在属于它的任意强优美标号f下划分为两个集合V(X)与V(Y)，T=(X,Y)，对任意的x∈X,y∈Y,都有f(x)<f(y)，不妨记作f(X)<f(Y)，称这种划分为顶点标号二部划分原则．我们先将下文中将要用到的记号做一说明，H=〈T_i1,T_i2,…,T_in〉表示T_i1⊕T_i2⊕…⊕T_in，其中T_i1⊕T_i2表示在顶点x_i1max与顶点y_i2max之间用一条边连接所形成的树(f是T_i1的一个集有序强优美标号，T_i1=(X_i1,Y_i1)，x_i1max∈X_i1，对任意的u∈Xi1且u≠x_i1max，有f(u)<f(x_i1max)；g是T_i2的一个集有序强优美标号，T_i2=(X_i2,Y_i2)，y_i2max∈Yi2，对任意的v∈Y_i2且v≠y_i2max，有f(v)<f(y_i2max))．由于1,2,…,n这n个数的全排列数为n!，那么我们就可以用这n个集有序强优美树T₁,T₂,…,T_n做成基，生成n!个树(包括同构)．形象地看是将一条长为n的路通过将每个顶点x_j换成树T_ij扩展成一个庞大的复杂的树，因此称这n!个树构成了一个线性图空间．

1 定理及其证明

定理1 n个集有序强优美树T₁,T₂,…,T_n构成的线性图空间中每一棵树均为集有序强优美树．

由于在这个线性图空间中每一棵树的任意性及树的个数n的任意性使得定理1的证明比较复杂，为此我们先看一个特殊情形，如下：

定理2 T,T′是两个二分强优美树，那么树H=〈T,T′〉也是二分强优美树．

证 针对树T与树T′的阶数与结构差异性，证明分三类.

第一类：若T,T′是两个同构的强优美树(见例1)，且|V(T)|=|V(T′)|=2n，给强优美树T一个强优美标号f及完美匹配R₁，使得T=(X,Y)，对任意的x∈X,y∈Y,都有f(x)<f(y)，不妨记作f(X)<f(Y)，边uv∈R₁，都有f(u)+f(v)=2n－1，且；给二分强优美树T′一个二分强优美标号f′及完美匹配R²，使得T′=(X′,Y′)，对任意的x′∈X′,y′∈Y′,都有f′(x′)<f′(y′)，不妨记作f′(X′)<f′(Y′)，边u′v′∈R²，都有f′(u′)+f′(v′)=2n－1，且

对任意的u∈V(T)，存在u′∈V(T′)，使得f(u)=f′(u′)，在u与u′间连一条边，得到的树记为树H=〈T,T′〉，下证树H是二分强优美的．依二分强优美标号f与f′给树H=〈T,T′〉=(X∪Y′,Y∪X′)=(M,N)定义一个新的标号g：

显然，对任意的x∈M,y∈N,都有f(x)<f(y)，且,顶点标号集合g(V(H))=［0,4n－1］．在树H中子树T的边标号集合G₁满足

在树H中子树T′的边标号集合G₂满足

边uu′的标号g(uu′)=|g(u′)－g(u)|=2n，则得树H的边标号集合

任意的边uv∈R(R=R₁∪R²为树H的完美匹配)满足g(u)+g(v)=4n－1．从而，树H是二分强优美树，g是树H的一个二分强优美标号．

第二类：若T,T′是两个不同构的二分强优美树，但|V(T)|=|V(T′)|=2n，证明方法与第一类的类似．

第三类：若T,T′是两个二分强优美树且|V(T)|≠|V(T′)|(见例2)，不妨设2n=|V(T)|>2m=|V(T′)|，给二分强优美树T一个二分强优美标号f及完美匹配R₁，使得T=(X,Y)，对任意的x∈X,y∈Y,都有f(x)<f(y)，不妨记作f(X)<f(Y)，边uv∈R₁，都有f(u)+f(v)=2n－1且；给二分强优美树T′一个二分强优美标号f′及完美匹配R²，使得T′=(X′,Y′)，对任意的x′∈X′,y′∈Y′,都有f′(x′)<f′(y′)，不妨记作f′(X′)f′(Y′)，边u′v′∈R²，都有f′(u′)+f′(v′)=2m－1且.

1) 当n≥2m时，对任意的u′∈Y′，存在v∈X，使得f(v)－f′(u′)=n－2m，或者对任意的u′∈X′，存在v∈Y,使得f(v)－f′(u′)=n，在顶点v与顶点u′间连一条边，得到的树记为H₁=〈T,T′〉；

2) 当m<n<2m时，对任意的u′∈Y′，存在v∈X，使得f′(u′)－f(v)=2m－n，或者对任意的u′∈X′，存在v∈Y,使得f(v)－f′(u′)=n，在顶点v与顶点u′间连一条边，得到的树记为H₂=〈T,T′〉．

下证树H₁与树H₂是集有序强优美的，仅证树H₁是集有序强优美的，这是因为树H₂的证明与树H₁的证明相同．依集有序强优美标号f与f′，给树H₁=〈T,T′〉=(X∪Y′,Y∪X′)=(M,N)定义一个新的标号g为

显然，对任意的x∈M,y∈N,都有f(x)<f(y)，且,顶点集合g(V(H))=［0,2(n+m)－1］．在树H₁中，子树T的边标号集合G₁为

在树H₁中，子树T′的边标号集合G₂为

边uu′的标号g(uu′)=|g(u′)－g(u)|=2m，可算出树H₁的边标号集合为

且对任意的边uv∈R(R=R₁∪R²为树H的完美匹配),都有g(u)+g(v)=2(n+m)－1，从而树H₁是集有序强优美的，g是树H₁的一个集有序强优美标号．至此，定理2证毕．

例1 集有序强优美树T与同构的集有序强优美树T′产生新的集有序强优美树(如图 1)．

例2 二分强优美树T与二分强优美树T₁产生新的二分强优美树(如图 2)．

再证定理1，对n个集有序强优美树T₁,T₂,…,T_n的任意一个有序排列T_i1,T_i2,…,T_in，可以两两组合采用定理2证明中的构造法产生新的集有序强优美树，以此类推便可构造出一族树T={〈T_i1,T_i2,…,T_in〉|i1,i2,…,in是1,2,…,n的一个有序排列}，显然，T中的每个树都是二分强优美树．这样我们可以看到定理1中的线性图空间仅是树族T的一个类．

推论1 T,T′是两个二分强优美树，那么树H=〈T,T′〉是二分(k,d)-强优美树．

证 依据定理2中树H=（M,N）的标号g作一个新的标号τ：对任意的u∈M，有τ（u）=g（u）d；对任意的v∈N，有τ（v）=k+（g（v）－1）d．显然，顶点标号集合τ（V（H））=［0,k+（|E（H)|－1）d］，边标号集合

且任意的边uv∈R(R=R₁∪R²为树H的完美匹配)，都有

则标号τ是树H的一个(k,d)-强优美标号，树H是(k,d)-强优美树．根据构造法易知在H=〈T,T′〉=(X∪Y′,Y∪X′)=(M,N)中对任意的x∈M,y∈N,都有f(x)<f(y)，且，那么标号τ就是树H的一个集有序(k,d)-强优美标号，树H就是集有序(k,d)-强优美树．

在推论1中，当k=1,d=1时，标号τ就是集有序强优美标号；当k=1,d=2时，标号τ就是集有序强奇优美标号．定理1给了我们一种用若干个小的集有序强优美树构造出大的集有序强优美树的方法，用此方法我们证明了一族树的集有序强优美性，是否能将条件弱化产生新的结论呢？通过实验可以作出一些改进，便有如下定理3．

定理3 T₁,T′₁,T₂,T′₂,…,T_n,T′_n是2n个强优美树且T_i与T′_i(i∈［1,n］)同构，H_i=〈T₁,T′₁〉,则对任意的一个排列H_i1,H_i2,…,H_in，树H=〈H_i1,H_i2,…,H_in〉是强优美树．

由于树T的任意性及树的个数n的任意性使得定理3的证明更加复杂，为顺利完成定理3的证明，我们先证明一个特殊情形，如下：

定理 4 T,T′是两个同构的强优美树，那么树H=〈T,T′〉是强优美树．

证 T,T′是两个同构的强优美树且|V(T)|=|V(T′)|=2n，依顶点标号二部划分原则给强优美树T一个强优美标号f及完美匹配R₁，使得T=(X,Y)，对任意的x∈X,y∈Y,都有f(x)<f(y)，不妨记作f(X)<f(Y)，边uv∈R₁，都有f(u)+f(v)=2n－1，同理给强优美树T′一个强优美标号f′及完美匹配R²，对任意的x′∈X′,y′∈Y′,都有f′(x′)<f′(y′)，不妨记作f′(X′)<f′(Y′)，边u′v′∈R²，都有f′(u′)+f′(v′)=2m－1，且．对任意的x∈V(T)，存在x′∈V(T′)，使得f(x)=f′(x′)，在x与x′间连一条边，得到的树记为树H=〈T,T′〉．依强优美标号f与f′给树H=〈T,T′〉=(X∪Y′,Y∪X′)=(M,N) 定义一个新的标号g：

显然，对任意的x∈M,y∈N,都有f(x)<f(y)，且,顶点标号集合g(V(H))=［0,4n－1］．在子树T中依点标号为0的顶点为初始点做二部划分，在子树T′中依点标号为2n－1的顶点为初始点做二部划分，T=(X^*,Y^*)，存在s∈X^*，使g(s)=0；T′=(X′^*,Y′^*)，存在s′∈X^*，使g(s′)=2n－1．将不符合二部划分原则的同构点的标号互换(T:u∈X^*,v∈Y^*,α=g(u)>g(v)=β且g(u)+g(v)=4n－1；T′:u′∈X′^*,v′∈Y′^*, λ=g(u′)>g(v′)=γ,且g(u′)+g(v′)=4n－1；g(u)=λ，g(v)=γ，g(u′)=α，g(v′)=β).至此,标号完成.

下证树H是强优美的．标号过程中我们会发现这样一个现象，在发生同构点的标号互换之后，树H的边标号仅仅改变的是连接初始互换标号顶点(如连接顶点u,u′)边的边标号，这些边标号作成的集合记G₁：G₁=G′₁∪G″₁(其中G′₁表示原来在子树T上的点标号互换给子树T′上的同构点后边标号产生改变的集合，

(u是初始互换标号的顶点，w是未互换标号的顶点)G″₁表示原来在子树T′上的点标号互换到子树T上的同构点后边标号产生改变的集合，G″₁={g(uw)|g(uw)=2n+(u′w′),u′,w′∈V(T′),u′v′∈E(T′);u,w∈V(T),uv′∈E(T)}(u′是初始互换标号的顶点，w′是未互换标号的顶点))．未发生同构点的标号互换之前树H中子树T的边标号集合G₂=G′₂∪G″₂,其中，

树H中子树T′的边标号集合G₃=G′₃∪G″₃,其中，

边xx′的标号g(xx′)=|g(x′)－g(x)|=2n，那么最终树H的边标号集合

显然,对任意的x∈M,y∈N,都有f(x)<f（y），且, 顶点标号集合g（V（H））=[0,4n－1]，从而树H是强优美树，g是树H的一个强优美标号．

至此，定理4证毕．

再述定理3，对于T₁,T′₁,T₂,T′₂,…,T_n,T′_n这2n个强优美树，先将T_i与T′_i采用定理4证明中的构造法构造产生新的强优美树H_i，然后两两组合，以此类推便可构造出强优美树H=〈H_i1,H_i2,…,H_in〉．

推论2 T是个二分强优美树，T′是个强优美树，|V（T）|≥|V（T′）|，那么树H=〈T,T′〉是强优美树．

证 由于T是二分强优美树，T′是强优美树，且有2n=|V（T）|≥|V（T′）|=2m，则二分强优美树T有一个二分强优美标号f，使得T=（X,Y），对任意的x∈X, y∈Y, 都有f（x）<f（y），不妨记作f（X）<f（Y），边uv∈R₁，都有f（u）+f（v）=2n－1，且；依顶点标号二部划分原则给强优美树T′一个强优美标号f′，使T′=（X′,Y′），对任意的x′∈X′, y′∈Y′, 都有f′（x′）<f′（y′），不妨记作f′（X′）<f′（Y′），边u′v′∈R₂，都有f′（u′）+f′（v′）=2m－1，且．

1） 若n≥2m，任意的u′∈Y′，存在v∈X，使得f（v）－f′（u′）=n－2m或任意的u′∈X′，存在v∈Y, 使得f（v）－f′（u′）=n，在顶点v与顶点u′间连一条边，得到的树记为树H₁=〈T,T′〉；

2） 若m≤n<2m，任意的u′∈Y′，存在v∈X，使得f′（u′）－f（v）=2m－n或任意的u′∈X′，存在v∈Y, 使得f（v）－f′（u′）=n，在顶点v与顶点u′间连一条边，得到的树记为树H₂=〈T,T′〉．

下证树H₁是强优美的，树H₂是强优美的证明类似．依强优美标号f与f′给树H₁=〈T,T′〉=（X∪Y′,Y∪X′）=（M,N）定义一个新的标号g：

显然，对任意的x∈M，y∈N, 都有f（x）<f（y），且, 顶点标号集合g（V（H））=[0,2（n+m）－1]．在树H₁中子树T的边标号集合：

在树H中子树T′的边标号集合：

边vu′的标号g（vu′）=|g（u′）－g（v）|=2m，既而树H₁的边标号集合

, 从而树H₁是强优美树，g是树H₁的一个强优美标号．至此，推论3证毕．

推论3 T是个二分强优美树，T′是个强优美树，|V（T）|≤|V（T′）|，那么树H=〈T,T′〉是强优美树．

证 T是个二分强优美树，T′是个强优美树，不妨设2n=|V（T）|≤|V（T′）|=2m, 给二分强优美树T一个二分强优美标号f，使得T=（X,Y），对任意的x∈X, y∈Y, 都有f（x）<f（y），不妨记作f（X）<f（Y），边uv∈R₁，都有f（u）+f（v）=2n－1，且；依顶点标号二部划分原则给强优美树T′一个强优美标号f′，使得T′=（X′,Y′），对任意的x′∈X′, y′∈Y′, 都有f′（x′）<f′（y′）.

不妨记作f′（X′）<f′（Y′），边u′v′∈R₂，都有f′（u′）+f′（v′）=2m－1，且．

1） 当m≥2n时，任意的u′∈Y′，存在v∈X，使得f（v）－f′（u′）=n－2m或任意的u′∈X′，存在v∈Y, 使得f（v）－f′（u′）=n，在顶点v与顶点u′间连一条边，得到的树记为树H₁=〈T,T′〉；

2） 当n<m<2n时，任意的v∈X，存在u′∈Y′，使得f′（u′）－f（v）=2m－n或任意的v∈Y，存在u′∈X′, 使得f（v）－f′（u′）=n，在顶点v与顶点u′间连一条边，得到的树记为树H₂=〈T,T′〉．

下证树H₁是强优美的，树H₂是强优美的证明类似．依强优美标号f与f′给树H₁=〈T,T′〉=（

∪Y′,∪X′）=（M,N）定义一个新的标号：

显然，对任意的x∈M, y∈N, 都有f（x）<f（y），且, 顶点集合g（V（H））=[0,2（n+m）－1]．在树H₁中子树T的边标号集合：

在树H₁中子树T′的边标号集合：

边vu′的标号g（vu′）=|g（u′）－g（v）|=2m，既而树H₁的边标号集合G=G₁∪G₂∪{g（uu′)}=[1,2（n+m）－1], 推出树H₁是强优美树，g是树H₁的一个强优美标号．至此，推论3证毕．

推论2和3说明给出一种用二分强优美树与强优美树构造产生新的强优美树的方法，能否再将此条件弱化呢？便有如下的问题．

问题 两个强优美树T₁,T₂可以产生新的强优美树．

本文主要研究了一类图空间的集有序强优美性，在研究中创造性地提出一些独特的构造证明方法，这对以后进攻新的问题^[10~12]有较大的帮助，同时也发现了新的问题，为以后深入地研究指明了方向．