偶一致超图划分问题的若干结果

鄢仁政

(福建江夏学院数理教研部,福建福州350108)

偶一致超图划分问题的若干结果

鄢仁政

(福建江夏学院数理教研部,福建福州350108)

划分问题因其在多个领域的重要应用一直是图论的研究热点.利用张量的特征值研究超图的划分与奇划分,并结合边割的界给出最大奇割、平均最小割、等周数等超图拓扑指标的界.当k取2时,这些结果与对应的图谱理论中的经典结论一致,因此可视为这些结论在超图的推广.

超图;划分;张量;特征值

1 引言

本文只考虑有限的简单超图,记为H=(V,E),其中V={1,2,···,n}为顶点集, E={e1,e2,···,em}为边集.若∀i=1,···,m均有称H为k一致超图,简称k-超图.当k为偶数时,k-超图也称为偶一致超图.下文总假定k为偶数,当k=2时, 2-超图称为图,总用G表示.本文未说明的记号可参考文献[1].

划分问题是图论中的一个研究热点,在集成电路设计、数模转换、元件布局等领域都有重要的应用[24],而其计算多数是NP-困难或NP-完全的[5],因此关于划分问题的上下界的研究是重要且有实践意义的.图的划分问题可表述为:确定图G顶点集的一个划分使得其边割满足某种特定性质取极值,这样的性质可以是最大割、平均最小割或等周性等.

超图是图论中的一个重要研究分支,相关研究内容丰富[67].本文对超图定义奇划分,利用Laplacian张量的特征值研究超图的划分与奇划分,并结合边割的界给出最大奇割、平均最小割和等周数的界,这些结果当k=2时就是图谱理论中关于最大割、平均最小割和等周数的经典结论,因此可视为这些图的结论在超图的推广.

2 预备知识

定义2.1[8]对k阶n维的实张量T=(ti1··ik),向量定义

显然,Txk是一个实数.而其第i个分量定义为:

定义2.2[910]设T是k阶n维的实张量,若∃λ∈R,x∈Rn{0},满足

则称λ是T的一个H-特征值,非零向量x是对应于λ的H-特征向量.

假设,k-超图H的顶点数为n,其邻接张量A(H)=(ai1i2··ik)的元素定义为:如果{i1i2···ik}∈E,则如果=0.显然, A(H)是k阶n维的实对称张量.H的度对角张量D(H)是指对角元Di··i取顶点i的度,其余元素均为0的张量.超图的Laplacian张量目前有不止一种的定义形式[1112],而下面这个定义从图的角度看是最自然的.

定义2.3[11]设k-超图H的顶点数为n,则称(D−A)是其Laplacian张量,记为L(H).

引理2.1[11]设k-超图H的顶点数为n,Laplacian张量为L,其最大H-特征值为λmax(L),则

引理2.2[13]设k-超图H的顶点数为n,邻接张量为A,则

其中xe=xi1xi2···xik,若e=

3 主要结果

定义3.1超图H顶点集的一个划分V(H)=S∪¯S,若其边割

这里的max是取遍H的奇划分,称Moc(H)是H的最大奇割.

超图的奇划分总是存在的:任取H的一个顶点记为S0,则δS0的每条边与S0关联的顶点数恰为1,因此是H的一个奇划分.并且当k=2时,超图的奇划分定义与图的划分定义等价,最大奇割与图的最大割定义等价.

定理3.1设H是n个顶点,m条边的k-超图,L是其Laplacian张量,V(H)=S∪¯S是H任意的奇划分,则

证明设若i∈¯S.A是图H的邻接张量,由引理2.2,可得

因为

所以

又因为向量x满足

推论3.1设H是n个顶点的k-超图,则其最大奇割满足:

证明设就是H的满足|δS|最大的奇划分,即

当k=2时,推论3.1与文献[14]给出的图最大割的如下结果一致:

这里的min是取遍Rn+中的向量x,文献[11]定义

并将α′(H)称为H的代数连通度.认为将α(H)=2α′(H)称为k-超图H的代数连通度更合适,理由可见下面的定理3.2和定理3.3.

引理3.1[11]k-超图H连通的充要条件是α(H)>0.

引理3.2[11]设H是n个顶点的k-超图,S是V(H)的非空真子集,则

称为点集S的边密度.

定理3.2设H是n个顶点的k-超图,则

证明设S0⊂V(H)就是H的满足ρc(S)最小的非空点集,即ρc(S0)=γ(H).由引理3.2,可得

命题成立.

当k=2时,定理3.2与图的平均最小割的如下经典结论[15]一致:

n个顶点的k-超图H的等周数定义为:

图的等周数已有大量的研究[1617],这里考虑k-超图的等周数.

定理3.3设H是n个顶点的k-超图,则

证明∀S⊂V(H),若则由引理3.2,可得

由i(H)的定义可知命题成立.

当k=2时,定理3.3与文献[16]给出的图等周数的如下结果一致:

参考文献

[1]贝尔热C.超图[M].南京:东南大学出版社,2002.

[2]Lengauer T.Combinatorial Algorithms for Integrated Circuit Layout[M].New York:J.Wiley,1990.

[3]Bhatt S N,Leighton F T.A framework for solving VLSI graph layout problems[J].Journal of Computer and System Sciences,1984,28(2):300-343.

[4]Nesetril J,Poljak S.A remark on max-cut problem with an application to digital-analogue convertors[J]. Oper.Res.Lett.,1986,4(6):289-291.

[5]Garey M R,Johnson D S,Stockmeyer L.Some simpli fi ed NP-complete graph problems[J].Theoretical Computer Science,1976,1(3):237-267.

[6]郑国彪.D-完全一致混合超图不可着色的一个充要条件[J].纯粹数学与应用数学,2011,27(3):308-312.

[7]郑国彪.关于D-完全一致混合超图上色数的一个结论的推广[J].纯粹数学与应用数学,2012,28(3):294-302.

[8]Ko fi dis E,Regalia P A.On the best rank-1 approximation of higher-order supersymmetric tensors[J].SIAM J.Matrix Anal.Appl.,2002,23(3):863-884.

[9]Qi L.Eigenvalues of a real supersymmetric tensor[J].J.Symb.Comput.,2005,40(6):1302-1324.

[10]Lim L H.Singular values and eigenvalues of tensors:a variational approach[J].Proceedings of the IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing,2005,1:129-132.

[11]Qi L.H+-eigenvalues of Laplacian and signless Laplacian tensors[J].Communications in Mathematical Sciences,2013,13:2186-2192.

[12]Xie J,Chang A.A new tpye of Laplacian tensor and its Z-eigenvalues of an even uniform hypergraph[J]. Int.J.Appl.Math.Stat.,2013,31(1):9-19.

[13]Cooper J,Dutle A.Spectra of uniform hypergraphs[J].Linear Algebra Appl.,2012,436(9):3268-3292.

[14]Mohar B,Poljak S.Eigenvalues and the max-cut problem[J].Czech.Math.J.,1990,40(2):343-352.

[15]Mohar B.Laplace eigenvalues of graphs-a survey[J].Discrete Math.,1992,109:171-183.

[16]Mohar B.Isoperimetric numbers of graphs[J].J.Combin.Theory,Ser.B,1989,47(3):274-291.

[17]Kahale N.Isoperimetric inequalities and eigenvalues[J].SIAM J.Discrete Math.,1997,10(1):30-40.

Some results on partition problems of even uniform hypergraphs

Yan Renzheng

(Department of Mathematics and Physics,Fujian Jiangxia University,Fuzhou350108,China)

Because of the widespread applications in many fi elds,partition problems play an important role in graph theory.We study partition and odd-partition problems of hypergraphs by eigenvalues of the Laplacian tensor.Joined with the bound for cardinality of edge cuts,we introduce some bounds for max-odd-cut,averaged minimal cut and isoperimetric number of hypergraphs.These bounds generalize,to the case of hypergraphs, some classical results in spectral graph theory.

hypergraph,partition,tensor,eigenvalue

O157.5

A

1008-5513(2014)01-0040-05

10.3969/j.issn.1008-5513.2014.01.007

2013-11-20.

福建省中青年教师教育科研项目(JB13194).

鄢仁政(1980-),硕士,讲师,研究方向：图论及其应用.

2010 MSC:05C65