(1.厦门大学嘉庚学院信息科学与技术学院,福建 漳州 363105; 2.厦门理工学院应用数学学院,福建 厦门 361024)
(1.School of Information Science and Technology,Xiamen University Tan Kah Kee College,Zhangzhou 363105,China; 2.College of Applied Mathematics,Xiamen University of Technology,Xiamen 361024,China)
uniform supertrees; adjacency tensor; Z-eigenvalues; Z-spectral radius
DOI: 10.6043/j.issn.0438-0479.201806020
备注
设T是任意给定的r一致超树,ρsub>Z(T)是T的邻接张量的Z-谱半径.证明了当r≥3时,ρ/sub>Z(T)=r1-r/2.
Let T be an r-uniform supertree,and ρ/sub>Z(T)be the Z-spectral radius of the adjacency tensor of T. We show that ρ/sub>Z(T)=r1-r/2 with r≥3.
引言
1 预备知识
图谱理论是图论中的一个主要研究内容[1].从2005年Qi[2]和Lim[3]分别独立引入张量的特征值概念后,这一新兴概念立刻引起了国内外多个学科领域学者的重视,并随之在网络与控制、信息技术、生物学和数学等不同学科领域得到了实际应用[4].与矩阵在图谱理论研究中的作用相同,张量成为超图谱理论研究的一个有效工具[5].随着张量特征值理论的不断完善,张量逐渐成为研究超图谱理论的一种有效工具,利用张量特征值理论和方法研究超图及其结构,已经成为图与超图谱理论中的热点方向.
本文中所讨论的超图均为无重边连通超图.设H=(V,E)是一个超图[6],顶点集V=[n]:={1,2,…,n},边集E={e1,e2,…,em},其中ei[n].若H的任意超边ei∈E均满足|ei|=r,称H为r一致超图.若H的任意超边ei≠ej均满足|ei∩ej|≤1,称H为线性超图.若r一致线性超图是无圈的[6],记作T,称T为r一致超树.定义张量A的谱半径ρ(A):=max{|λ|:λ是A的特征值}.T的邻接张量的H-谱半径和Z-谱半径分别为ρH(T)和ρ<sub>Z(T).Li等[7]首先引入超图的移边操作和释边操作等定义,讨论了r≥2时任意T的邻接张量H-谱半径的上下界及其对应的极值图类,即ρH(Prn)≤ρH(T)≤ρH(Srn).目前关于超图Z-谱半径的研究相对较少,超树是超图研究中的一个重要超图类,本文中从r一致超树出发,参考移边运算和释边运算的定义及方法[7],讨论r一致超树T的邻接张量的Z-谱半径ρ</sub>Z(T). 显然r=2时,T为普通树图,ρ(T)是该树的邻接矩阵谱半径,有ρ</sub>Z(T)=ρ(T)=ρH(T).为了得到更一般的结论,本文中给出了r≥3时,任意r一致超树T的邻接张量的Z-谱半径公式:ρ</sub>Z(T)=r1-r/2.
2 相关定义定理
2.1 一些基本定义和引理定义1[5] 对n个顶点的r一致超图H=(V,E),定义H的邻接张量为一个r阶n维非负对称张量A=(ai1i2…ir):
ai1i2…ir:={1/((r-1)!),{i1,i2,…,ir}∈E,
0, {i1,i2,…,ir}E.
定义2[5] x是任意实向量,对给定的r一致超图H及对应的邻接张量A,定义一个实数
Axr:=∑i1,i2,…,irai1i2…irxi1xi2…xir=
r∑{i1,i2,…,ir}∈Exi1xi2…xir.
若任意e={i1,i2,…,ir}∈E,记xe=xi1xi2…xir,则Axr=r∑e∈Exe.
定义3[2] 对r阶n维张量A,若存在λ∈R和x∈Rn\0满足如下方程组:
{Axr-1=λx,
xTx=1,
其中Axr-1表示向量,则称λ为张量A的Z-特征值,x为λ对应的一个Z-特征向量.
定义4[8] λ是张量A的任意Z-特征值,定义张量A的Z-谱半径:
ρ</sub>Z(A):=max{|λ|:λ是A的Z-特征值},
特别的,A是H对应的邻接张量,记H的邻接张量的Z-谱半径为ρ</sub>Z(H):≡ρ</sub>Z(A).
引理1[9] r一致超图H对应的邻接张量A是弱对称张量,且满足
ρ</sub>Z(H)=max{λ:λ是A的Z-特征值}=
max{Axr:x∈Rn+,xTx=1}.
在r一致超图H=(V,E)中,度数为1的顶点称为悬挂点; 若e∈E包含r-1个悬挂点,则称e为悬挂边; 否则称e为非悬挂边.
引理2 [7] r一致超树T的边数和顶点数满足m=(n-1)/(r-1).
定义5[10] 对任意超图H=(V,E),u,v∈V,若交换H中u,v两个顶点的位置,没有改变H中任意顶点之间的邻接关系,则称u和v是等价的,记作u~v.
引理3[10] H是r一致线性超图,x是H的任意邻接张量的Z-特征向量,若u~v,则xu=xv.
引理4[11] G是H的任意子图,则有ρ</sub>Z(G)≤ρ</sub>Z(H).
2.2 移边运算和释边运算的定义定义6[7] 设k>1,H=(V,E)是一个超图,u∈V,e1,e2,…,ek是E中不包含u的k条超边,对任意vi∈ei,i∈[k],记e'i={ei\{vi}}∪u,H'是在H中删除ei并添加e'i得到的新超图,即H'=(V',E'),其中V'=V,E'=(E\{e1,e2,…,ek})∪{e'1,e2,…,e'k}.我们称H'是通过H把超边(e1,e2,…,ek)从(v1,v2,…,vk)移动到u得到的超图,简称为超图的移边运算.
注:(i)v1,v2,…,vk中的顶点可以相同,即允许某些顶点重复出现.
(ii)一般来说,超图H'可能包含重边,如果H是无圈的且存在一条超边包含u,v1,v2,…,vk这些顶点,则H'没有重边.
定义7[7] H是线性超图,e是H上的一条非悬挂边,u∈e,e1,e2,…,ek是H中与e相交但不包含u的k条超边,记ei∩e=vi,H'是通过H把超边(e1,e2,…,ek)从(v1,v2,…,vk)移动到u得到的超图,则称H'是由H通过释放边e到u上得到的超图.
3 r一致超树的Z-谱半径
本节主要证明r一致超树的邻接张量的Z-谱半径公式,即:
定理1 对任意r一致超树T,若r≥3,则
ρ</sub>Z(T)=r1-r/2.
在证明定理1前,需要先证明几个引理.
引理5 设H=(V,E)是r一致超图,H'=(V',E')是通过H把超边(e1,e2,…,ek)从(v1,v2,…,vk)移动到u得到的超图,且H'没有重边.若对ρ<sub>Z(H)的任意非负邻接张量的Z-特征向量x都有xu≥max1≤i≤k xvi,则
ρ</sub>Z(H')≥ρ</sub>Z(H).
证明 令e'i={ei\{vi}}∪{u},对ρ</sub>Z(H)的任意非负Z-特征向量x,由xu≥max1≤i≤k xvi≥0得到xe'i-xei≥0.由定义3和引理1可得ρ</sub>Z(H)=r∑e∈Exe,ρ</sub>Z(H')≥r∑e∈E'xe,因此ρ</sub>Z(H')-ρ</sub>Z(H)≥r∑e∈E'xe-r∑e∈Exe=r∑1≤i≤k(xe'i-xei)≥0.即ρ</sub>Z(H')≥ρ</sub>Z(H).
引理6 设r一致超树T'是由T通过释放非悬挂边e到v上得到的超图,其中v是e的任意顶点,则
ρ</sub>Z(T')≥ρ</sub>Z(T).
证明 设x是T的任意非负邻接张量的Z-特征向量,则存在u∈e使得xu=maxi∈e{xi},记T″是T通过释放非悬挂边e到u上得到的超树,显然T'和T″是同构的.通过定义7可知,T″是T通过移动与e相交的那些超边到u得到的超图.因此,由引理5可得ρ</sub>Z(T')=ρ</sub>Z(T″)≥ρ</sub>Z(T).
注:引理6说明r一致超树通过释放某条非悬挂边e到e上任意顶点,得到的新r一致超树是同构的,与顶点的选择无关.即对r一致超树,释放某条非悬挂边是把该超边转化为悬挂边.在不发生误解的情况下,以下简称为释边运算.
引理7 设T是n个顶点的r一致超树,则
ρ</sub>Z(T)≤ρ</sub>Z(Srn).
证明 对T中非悬挂边的边数(T)作归纳法:
i)若(T)=0,T中的超边都是悬挂边,即T是r一致超星Srn,结论显然成立;
ii)若(T)≥1,则T至少存在一条非悬挂边,这样总能对T进行一次释边运算使这条非悬挂边转化为悬挂边,记T释边运算后得到的r一致超树为T',则(T')<(T).此外,由引理6可知ρ</sub>Z(T)≤ρ</sub>Z(T'). 由归纳假设可得(T')≥(Srn),ρ</sub>Z(T')≤ρ</sub>Z(Srn).
综合i)和ii),即有ρ</sub>Z(T)≤ρ</sub>Z(Srn).
引理8 对任意n个顶点的r一致超星Srn. 若r≥3,则
ρ</sub>Z(Srn)=r1-r/2.
证明 设Srn的超边集E={e1,e2,…,em},由引理2可知n=m(r-1)+1,令x是ρ</sub>Z(Srn)对应的一个非负Z-特征向量.由引理3可知Srn中属于同一超边的悬挂点特征分量均相等.不妨记Srn的中心顶点对应的特征分量为x0,第i条超边的悬挂点特征分量为xi,由引理1可知ρ</sub>Z(Srn)=r∑e∈Exe=max{rx0(∑1≤i≤mxr-1i)}及x20+(r-1)∑1≤i≤mx2i=1.固定x0,考虑∑1≤i≤mxr-1i在∑1≤i≤mx2i=(1-x20)/(r-1)限制下的最大值.设函数f1(y)=y(r-1)/2是过原点的幂函数,(r-1)/2≥1,对任意yi≥0,都有∑1≤i≤mf1(yi)≤f1(∑1≤i≤myi).取yi=x2i,则有∑1≤i≤mxr-1i≤(∑1≤i≤mx2i)(r-1)/2=((1-x20)/(r-1))(r-1)/2. 设函数f2(x)=rx((1-x2)/(r-1))(r-1)/2,0≤x≤1.令f'2(x)=0,解得x=r-1/2是唯一极大值点,f2(r-1/2)=r1-r/2. 因此
ρ</sub>Z(Srn)=max{rx0(∑1≤i≤mxr-1i)}=
max{rx0((1-x20)/(r-1))(r-1)/2}=r1-r/2.
即有ρ</sub>Z(Srn)=r1-r/2.
定理1的证明 任意非空r一致超树至少包含r个顶点构成的单边超星Srr,即SrrT,由引理4可得ρ</sub>Z(Srr)≤ρ</sub>Z(T). 又由引理7可得ρ<sub>Z(T)≤ρ<sub>Z(Srn). 最后由引理8得到r≥3时,任意r一致超星的邻接张量的Z-谱半径,即ρ</sub>Z(Srr)=ρ</sub>Z(Srn)=r1-r/2. 这样就证明了ρ</sub>Z(T)=r1-r/2.
推论1 对任意n个顶点的r一致超路Prn. 若r≥3,则ρ</sub>Z(Prn)=r1-r/2.
- [1] BROUWER A E,HAEMERS W H.Spectra of graphs[M].Berlin:Springer Science and Business Media,2011:3-9.
- [2] QI L.Eigenvalues of a real supersymmetric tensor[J].J Symb Compute,2005,40:1302-1324.
- [3] LIM L H.Singular values and eigenvalues of tensors:a variational approach[C]∥Proc IEEE International Workshop on Computational Advances in Muli-tensor Adaptive Prcocessing(CAMSAP'05).Puerto Vallarta:IEEE,2005:129-132.
- [4] QI L,YW G,WU E.Higher oder positive semi-definite diffusion tensor imaging[J].SIAM J Imaging Sci,2010,3(3):416-433.
- [5] COOPER J,DUTLE A.Spectra of uniform hypergraphs[J].Linear Algebra Appl,2012,436:3268-3292.
- [6] BERGE C.Hypergraphs,combinatorics of finite sets[M].Amsterdam:Elsevier,1984:1-30.
- [7] LI H,SHAO J,QI L.The extremal spectral radii of k-uniform supertrees[J].J Comb Optim,2016,32:741-764.
- [8] CHANG K C,QI L,ZHANG T.A survey on the spectral theory of nonnegative tensors[J].Numer Linear Algebra Appl,2013,20:891-912.
- [9] CHANG K C,PEARSON K,ZHANG T.Some variational principles of the Z-eigenvalues for nonnegative tensors[J].Linear Algebra Appl,2013,438:416-4182.
- [10] NIKIFOROV V.Analytic methods for uniform hypergraphs[J].Linear Algebra Appl,2014,457:455-535.
- [11] XIE J,CHANG A.On the Z-eigenvalues of the adjacency tensors for uniform hypergraphs[J].Linear Algebra Appl,2013,439:2195-2204.