星形布局的不同構(gòu)圖的計算

張 軍

（延邊大學(xué)理學(xué)院 數(shù)學(xué)系，吉林 延吉133002）

星形布局的不同構(gòu)圖的計算

張 軍

（延邊大學(xué)理學(xué)院 數(shù)學(xué)系，吉林 延吉133002）

根據(jù)物理學(xué)中圖態(tài)與數(shù)學(xué)中圖的對應(yīng)關(guān)系，從數(shù)學(xué)的角度構(gòu)建了1個特殊的向量映射關(guān)系，應(yīng)用圖論、有限群對集合的作用、軌道及等價關(guān)系等將一類多部圖按同構(gòu)進(jìn)行了分類，并給出了不同構(gòu)圖（態(tài)）數(shù)目的計算公式．

布局；不同構(gòu)；不動點；有限群；軌道

自1935年Einstein等發(fā)表質(zhì)疑量子力學(xué)完備性的論文以來，量子糾纏就一直成為量子力學(xué)中熱點討論的基本問題之一．研究［1］表明，很多經(jīng)典方法所不能實現(xiàn)的量子信息方案都可以通過量子糾纏來輔助實現(xiàn)．近年來，一種特殊類型的多量子位糾纏態(tài)——圖態(tài)引起了人們的關(guān)注，它是與數(shù)學(xué)中的圖有關(guān)的一種特殊的純多量子位糾纏態(tài)，圖的結(jié)點就相當(dāng)于物理系統(tǒng)，而圖的邊則表示2個不同物理系統(tǒng)之間的相互作用．圖態(tài)的許多糾纏特性與相應(yīng)的圖有關(guān)，有些圖態(tài)已成為量子計算和量子信息的重要資源，例如：團(tuán)簇態(tài)是單向量子計算的有用資源，多量子位GHZ態(tài)是量子通訊的重要資源等［2］．本文根據(jù)圖態(tài)與數(shù)學(xué)中圖的對應(yīng)關(guān)系，從數(shù)學(xué)的角度建立1個特殊的向量映射關(guān)系，應(yīng)用圖論、有限群對集合的作用、軌道及等價關(guān)系等將文獻(xiàn)［3－9］等二部、三部圖進(jìn)行了推廣，將文獻(xiàn)［10］的串聯(lián)式布局改成了星形布局，給出了一類多部圖的不同構(gòu)圖（態(tài)）個數(shù)的計算公式．

1 向量映射與星形布局圖

設(shè)有n＋1個集合，分別記為

定義1 設(shè)g＝（g01，g02，…，g0n），其中g(shù)0i為V0×Vi（i∈ 〈n〉）到｛0，1｝的映射，即對…，t0n）∈A，則可得V到A的1個映射g，稱g＝（g01，g02，…，g0n）為向量映射．令V到A的向量映射集合為M＝｛g∶V→A｝＝AV．

定義2 設(shè)V＝V0×V1×…×Vn，對?g∈M，稱集合為廣義邊集．其中T表示分量都是0或1的n維向量，即T＝（t01，t02，…，t0n），t0i∈｛0，1｝，i∈〈n〉；αT表示在α的第1個分量和第i＋1個分量之間建有關(guān)系，記為t0i，i∈ 〈n〉．當(dāng)t0i為0時，2個元素a0k與aik之間無邊；當(dāng)t0i為1時，2個元素a0k與aik之間有邊．稱（V ，Eg）為以V為結(jié)點集，以Eg為邊集，以V0為中心的n＋1部星形圖，記為

令n＋1部星形圖Gg的集合為所

定義3 設(shè)Gg1＝ （V，Eg1），Gg2＝ （V，Eg2）∈X．若存在雙射σ∶V→V滿足，則稱Gg1與Gg2為同構(gòu)的n＋1部星形圖，

定義4 設(shè)Gg∈X，稱集合部星形圖Gg的等價類；集合中的任意元素（n＋1部星形圖）稱為Q（Gg）的代表元，且記n＋1部星形圖的等價類的集合為Qe＝

2 Burnside引理的應(yīng)用

設(shè)有限群S＝Sm0×Sm1× … ×Smn，其中Smj（0≤j≤n）均為對稱群．?σ＝（σ0，σ1，…，σn）定義σ對Gg的作用：σ（Gg）表示在σ（α）的第1個分量和第i＋1個分量之間建有關(guān)系當(dāng)t0i為0時，2個元素之間無邊；當(dāng)t0i為1時，2個元素之間有邊．稱（V ，Eg）為以V為結(jié)點集，以Eg為邊集，以V0為中心的n＋1部星形圖，記為

令n＋1部星形圖Gg的集合為所

定義3 設(shè)Gg1＝ （V，Eg1），Gg2＝ （V，Eg2）∈X．若存在雙射σ∶V→V滿足，則稱Gg1與Gg2為同構(gòu)的n＋1部星形圖，

定義4 設(shè)Gg∈X，稱集合部星形圖Gg的等價類；集合中的任意元素（n＋1部星形圖）稱為Q（Gg）的代表元，且記n＋1部星形圖的等價類的集合為Qe＝

2 Burnside引理的應(yīng)用

設(shè)有限群S＝Sm0×Sm1× … ×Smn，其中Smj（0≤j≤n）均為對稱群．?σ＝（σ0，σ1，…，σn）定義σ對Gg的作用：σ（Gg）表示在σ（α）的第1個分量和第i＋1個分量之間建有關(guān)系當(dāng)t0i為0時，2個元素之間無邊；當(dāng)t0i為1時，2個元素之間有邊．因此，有限群作用n＋1部星形圖Gg∈X的軌道為

3 結(jié)論與計算

由對稱群Smj（0≤j≤n）的元素性質(zhì)可知，當(dāng)σj∈Smj時，?λj1，λj2，…，λjmj∈｛0，1，2，…，mj｝，

定義5 設(shè)Smj（0≤j≤n）均為對稱群型置換．令）型元素．

其中（＊，＊）表示2個數(shù)的最大公因數(shù)．

由式（1）和式（2）可得有限群S＝Sm0×Sm1×…×Smn作用于n＋1部星形圖集X上的不同軌道數(shù)N為

例題1 設(shè)4個集合分別為V0＝｛a01，a02｝，V1＝｛a11，a12，a13｝，V2＝｛a21，a22｝，V3＝｛a31｝，求以V0為中心的不同構(gòu)4部星形圖的個數(shù)．

解 設(shè)V＝V0×V1×V2×V3，A＝｛（t01，t02，t03）｜t0i∈ ｛0，1｝，i∈ 〈3〉｝，向量映射g＝（g01，g02，g03），即對任意的α＝（a0k0，a1k1，a2k2，a3k3）∈V，k0∈ 〈2〉，k1∈ 〈3〉，k2∈ 〈2〉，k3∈ 〈1〉，有g(shù)（α）＝（g01（α），g02（α），g03（α））∶＝（g01（a0k0，a1k1），g02（a0k0，a2k2），g03（a0k0，a3k3））＝（t01，t02，t03）∈A，其中t0i∈ ｛0，1｝，i∈ 〈3〉．記向量映射集合M＝｛g∶V→A｝＝AV，4部星形圖集合X＝｛Gg｜g∈M｝．現(xiàn)計算與V對應(yīng)的有限群S＝S2×S3×S2×S1作用于4部星形圖集X上的軌道個數(shù)N．因有限群S＝S2×S3×S2×S1的所有可能的不同型元素為（12，13，12，11），（12，13，21，11），（12，1121，12，11），（12，1121，21，11），（12，31，12，11），（12，31，21，11），（21，13，12，11），（21，13，21，11），（21，1121，12，11），（21，1121，21，11），（21，31，12，11），（21，31，21，11），利用公式（3）計算S作用在X上的軌道個數(shù)，則所求不同構(gòu)4部星形圖的個數(shù)為

［1］ 許金時，李傳鋒，張永生，等．量子關(guān)聯(lián)［J］．物理，2010，39（11）：729－730．

［2］ 計新．多量子位糾纏態(tài)的制備［D］．哈爾濱：哈爾濱工業(yè)大學(xué)，2011．

［3］ 張軍，金明愛，馮恩民．換熱網(wǎng)絡(luò)布局問題的不動點集性質(zhì)及計算［J］．運籌與管理，2001，10（3）：89－92．

［4］ 廉曉龍，魏連鑫，張軍，等．三部圖中無向不同構(gòu)圖的計算［J］．上海理工大學(xué)學(xué)報，2010，32（6）：602－604．

［5］ 馮恩民，張軍，王錫祿．換熱網(wǎng)絡(luò)綜合問題中的布局優(yōu)化［C］//中國運籌學(xué)會第六屆學(xué)術(shù)交流會論文集．香港：Global－Link出版社，2000：542－547．

［6］ 廉曉龍，張軍．換熱網(wǎng)絡(luò)布局問題的不同構(gòu)圖的計算［J］．延邊大學(xué)學(xué)報：自然科學(xué)版，2009，35（4）：309－311．

［7］ 張軍．換熱網(wǎng)絡(luò)布局問題的改進(jìn)及計算［J］．延邊大學(xué)學(xué)報：自然科學(xué)版，2006，32（4）：40－43．

［8］ 廉曉龍，張軍．一類網(wǎng)絡(luò)布局優(yōu)化問題的不同構(gòu)圖的計算［J］．延邊大學(xué)學(xué)報：自然科學(xué)版，2008，34（3）：177－178．

［9］ 孫吉榮，廉曉龍，丁巍巍，等．一類三部圖中不同構(gòu)圖的計算［J］．延邊大學(xué)學(xué)報：自然科學(xué)版，2009，35（2）：109－111．

［10］ 方艷藍(lán)，金美英，廉曉龍，等．n個集合串聯(lián)式布局的不同構(gòu)圖的計算［J］．延邊大學(xué)學(xué)報：自然科學(xué)版，2010，36（1）：34－37．

［11］ 胡冠章．應(yīng)用近世代數(shù)［M］．2版．北京：清華大學(xué)出版社，1999：108－109．

The calculation of the graph of non－isomorphism in starlike layouts

ZHANG Jun
（Department of Mathematics，College of Science，Yanbian University，Yanji 133002，China）

Based on the corresponding relation between the physical graph state and the mathematical graph，we constructe a particular vector mapping from the view of mathematics．And by applying graph theory，finite group acting on sets，orbit and equivalent relation and so on，a multipartite graphs are classified according to the isomorphism．Finally，a computational formula is given for non－isomorphic graph（state）．

layout；non－isomorphism；fixed points；finite group；orbit

O157．5

A

1004－4353（2012）02－0115－03

2012－06－02

張軍（1957—），男，教授，研究方向為布局優(yōu)化．