星形布局的不同構圖的計算

張 軍

（延邊大學理學院 數學系，吉林 延吉133002）

星形布局的不同構圖的計算

張 軍

（延邊大學理學院 數學系，吉林 延吉133002）

根據物理學中圖態與數學中圖的對應關系，從數學的角度構建了1個特殊的向量映射關系，應用圖論、有限群對集合的作用、軌道及等價關系等將一類多部圖按同構進行了分類，并給出了不同構圖（態）數目的計算公式．

布局；不同構；不動點；有限群；軌道

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

1 向量映射與星形布局圖

設有n＋1個集合，分別記為

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

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

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

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

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

2 Burnside引理的應用

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

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

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

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

2 Burnside引理的應用

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

3 結論與計算

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

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

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

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

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

解 設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（α）＝（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｝．現計算與V對應的有限群S＝S2×S3×S2×S1作用于4部星形圖集X上的軌道個數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上的軌道個數，則所求不同構4部星形圖的個數為

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

［2］ 計新．多量子位糾纏態的制備［D］．哈爾濱：哈爾濱工業大學，2011．

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

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

［5］ 馮恩民，張軍，王錫祿．換熱網絡綜合問題中的布局優化［C］//中國運籌學會第六屆學術交流會論文集．香港：Global－Link出版社，2000：542－547．

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

［7］ 張軍．換熱網絡布局問題的改進及計算［J］．延邊大學學報：自然科學版，2006，32（4）：40－43．

［8］ 廉曉龍，張軍．一類網絡布局優化問題的不同構圖的計算［J］．延邊大學學報：自然科學版，2008，34（3）：177－178．

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

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

［11］ 胡冠章．應用近世代數［M］．2版．北京：清華大學出版社，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—），男，教授，研究方向為布局優化．