偶一致超圖劃分問題的若干結果

鄢仁政

(福建江夏學院數理教研部,福建福州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