关于n部图的无向不同构图计算

廉晓龙， 魏连鑫， 张 军， 冯恩民

关于n部图的无向不同构图计算

廉晓龙1， 魏连鑫2， 张 军3， 冯恩民4

图的计数问题是图论中一个比较基本的问题，也是一个NP困难问题（非确定性多项式问题）.文献［1-2］研究了二部图中无向不同构图的计算问题，文献［3-6］研究了一些特殊类型的三部图中无向不同构图的计算问题，文献［7］解决了一般三部图中无向不同构图的计算问题.本文通过建立一个特殊的向量映射关系，再应用图论、有限群对集合的作用、轨道及等价关系等将无向不同构图的计算推广到了n部图，给出了n部图中无向不同构图的个数的计算公式.

1 向量映射与n部图的关系

设有n个集合，分别记为Vi=｛ai1，ai2，…，aim｝，i=1，2，…，n.现在Vi与Vj（1≤i＜j≤n）i的元素之间建立关系，构成由n个集合的元素为顶点的n部图.对任意的正整数p，定义指标集〈p〉∶=｛1，2，3，…，p｝.令

得V到A的一个映射g，称g=（g12，g13，…，g1n，g23，…，g（n-1）n）为向量映射.

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

定义2设V=V1×V2×…×Vn，对∀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个分量aiki和第j个分量ajkj间建有tij（1≤i＜j≤n）条边.当tij=0时，两元素之间无边；当tij=1时，两元素之间有边.称（V，Eg）为以V为顶点集，以Eg为边集的n部图，记为Gg.

2 Burnside引理的应用

3 结论与计算

［1］ 冯恩民，张军，王锡禄.换热网络综合问题中的布局优化［C］∥中国运筹学会第六届学术交流会论文集.香港：Global-Link出版社，2000：542-547.

［2］ 张军，金明爱，冯恩民.换热网络布局问题的不动点集性质及计算［J］.运筹与管理，2001，10（3）：89-92.

［3］ 张军.换热网络布局问题的改进及计算［J］.延边大学学报（自然科学版），2006，32（4）：40-43.

［4］ 廉晓龙，张军.一类网络布局优化问题的不同构图的计算［J］.延边大学学报（自然科学版），2008，34（3）：177-178.

［5］ 孙吉荣，廉晓龙，丁巍巍，等.一类三部图中不同构图的计算［J］.延边大学学报（自然科学版），2009，35（2）：109-111.

［6］ 廉晓龙，张军.换热网络布局问题的不同构图的计算［J］.延边大学学报（自然科学版），2009，35（4）：309-311.

［7］ 廉晓龙，魏连鑫，张军，等.三部图中无向不同构图的计算［J］.上海理工大学学报，2010，32（6）：602-604.

［8］ 胡冠章.应用近世代数［M］.3版.北京：清华大学出版社，2006.

（1.延边大学师范分院，延吉 133000；2.上海理工大学理学院，上海 200093；3.延边大学理学院，延吉 133002；4.大连理工大学数学科学学院，大连 116024）

通过建立一个新的向量映射关系，并在该向量映射关系下应用图论、有限群对集合的作用、轨道及等价关系等对三部图中无向不同构图的计算结果进行推广，研究了n部图的无向不同构图的计算问题，并给出了计算公式.

n部图；不动点；不同构；有限群；轨道

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

国家自然科学基金资助项目（19871009）

廉晓龙（1975-），男，副教授.研究方向：图论及布局优化.E-mail：lx1751124@163.com

张 军（1957-），男，教授.研究方向：布局优化问题.E-mail：zhangjun@ybu.edu.com