【doc】二色有向图及二色有向自补图的计数与构造

【doc】二色有向图及二色有向自补图的计数与构造 二色有向图及二色有向自补图的计数与构 造 第l8卷第4期陕西师大(自然科学版)Vo1.18No.4 199L)年l1月JournalofShaanxiNormaIUnlvei"sity(Natura1ScienceEdition)Nov.1990 二色有向图及二色有向 自补图的计数与构造 许进 (数学系) 摘要 通过构造一种新的群,解决了:色有向图厦:色有向自补图的计数I可.获得 了有m个顶点的一种颜色和个顶点的另一种颜色的二色有向固的计数发生函数 B()厦二色有向自补图的数日分别是B…()=Z(S鬻S}1+)和Z(S鬻S., 0,2,0,2,…).井构造出m—=2的奎部76个二色有向图厦奎部12个二色有向 自补图. 关麓词l二色有向图J二色有向自补图,计数,拘遣 本文所言之图皆指有向,无环的图,文中未定义的概念均与文献[1]中的相同. 一 个有向图D一(,Y)称为二色的,如果D的m个顶点集具有一种颜色,个顶点集l, 具有另一种颜色,并且D的任一弧的首与尾两端的颜色相异.两个=色有向图D一(.,Y), D一(X,Y.)被称为是同构的,如果存在一个从D到D.的,保持颜色不变的同构映射,完 垒=色有向图,记作五…,具有m+个顶点,m个顶点具有一种颜色,个顶点具有另一种 颜色,并且任意两个顶点可达当且仅当它们有不同的颜色.显然五…有2mn条弧.设D示 一 个有向图,则用r-(D)表示D的线群. 若是一个置换群,其对象集为X,则的圈指标z()定义为 z()一古暑鱼s.(1) 其中ll表示的阶数,t(表示中的置换口中长度为t的圈的数目,它显然满足 1?,l+2?如+…+?^=.(2) 如果用^:表示中置换对的划分型为=(,j,…,.)的数目,则(1)可变为下列式 子l1_. z()T打善l?S:io(3)】 设一(,:,…,),l,一曲,g,…,.),定义与y的所有有序对构成的集合 X睾Y=X×l,UY×—t(i,),(,,.)』i=l,2,…,m,J=l,2,…,).在X{l| y上定义一个群,记作S素s,是一个由x中的m次对称群s与l,中的衄对称群s导出的群, 收稿日期j1989-07—11 4陕西师大(自然科学版)1990年 对于任l意(,)?x弗Y,其中?x,?Y,(,)?S弗S,这里口?S,?s. (,卢)(,)=(ax,).(4) 并且认定(口,)与(,)是一样的,因此,S木S.中共有m!n1个元素,xy中共有2mn个 元素,容易检验SS关于上述运算成群. SI理1设G是一个给定的图,剐G的具有r条边的所有生成子图的数目是下式中的 系数. Z(Fl(G),l+).(5) 定理2对于任意的正整数m,n,具有m个顶点的一种颜色和n个顶点的另一种颜色的二 色有向图的计数发生西数B…()是 B…()暑Z(S木S,1+).(6) 舯Z(SS善直垂s2-r.~r,,l"f"'',(7) 这里,[r,]表示r与的最小公倍数,(r,1)表示r与的最大公约数. 证明首先注意到任一具有m个顶点的一种颜色和个顶点的另一种颜色的二色有向图 D一(x,I,)都是五…的生成子图.反过来,五…的任一生成子图D一(x,y)都是具有m 个顶点的一种颜色和个顶点的另一种颜色的二色有向图,因此,由引理1,从而有下述结 果 B…()=Z(f1(K…),1+).(8) 以下来确定五…的线群F(五…).假设x是五…中m个顶点的同种颜色的点集合,y 是具有同种颜色的n个顶点的集台,则在x木Y中的每一个有序对(,),恰好对l应五…中 的一条弧,因此,F(K…)中的置换是由x和y中的置换与导出的置换对(,)构成. 由此推出下列在置换群上的二元运算;设s是对象集为x的m次对称群,s是对象集为y的n 次对称群,s与的乘积,记作;s*,其对象集为9(-Y,它的置换由所有有序对(口,) 构成,?S,?s.,由(口,)确定的x*y中的每一个元素(,)的象如(4)式,于是有 (,)(,)一(,)(,)一(ax,).由此得到 F】(五…)=S"X-S.(9) 将(9)式代人(8>式得(6). 下面来证明(7)式. 对于V(,)?s*.,来推导交所产生的圈指标的项.没口中长度为,的一个圈为,, 中长度为的一个圈记为,于是,在有序对集x*y中共有2r1个有序对(.,.)被(,, )置换,.被置换,被置换.这些有序对被长度为[r,]的圈(,,.)置换,因此, 圈(,)置换了长度为[r,妇的共有2(r,1)个有序对,从而(,.)对s*s中圈指标产 生的项为s::"r.所以,(,)对s*S.的圈指标贡献的项为卉S::r. 于是 Z(S)=—每直.i(…r.1r",. 许进二色有向图及二色有向自补图的计数与构造占 " , . .:',口并y在.中仍是暂色性竺: 一…. 毫 或:凳磊嚣垂三(或可达到)当且仅当在D中,瑚有达到''曾??膏, (勋没有达到容器=三= 一 蝴一个二色有向图D与它的二色有向补警 图百卿磊卟项翠毫鏊定理5具有个顶点的一种颜色与个顶?'厶? 点的另一种颜色的二色有向自补图的数目为譬翟翟Z .. 1o',.,,…其器茗 的证明与[2]中主要定理的主三这个定理的证明方法与[2]中主要定理的A?: 舌. 证明方法较为类似:故在此省.~I_. 一岱喜2囊=色有向自补图的数目,并且构造出了m—n : ;时的垒部76个=色有向图及垒部12个二色摹S: 有向:.……暮容善= 则有2:0i0:吾囊喜耋三三二:则1(】)=,口】)一,J(2)=,母簪为鸟一. Z(S{鱼鱼s +2.矗矗s::"…I?1 + 鱼s') 淡西师大(自然科学版) 相应的l2个二色有向自补图如图2所示. 办h 1990年 2宠 :嚣 图2二色有向自补幽 参考文献, 1HararyF.PalmerEM.Graphicalenllmeration.AcademicPress.NewYork andLondon,1973 2HararyF.Onthenumberofbicoloredgraphs,paeifieJ.Math.1958.8;743~755 5 3魏逞荪,许进.偶自补图的计数.陕西师大(自然科学版).i988,I6(3)I, TheEnumerationandConstructionofBicoIoredDigraphs andBicoIoredSeIf—complementaryDigraphs Xu (Departmentof jn MathematicS) Abstract theenumerationofbicoloreddigraphsandbicoloredself,complementarydigraphs aresolvedbyconstructingaclassofnewgroup.Itisprovedthat,forgiventwo positiveintegersmandn,theenumerationgenerationfunctionB…(x)ofbicolored digraphswithblackcoloronmverticesandwhitecolotOnnverticesiSB…) 一Z(*S'l+),andthenumberofbieoloredself—complementarydigraphwith blaekcoloronmverticesandwhitecoloronnverticesisZ(S.g-S-'O,2,0,2,…), all76bicoloreddigraphsandal1l2bieoloredself—complementarydigraphsale constructedwhenm—一2. Keywords:bicoloreddigraphs,bicoloredself—complementarydigraphsI enumerationlc0nstructi0n 《理论力学》一出版发行 一 郜反映基础理论课教学研究成果的新书一一《理论力学》.近期已由我校出版社 出版发行.该书由 吴寿键张树华任主编.雷守文,孙凤麟.王唐任副主编.作者在奉书中,将分析力学单独立编.明确地 一 此顿力学和分力学分鳊,从编写体系『,把分析力学提到了应有的地位.以运动形式为区分点. 使l念叙述更为r钳惫.全书着意在解题方法和解题巴路方面作了分析,配备典型例题85遭.在内容上.增 卦了师范院校:必需的目c体静力学及力系简化等虎容相信该书问世,会对理论力学这门古老的基础理论 ?科的发展起主J驻l极的促进作用. (潘撅)