无向超图的计数级数.pdf_大学文库_中国高校课件下载中心

D0I:10.13374/j.issn1001-053x.1999.05.053 第21卷第5期北京科技大学学报 Vol.21 No.5 1999年10月 Journal of University of Science and Technology Beijing 0ct.1999 无向超图的计数级数黄汝激北京科技大学信息工程学院，北京100083 摘要应用置换群理论，引入了超边群、超图群和超图同构的概念，导出了超边群及其循环指标的一般表达式.导出了无向无标号超图和标号超图的计数级数，解决了无向超图的同构和计数问题. 关键词超图；超边群：超图同构：计数级数分类号0157.5 超图的同构和计数问题是超图理论的一个超边置换b,a上一个超边置换b,SH上一个h 重要课题.文献[1,2]只介绍了图的同构和计数 -超图置换c和SH上一个超图置换c,从S,导出理论，如何把它推广到超图，研究成果很少).本的所有b,b,c和c分别构成h-超边群S,超文应用置换群理论，研究无向超图的同构和计边群S,h-超图群GH和超图群GH,.它们的对数问题，象集分别是m,o,SHw和SH.其中Sg={(e)}和 GH={(H)}是单位元素群，lS=GH叭=1. 1超边群、超图群和超图的同构设置换群P的对象集为X,P称为P的阶，| X)称为P的度.考虑X的二子集S∈X,S'∈X,若存 (P,g)无向超图H是点集V和超边集E的在a∈P使aS=S',则称S与S'为P.等价的，记作有序对(V,E),M=p21,回=920，即 SS'.特别是若有a∈P,ar=y,则y=x,x的P.等 H=(VE),V={1,,p,E={e,…,eg,e={i,, 价类x)yyEX,a=y}.X可按P.等价类分成n ia}sV,1≤hsp (1) 个不相交子集：9，…，0n,且式中，超边e,含h个点，亦称h-超边，简写成e,= ,,m,其中点，…，称为超邻接的.若e*e X=0,U…U8n1≤n≤XM,0,n8,=中，i*(2) X的稳定核Px){ala∈P,ar=x}.P可按Px)划分 ,廿j,则H称为简单超图，否则称为多重超图. 成m个不相交子集，即：若H的p个点标定了不同标号，如1，，p,则H 称为标号超图，否则称为无标号超图.下文中超 P=UM P(x)a,m=0(x),a=e,aEP-U-P(x)a, =2,…,m (3) 图均指"简单标号无向超图”.令E= {ele∈E,lel=h},则E=UUR,E,H=(V,Em)称为H 式中，e为单位置换.从上式可导出 P=(xP(x) (4) 的h-子超图. 定义h-超边集-{ee三V,le例=h},则若赋予每个6，及所有x∈0，以相同权 W)=Wx女∈)，则从上式可导出X的等价类权训==p!/h!p-h)!,其中表示从p元和公式：素取h元素的组合数.特别有o={eeo=仍. 进一步引入下列定义：p点全h-超图K= 三队)=向三d (5) (,),p点h-超图集SH={H=(V,E 超图H=(V,E)与H2=(V,E)称为同构，记作 E≤}，全超边集=U层1，=2-1，p点 H,三H2,若H,与H2是S-等价的，即有a∈Sn和从a 全超图K=(Y,),p点超图集SH={H=(V,E) 导出的b∈Sg和c∈GH,使E2=bE,和H,=cH,亦即 E≤.点集V上所有p!个置换构成点群（对称 H,与H之间存在一个保持超邻接性的点置换群)Sp.从每个点置换a∈S,可导出上一个h- aES,.若去掉标号，S-等价类H)中所有标号超图将变成同一个无标号超图，即每一个标号超 1999-01-13收稿黄汝激男，68岁，教授

第卷第期年月北京科技大学学报、一无向超图的计数级数黄汝激北京科技大学信息工程学院，北京摘要应用置换群理论，引入了超边群、超图群和超图同构的概念，导出了超边群及其循环指标的一般表达式导出了无向无标号超图和标号超图的计数级数，解决了无向超图的同构和计数问题关键词超图超边群超图同构计数级数分类号超图的同构和计数问题是超图理论的一个重要课题文献【，只介绍了图的同构和计数理论，如何把它推广到超图，研究成果很少【本文应用置换群理论，研究无向超图的同构和计数问题超边群、超图群和超图的同构，无向超图，，是点集和超边集的有序对习，川之，囚七。，即月二五，，… ，，，… ，，，爵，… ，六， ‘ 印式中，超边马含个点，亦称超边，简写成，二，， … ，，其中点，， … ，存称为超邻接的若羊，私则万称为简单超图，否则称为多重超图若的个点标定了不同标号，如，… ，，则称为标号超图，否则称为无标号超图下文中超图均指 ” 简单标号无向超图 ” 令低已任， ‘一，则咪 ‘内，，尸，五介，称为万的子超图定义超边集叼性叫】二，则尸叫，切一，其中，表示从元素取元素的组合数特别有砂，二产尹二玛进一步引入下列定义点全一超图理，尸六，，尸点一超图集况日《石，尸 ‘ ，代石〔内，二砂，，全超边集砂，二研二，砂，砂】一，点全超图玲，，砂，点超图集二万二砂，点集上所有尸个置换构成点群对称群，，凡从每个点置换任凡可导出砂，上一个超边置换，砂上一个超边置换，凡印上一个一超图置换，和厅上一个超图置换。从凡导出的所有，，，和。分别构成超边群军，，超边群琴，超图群卿，和超图群凡它们的对象集分别是尸功，砂城附《劫和厅其中幸，尹和砂，二砂，是单位元素群，酬卜毋卜设置换群尸的对象集为，田称为尸的阶，川称为尸的度考虑的二子集任， ‘ 任龙若存在任使二 ‘ ，则称与 ‘ 为等价的，记作兰 ’ 特别是若有任尸，，则兰的几等价类阶玲伽沙，一对可按几等价类分成个不相交子集，… ，，且，氏，三 ‘ 因，民价，对的稳定核尸以红任，尸可按尸划分成个不相交子集，即尸碑，雌，，二，任尸一岭尸马，，… ，式中，为单位置换从上式可导出】侧不年若赋予每个叹及所有任以以相同权叫，州戈眯任，，则从上式可导出的等价类权和公式「‘，鲁。，请煞叫超图鱿五，与从二代石称为同构，记作鱿皇从，若私与从是一等价的，即有任凡和从导出的任酷和任耳使及和从万】，亦即私与从之间存在一个保持超邻接性的点置换任凡若去掉标号，一等价类厌功中所有标号超图将变成同一个无标号超图，即每一个标号超一一收稿黄汝激男，岁，教授 DOI ：10．13374／j ．issn1001－053x．1999．05．053

北京科技大学学报年第期图凡一等价类对应于一个无标号超图超图万三习万二咪，的自同构是到它自身的一个同构，即有任凡及其导出的，和涟，使，，，… ，所有这种置换，和，分别构成的点群只功，超边群几功和一超边群显然有几功二衡几功，八心八心卜凡几心，，，几衅，酷，定理几洲和与点群月功同构的充分必要条件是中至多有一个不与任何超边关联的孤立点对于任二邻接点和，中有一超边含，且不含，或含姚且不含定理的证明类似于文献【中定理因，和君，， … ，一满足上二条件，故据式得推论超边群，和，， … ，一，都与点群凡同构，从而它们的基数都是川超边群，及其循环指标的一般表达式阵， … ，上个置换构成的点群凡可表示为凡一九。，。一 … 。，、， … ，艺’ 沙衡产黑，〕【阴〕… 十一，’ ，任创式中表示对循环中每个元素取对模的余数若把每个中个下标对应的个点组成一条超边砂，则柯个对应于同一条酬这条超边砂，… ，毋形成一个且只形成一个长超边循环才…哟从可组成，条超边，其中一部分构成瓜个长一超边循环竺，，，，，… 孤同理，若，， ‘二 ‘， ‘ ‘ ，则从可形成一个 ‘ 长 ‘ 一超边循环 ‘ ，从它可组成《 ‘ ， ‘ 条一超边，其中一部分构成儿，个 ‘ 长一超边循环故只有【《，一艺 ’儿， ‘ 条一超边可用于构成醋，力，从而儿可按值的增序产习 … 礼味，用递推公式一计算把岭，丫对所有，和值求积即得，和，正一勿万，一酗，动竺，，，， “ ，，，日，优刁，则有引理脚，二个超边置换，拼，… ’，任取一组个， · ，，习 … 今 ‘ 。习，从每个任取一个溉〕满足条件气二气， ‘ 印，可导出一个新超边置换，… ，如下，… ，，… ， … ，… ，一式中，点置换表示成长点循环诀的乘积沂是长为的的个数，向量 ’ 口，… 卉称为的循环分解向量引理每个点循环久导出如下一个超边置换，， ‘，，， … “ ，凡脸，… 刃，… 沂一 “ ，，… ， ‘ 七俪批劫神产召么， “ 、，万声， ’ · ’ ，，。，封，』尸】日，户产 ‘” ，，幻用戈纷，，，沃耐伽土， ’ ，，… 艺 ‘养一式中，是一超边置换是与最大公因数刃阴表示是的因素且无分是的因数，它在下表示对所有这种值求积酷，，是号一长一超边循环汤是一长一超边循环的个数，是从。个元素取个的组合数证令。卜表示久的对应下标循环，司九，剐试，必仃’ ，仃刃一价刹必划为欧拉函数，则有几，… 岁从人介【 … 。〕一式中俄，，… ，人八，表示 “ 号长一超边循环，〔，… 月是，，… ，。的最小公倍数而是这种循环的个数，求积是对变量，，，，卜，… ，的所有可能值进行的证从所取个循环破，，… ，每个任取一条，一超边，可组成刀蕊，… 。条一超边，它们在该。个循环的联合作用下，可构成苏了个长一超边循环俄，，… ，，，，… ，几刀浅卜 … 了从对所有变量的所有可能值求积，就得一和式根据引理和，考虑到砂，砂，且砂，是单位元素群，可推得下列定理定理从点群凡可导出超边群，和一超边群罕，的一般表达式如下， “ ，… 加，，，…砂，罕，一。 ‘” ，。 ‘“ ，一八九。 ‘为，、，七， ‘ 卜一 ‘ ，，… ，

Vol.21 No.5 黄汝激：无向超图的计数级数 ·509· h=l,…,p-1 (11-b) w(r)=(w(r),…,w.(r)和权函数Wryy.y. S=1bob-(e)) (11-c) 定义图形计数级数为式中，(e)是p-超边e的单位置换.特别有Sg=Sp, cwe8ry=Σcy (15) 且S9是图论中的对群. 式中，c是权为w()一w的图形r的数目.定义构定理3超边群S和S的循环指标Z(S)和形的权函数为 Z(Sg)的一般表达式： ww(d))=Iy-yw()-w((d)(16) ZSg=ZSg)…Z(SP) (12) 易证f的E等价类)中所有函数的权都相 Z(S)(kr,s)-, 同，定义)的权W()=Wf∈).设R共含n bti51,",tnS0一SMa] (13-a) 个E等价类：9，…，0n,定义构形计数级数（或生成 2S☆81-4。只函数)为 hmH(h) 1a太加 S所人 CW-立wm8)-y-ΣCy (17) )i,…o),N)=p/Πkj4jj+…tjn 式中，C,是权为w()-w的构形等价类8，的数目. M-{m…m,fM=m…mM,h=1,…p-1(13-b) Polya定理可推广成下面的p变量形式. ZS)=S1p (13-c) 定理4（广义Polya定理）构形计数级数式中，一表示"换成"，求和是对满足Σ=p Cy)可从置换群A的循环指标Z(A)中把变量s 的所有向量V)1,…)进行的，S%表示置换b中换成图形计数级数cy)得到，即含有f个m长h-超边循环，余类推，每项中所有 C0y,…y=ZA,s4→c0,…) (18) 循环的个数与长度之积的和等于P,h). 正：设aEA,eta0,则z乙0e闪三. 证：(12)式是由于二置换群乘积的循环指若ef=fdea(),fd-reR,则(ef(d-fad 标等于其对应循环指标的乘积.(13-a)式是根据 f(d),ad∈a(),即f八d)=r∈R,Vdea().由此并应用循环指标的一般定义).因有相同向量)的b (5)式，令P=E,即得：对应的项都相同，这种项有)个，故按)集项，可推得(13-b)式.从(11-c)式推得(13-c)式. wym1gy-i年少n k1同I rER dEoli h-超边e=V与(p-h)-超边e-=V-e称为互 -f fic(y)=f1lc(): 补超边，二者一一对应，b与bP-=b(e一e)也 com0a三07三awy- ·一对应，S与S是恒等的置换群.故有： Z(A.s.-c(y)). 推论3(a)互补的h-超边群S和(p-h)-超边无向无标号的超图计数级数h(xy),p点超群S州是恒等的，Sg=S%",即：图计数级数h,y)和p点h-超图计数级数hy)的 Z(Sy-)=ZSg,Smh一5mp-,h=1,…p-1(14) 定义如下：例1设省略5m的下标h,应用定理3和推 hxy)=Σh.y)x=hp.ox'y (19-a) 论3(a)可得 p] p.2 Z(SP)-Z(S)) h,0 v)=Ehnov,p=l,2,3,… (19-b) (19-c) ZS9y石6415si40si45si90sr+ h(y上hyR,h=l,…2 9.0 式中yy,…y,(g,…,4l,yt…%,h,e 120s7ss+144s+15s°+90ss+40ss+ hpg,表示含p点q条h-超边，h=l,…p的无向无 12052S). 标号超图的数目，hp表示含p点g条h-超边的无向无标号h-超图的数目，求和是对所有p=1,2,… 3无向无标号超图的计数级数和2中所有q=0,1,…,p,h),h=1,…p,进行的. 设置换群A={a}的对象集为D={d,单位定理5hy)和h,y)可从Sg和S的循环指置换群E={e}的对象集为R={r},函数集RP= 标ZS)和ZS)导出： fD一R,r称为图形，∫称为构形，函数置换群 g0小ZS,54-1+岂t (20-a) 40 E={eef(d)=f八ad},E的对象集是R”,变量向 h,0 )=Z(S,S一1+y%,h=1,…p卢nhg6y) 量y(y,…,),y(,).赋于r∈R以权向量 h,hhme (20-b)

心黄汝激无向超图的计数级数， … ，一一酬伽，沙，一式中，是一超边砂的单位置换特别有裂凡，且驴是图论〔切中的对群定理超边群望和母，的循环指标和以毋的一般表达式， … ，。和权函数呵弓尸 ·，却 ‘ ·，… 试日定义图形计数级数为伽全叫艺丫 ‘ 尸，艺了式中，，是权为的图形的数目，定义构形的权函数为叭乃锻环戈八动一黔嘟咖刁 “ 切，切一恿抓朔 ‘ “ 易证的碑等价类试乃中所有函数的权都相同，定义口仍的权牙环飞乃分趁设尹共含个尸等价类，… ，氏，定义构形计数级数或生成函数为日、以母以瞬 … 酬以母〕会母，一 ’ 澎，竺，，，一，，，声，… ，，，，一。〕黔节条、公础旁歇夕旬阴肚户污习一一人幸气峭七加淑七幼矛，， ‘ 伽艺叫，艺丫伍艺么丫尸户 ’ 布，… 动，心孰娜， ’ ，二为卜〔 … 月，几，… 洲城，… 刃一一酬，一式中， ’与 ’表示 ” 换成 ” ，求和是对满足艺弘从的所有向量’ 仃，… 卉进行的，歇夕表示置换劫中含有几’ 个长一超边循环，余类推，每项中所有循环的个数与长度之积的和等于切，证式是由于二置换群乘积的循环指标等于其对应循环指标的乘积一式是根据循环指标的一般定义〔，，因有相同向量 ’ 的，对应的项都相同，这种项有刃口个，故按’ 集项，可推得一式从一式推得一式一超边，犷与勿一一超边沙一呢一，称为互补超边，二者一一对应，，与沙一一沙一勺也一一对应，驴，与砂一是恒等的置换群〔，〕故有推论互补的一超边群罕和切一一超边群聆一是恒等的，，二平一，即酷一 ’ 珊， ‘ ，一‘ ，一办，，… ，一例设省略‘ ，的下标，应用定理和推论可得式中，是权为，，的构形等价类以的数目定理‘，可推广成下面的变量形式定理广义定理构形计数级数伽可从置换群的循环指标及月中把变量又换成图形计数级数试犷得到，即伽，’ 扮刀冰燕一份，… 苏证设 · ，喜套久，则挂街恿睿、 · 若‘ 子锐任几，八刃，则们刃于八司刃，任，巨刃任，任由此并应用式，令月，即得恶哪观黔喇“ 一警县恿易尸一县县犷们乏留忿伊〔伊梦卜妙艺呵，一花可艺乏护尸少‘ 了少哪椒份于卜奇、子，，，、带。巧 ” ，，、，、，亏圣忍尝聋母全呢无向无标号超图的计数级数设置换群二毛的对象集为毋，单位置换群的对象集为，函数集性仃甘，一，称为图形称为构形，函数置换群尸川试力刃习刃尸的对象集是，变量向量厂蜘，… 妇，鹉份，… 苏赋于任以权向量，一伊无向无标号的超图计数级数力，点超图计数级数气伽和点一超图计数级数心知的定义如下少二艺气妙丫艺气，的尸一 · 气妙艺气，尹，二，，，’ · 一公，。、一誉，，。一，… ，一争印式中厂伽，… 伪，，，… ，价刁。弓哼二吟，气户气，。，表示含点条一超边，，… ，的无向无标号超图的数目，栋表示含点、条一超边的无向无标号一超图的数目，求和是对所有尸，，… 和中所有争，，… ，切，，，… ，，进行的定理砂饥和气妙可从裂，和，的循环指标酷和导出钟》衅饥以酬，一切二艺气洲一小司气切罕，，一够，一，… 劝一六衅饥艺气沙气气二县呱，一

·510· 北京科技大学学报 1999年第5期证：在定理4中令A=S,D=,R=R={0,h}, 位群Eg=E和超边单位群E=E,的循环指标导 f=f:一R,wr）d,i=1,…P,=0,h,S=5mh,则出如下： c0y)=cy1+y,Sm一c0)=1+y%,式中y%表示导出 H6）ZEo,4-1-1+wn=笔o,,g Sm的那个b的m条h-超边被f映射到=h,即被 (24) 取来构成h-超图，1=(y)°表示这m条h-超边被映射到=O,即舍去不用，因此每个函数f表 Hv,v)=Z(Ez,s-1+y.,h=1,p)=IIH(ya) ■1 示一个h-超图，Cy=hya),h表示含p点q条h- =1(1+ya) (25) 超边的标号h-超图的S,等价类（或对应无标号推论6(a)从定理6可推出下列结果： h-超图)的数目.对于S有p个函数集R,= (1)(p,9)无向标号h-超图数np,h),q: ff:w-R,h=l,,由(12)和(20-a)式可推 (2)p点无向标号h-超图总数n-2; 得(20-b)式. (3)(P9)无向标号超图数n2-1,q: 例2设省略下标h=3,应用定理5可得 (4)P点无向标号超图总数。=2-”. h(y)=Z(S,s-1+y)= 定理7一个P点无向无标号超图H的所有标号 4+r46(1+1+y+81+X1++ 方式（即对应的所有标号超图）的数目是 3(1+y22+6(1+y)]= l(H=p!/NH (26) 1+y+y+y+y. 式中H)和H)是H的对应标号超图等价类和推论5(a)p点无向无标号的h-超图总数n 点群. 和超图总数n,如下：证：(4)式中令P=S,x=H,Px=H),即得. n=hgy=1上Z(SpSmk一2)，h=1,…P (21-a) 例3设H的一个对应标号超图H,(V,E), n=ΠRng (21-b) V={1,…,4},E={123,124},则H={(1)2)3)4), 推论5(b)含有指定的一些h超边 (12)(3)(4),(1)(2)(34),(12)(34)},HTH)=4, (h∈U={h,h2,…}三V的p点超图计数级数hy)为 H=p!rH0=4!/4=6.实际上，E)={E, h,y)FΠhgya=Σh.eye (22) {234,231},{341,342},{412,413},{134,132}, {241,243},lE)=6. 特别当U={2}时，hy)=h0y)就是文献[1]中定理 15.5内的p点图计数多项式g(x) 5结论推论5(c)p点无向无标号多重h-超图的计数级数是导出了超边群及其循环指标的一般表达式， mo(y)=Z(Sp,sm-c(y)=(1-y)) (23) 并导出了无向无标号超图和标号超图的计数级数，解决了无向超图的同构和计数问题. 4无向标号超图的计数级数参考文献 p点单位置换群E,={e},e(1)(p),它的循环 1 Harary F.Graph Theory.Massachusetts:Addison-Wesley, 指标是Z(E)=.每个标号超图都构成一个E。-等 1969 价类，分别令A=E和，从定理4可推得 2 Harary F.Palmer E M.Graphical Enumeration.New York and London:Academic Press,1973 定理6p点无向标号的h-超图计数级数 3柳柏濂.超树的计数理论I.数学季刊，1988(2：78 Hgy)和超图计数级数Hy,…y)可从h-超边单 4黄汝激.有向超图理论的发展和应用.电子科技导报，1995(3)：10 Counting Series of Undirected Hypergraphs Huang Ruji Information Engineering School,UST Beijing,Beijing 100083,China ABSTRACT By applying permutation group theory,the concepts of hyperedge group,hypergraph group and hypergraph isomorphism are introduced,and the general expressions of hyperedge group and its cycle index are derived.Then the counting series are derived for undirected unlabeled and labeled hypergraphs,thus the isomorphism and counting problems of undirected hypergraphs are solved. KEY WORDS hypergraph;hyperedge group;hypergraph isomorphism;counting series

一北京科技大学学报年第期位群犁二凡力和超边单位群的循环指标导出如下勿，，饥以凡，，一、切力，艺切，，州〕琳、、了、，产、、了，‘ ﹄证在定理中令裂，砂，，厂，，介厂 ‘，砂，一尺、，，氏，，… 刃，二，，一 · ，，则切饥卜， ‘ ，一伏勺心，式中刃表示导出 ‘ ，的那个毋，的条一超边被厂映射到，即被取来构成一超图，卜帆表示这条一超边被尹，映射到，即舍去不用因此每个函数厂表示一个一超图刀妙砂饥，凡二表示含点、条超边的标号一超图的凡一等价类或对应无标号一超图的数目对于〕有个函数集介护的沪，砂一、，，… ，，由和一式可推得一式例设省略下标，应用定理可得脚切二叉》声，一丫凡。】，… 、一，，一，、，一 ‘ ，… ，一息卿饥，一那‘ 洲推论从定理可推出下列结果帆的无向标号一超图数碟气切，，点无向标号一超图总数心回仇无向标号超图数、气分一，砂点无向标号超图总数伟月卜命。， ‘，，、，“ ‘，，‘，甲，少， ’ 〕勺尸甲丫推论点无向无标号的一超图总数心，和超图总数伟如下心，心，饥以母，，，，，二，… 刃一刀厂象，心，一推论含有指定的一些一超边任九，… 二的点超图计数级数气切为气伽砂，伽、艺气，。夕为〔口特别当时，凡伽嘴饥就是文献【中定理内的点图计数多项式肠推论点无向无标号多重一超图的计数级数是衅，饥二砂，，，，、一帆一刃一 ’ 定理一个点无向无标号超图的所有标号方式即对应的所有标号超图的数目是氏功八式中以功和八功是的对应标号超图等价类和点群证式中令介凡声万尸。布以功，即得一例设的一个对应标号超图，，犷，… ，，百，，则八万，，，，口功口从科，夙功川口功卜实际上，氏百，，，，，，，，，，川酬万卜无向标号超图的计数级数点单位置换群凡。，二勿，它的循环指标是以瓦叫每个标号超图都构成一个凡一等价类，分别令犁，和母，从定理可推得定理点无向标号的一超图计数级数砂帆和超图计数级数凡伽，… 孙可从一超边单结论导出了超边群及其循环指标的一般表达式，并导出了无向无标号超图和标号超图的计数级数，解决了无向超图的同构和计数问题参考文献哪七一七弥娜即甜，柳柏镰超树的计数理论工数学季刊，黄汝激有向超图理论的发展和应用电子科技导报，刀初口 ’ ，，，汀，即，场冲，坤，坤坤