關(guān)于n部圖的無向不同構(gòu)圖計(jì)算

廉曉龍， 魏連鑫， 張 軍， 馮恩民

關(guān)于n部圖的無向不同構(gòu)圖計(jì)算

廉曉龍1， 魏連鑫2， 張 軍3， 馮恩民4

圖的計(jì)數(shù)問題是圖論中一個(gè)比較基本的問題，也是一個(gè)NP困難問題（非確定性多項(xiàng)式問題）.文獻(xiàn)［1-2］研究了二部圖中無向不同構(gòu)圖的計(jì)算問題，文獻(xiàn)［3-6］研究了一些特殊類型的三部圖中無向不同構(gòu)圖的計(jì)算問題，文獻(xiàn)［7］解決了一般三部圖中無向不同構(gòu)圖的計(jì)算問題.本文通過建立一個(gè)特殊的向量映射關(guān)系，再應(yīng)用圖論、有限群對(duì)集合的作用、軌道及等價(jià)關(guān)系等將無向不同構(gòu)圖的計(jì)算推廣到了n部圖，給出了n部圖中無向不同構(gòu)圖的個(gè)數(shù)的計(jì)算公式.

1 向量映射與n部圖的關(guān)系

設(shè)有n個(gè)集合，分別記為Vi=｛ai1，ai2，…，aim｝，i=1，2，…，n.現(xiàn)在Vi與Vj（1≤i＜j≤n）i的元素之間建立關(guān)系，構(gòu)成由n個(gè)集合的元素為頂點(diǎn)的n部圖.對(duì)任意的正整數(shù)p，定義指標(biāo)集〈p〉∶=｛1，2，3，…，p｝.令

得V到A的一個(gè)映射g，稱g=（g12，g13，…，g1n，g23，…，g（n-1）n）為向量映射.

令V到A的向量映射集合為M=｛g∶V→A｝=AV.

定義2設(shè)V=V1×V2×…×Vn，對(duì)?g∈M，稱集合

為廣義邊集.其中，T表示分量都是0或1的n（n-1）/2維的向量，即T=（t12，t13，…t1n，t23，…，t（n-1）n），tij∈｛0，1｝，1≤i＜j≤n；αT表示在α的第i個(gè)分量aiki和第j個(gè)分量ajkj間建有tij（1≤i＜j≤n）條邊.當(dāng)tij=0時(shí)，兩元素之間無邊；當(dāng)tij=1時(shí)，兩元素之間有邊.稱（V，Eg）為以V為頂點(diǎn)集，以Eg為邊集的n部圖，記為Gg.

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

3 結(jié)論與計(jì)算

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

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

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

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

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

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

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

［8］ 胡冠章.應(yīng)用近世代數(shù)［M］.3版.北京：清華大學(xué)出版社，2006.

（1.延邊大學(xué)師范分院，延吉 133000；2.上海理工大學(xué)理學(xué)院，上海 200093；3.延邊大學(xué)理學(xué)院，延吉 133002；4.大連理工大學(xué)數(shù)學(xué)科學(xué)學(xué)院，大連 116024）

通過建立一個(gè)新的向量映射關(guān)系，并在該向量映射關(guān)系下應(yīng)用圖論、有限群對(duì)集合的作用、軌道及等價(jià)關(guān)系等對(duì)三部圖中無向不同構(gòu)圖的計(jì)算結(jié)果進(jìn)行推廣，研究了n部圖的無向不同構(gòu)圖的計(jì)算問題，并給出了計(jì)算公式.

n部圖；不動(dòng)點(diǎn)；不同構(gòu)；有限群；軌道

Computation of Non-isomorphic Graphs with No Direction in n-partite Graphs

LIANXiaolong1， WEILianxin2， ZHANGJun3， FENGEnmin4
（1.Branch Normal College，Yanbian University，Yanji 133000，China；2.College of Science，University of Shanghai for Science and Technology，Shanghai 200093，China；3.College of Science，Yanbian University，Yanji 133002，China；4.College of Mathematical Science，Dalian University of Technology，Dalian 116024，China）

A new vector mapping method was constructed.By using the new vector mapping，combining with the applications of graph theory，finite group acting on sets，orbit and equivalent relation，the result of the calculation of non-isomorphic graphs with no direction in tri-partite graphs was popularized，The computation of non-isomorphic graphs with no direction in the npartite graphs was studied and the corresponding computation formula was given out.

n-partite graphs；fixed point；non-isomorphism；finite group；orbit

O 157.5

A

1007-6735（2013）01-0041-03

2011-03-10

國家自然科學(xué)基金資助項(xiàng)目（19871009）

廉曉龍（1975-），男，副教授.研究方向：圖論及布局優(yōu)化.E-mail：lx1751124@163.com

張 軍（1957-），男，教授.研究方向：布局優(yōu)化問題.E-mail：zhangjun@ybu.edu.com