偶一致超圖劃分問題的若干結(jié)果

鄢仁政

(福建江夏學(xué)院數(shù)理教研部,福建福州350108)

偶一致超圖劃分問題的若干結(jié)果

鄢仁政

(福建江夏學(xué)院數(shù)理教研部,福建福州350108)

劃分問題因其在多個(gè)領(lǐng)域的重要應(yīng)用一直是圖論的研究熱點(diǎn).利用張量的特征值研究超圖的劃分與奇劃分,并結(jié)合邊割的界給出最大奇割、平均最小割、等周數(shù)等超圖拓?fù)渲笜?biāo)的界.當(dāng)k取2時(shí),這些結(jié)果與對(duì)應(yīng)的圖譜理論中的經(jīng)典結(jié)論一致,因此可視為這些結(jié)論在超圖的推廣.

超圖;劃分;張量;特征值

1 引言

本文只考慮有限的簡單超圖,記為H=(V,E),其中V={1,2,···,n}為頂點(diǎn)集, E={e1,e2,···,em}為邊集.若?i=1,···,m均有稱H為k一致超圖,簡稱k-超圖.當(dāng)k為偶數(shù)時(shí),k-超圖也稱為偶一致超圖.下文總假定k為偶數(shù),當(dāng)k=2時(shí), 2-超圖稱為圖,總用G表示.本文未說明的記號(hào)可參考文獻(xiàn)[1].

劃分問題是圖論中的一個(gè)研究熱點(diǎn),在集成電路設(shè)計(jì)、數(shù)模轉(zhuǎn)換、元件布局等領(lǐng)域都有重要的應(yīng)用[24],而其計(jì)算多數(shù)是NP-困難或NP-完全的[5],因此關(guān)于劃分問題的上下界的研究是重要且有實(shí)踐意義的.圖的劃分問題可表述為:確定圖G頂點(diǎn)集的一個(gè)劃分使得其邊割滿足某種特定性質(zhì)取極值,這樣的性質(zhì)可以是最大割、平均最小割或等周性等.

超圖是圖論中的一個(gè)重要研究分支,相關(guān)研究內(nèi)容豐富[67].本文對(duì)超圖定義奇劃分,利用Laplacian張量的特征值研究超圖的劃分與奇劃分,并結(jié)合邊割的界給出最大奇割、平均最小割和等周數(shù)的界,這些結(jié)果當(dāng)k=2時(shí)就是圖譜理論中關(guān)于最大割、平均最小割和等周數(shù)的經(jīng)典結(jié)論,因此可視為這些圖的結(jié)論在超圖的推廣.

2 預(yù)備知識(shí)

定義2.1[8]對(duì)k階n維的實(shí)張量T=(ti1··ik),向量定義

顯然,Txk是一個(gè)實(shí)數(shù).而其第i個(gè)分量定義為:

定義2.2[910]設(shè)T是k階n維的實(shí)張量,若?λ∈R,x∈Rn{0},滿足

則稱λ是T的一個(gè)H-特征值,非零向量x是對(duì)應(yīng)于λ的H-特征向量.

假設(shè),k-超圖H的頂點(diǎn)數(shù)為n,其鄰接張量A(H)=(ai1i2··ik)的元素定義為:如果{i1i2···ik}∈E,則如果=0.顯然, A(H)是k階n維的實(shí)對(duì)稱張量.H的度對(duì)角張量D(H)是指對(duì)角元Di··i取頂點(diǎn)i的度,其余元素均為0的張量.超圖的Laplacian張量目前有不止一種的定義形式[1112],而下面這個(gè)定義從圖的角度看是最自然的.

定義2.3[11]設(shè)k-超圖H的頂點(diǎn)數(shù)為n,則稱(D?A)是其Laplacian張量,記為L(H).

引理2.1[11]設(shè)k-超圖H的頂點(diǎn)數(shù)為n,Laplacian張量為L,其最大H-特征值為λmax(L),則

引理2.2[13]設(shè)k-超圖H的頂點(diǎn)數(shù)為n,鄰接張量為A,則

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

3 主要結(jié)果

定義3.1超圖H頂點(diǎn)集的一個(gè)劃分V(H)=S∪ˉS,若其邊割

這里的max是取遍H的奇劃分,稱Moc(H)是H的最大奇割.

超圖的奇劃分總是存在的:任取H的一個(gè)頂點(diǎn)記為S0,則δS0的每條邊與S0關(guān)聯(lián)的頂點(diǎn)數(shù)恰為1,因此是H的一個(gè)奇劃分.并且當(dāng)k=2時(shí),超圖的奇劃分定義與圖的劃分定義等價(jià),最大奇割與圖的最大割定義等價(jià).

定理3.1設(shè)H是n個(gè)頂點(diǎn),m條邊的k-超圖,L是其Laplacian張量,V(H)=S∪ˉS是H任意的奇劃分,則

證明設(shè)若i∈ˉS.A是圖H的鄰接張量,由引理2.2,可得

因?yàn)?/p>

所以

又因?yàn)橄蛄縳滿足

推論3.1設(shè)H是n個(gè)頂點(diǎn)的k-超圖,則其最大奇割滿足:

證明設(shè)就是H的滿足|δS|最大的奇劃分,即

當(dāng)k=2時(shí),推論3.1與文獻(xiàn)[14]給出的圖最大割的如下結(jié)果一致:

這里的min是取遍Rn+中的向量x,文獻(xiàn)[11]定義

并將α′(H)稱為H的代數(shù)連通度.認(rèn)為將α(H)=2α′(H)稱為k-超圖H的代數(shù)連通度更合適,理由可見下面的定理3.2和定理3.3.

引理3.1[11]k-超圖H連通的充要條件是α(H)>0.

引理3.2[11]設(shè)H是n個(gè)頂點(diǎn)的k-超圖,S是V(H)的非空真子集,則

稱為點(diǎn)集S的邊密度.

定理3.2設(shè)H是n個(gè)頂點(diǎn)的k-超圖,則

證明設(shè)S0?V(H)就是H的滿足ρc(S)最小的非空點(diǎn)集,即ρc(S0)=γ(H).由引理3.2,可得

命題成立.

當(dāng)k=2時(shí),定理3.2與圖的平均最小割的如下經(jīng)典結(jié)論[15]一致:

n個(gè)頂點(diǎn)的k-超圖H的等周數(shù)定義為:

圖的等周數(shù)已有大量的研究[1617],這里考慮k-超圖的等周數(shù).

定理3.3設(shè)H是n個(gè)頂點(diǎn)的k-超圖,則

證明?S?V(H),若則由引理3.2,可得

由i(H)的定義可知命題成立.

當(dāng)k=2時(shí),定理3.3與文獻(xiàn)[16]給出的圖等周數(shù)的如下結(jié)果一致:

參考文獻(xiàn)

[1]貝爾熱C.超圖[M].南京:東南大學(xué)出版社,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-完全一致混合超圖不可著色的一個(gè)充要條件[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué),2011,27(3):308-312.

[7]鄭國彪.關(guān)于D-完全一致混合超圖上色數(shù)的一個(gè)結(jié)論的推廣[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué),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.

福建省中青年教師教育科研項(xiàng)目(JB13194).

鄢仁政(1980-),碩士,講師,研究方向：圖論及其應(yīng)用.

2010 MSC:05C65