有向超图的计数理论

D0I:10.13374/j.issn1001-053x.1999.05.054 第21卷第5期 北京科技大学学报 VoL21 No.5 1999年10月 Journal of University of Science and Technology Beijing 0ct.1999 n与 研究简报 有向超图的计数理论 黄汝激 北京科技大学信息工程学院，北京100083 把有向图的计数理论1推广到有向超图. 取一个b(ts)和从每一个b(t,lE{1,…,e}-{i}, 引入了有向超边群，有向超图群和有向超图同 中任取一个b(,s)满足条件：h+…+h,=h,e≤h≤p 构的概念，导出了有向超图的计数级数，解决了 可导出一个新的有向超边置换b(,…,)如下： 有向超图的计数问题 be(t,…,t)=b(t,…,t)…b(t,…,) (4-a) b(6,…,Πi,Πfifi fib0 1有向超边群Sg及其循环指标ZSg) letiui (Se5e0） 的一般表达式 上am-三m'人mh因 ={1,…p}上p!个置换构成的点群S,可表示 mm'就mn) (4-b) 成 fe=m…k…mJM S,={ala-HIfIa(r),a(r)=(vi,w).v.v.Ev, M,=[m…k…me] 式中，b(1S1；t,5ew)表示u号M,长h-有向超边 含i-p) (1) 循环；m…k…m]是m,…,k,…,m.的最小公倍数； 式中点置换a表示成k长点循环a(r)的乘积， fM是这种循环的个数；求积是对变量u,S5m,h,h 是长为k的ar)的个数，)=(，)称为a的循 i{1,…,e以，l∈{1，…，e}-{i,的所有可能值进行 环分解向量. 的. 引理1每个点循环a(r）导出一个有向超边 根据引理1和2及有向超边群与循环指标 置换bk,r)如下： 的定义和性质，考虑到-UV,可推得： bekr片b(k,r…b(k,r）,k=l,…p,r=l,…i(2-a 定理1从点群S,可导出有向超边群S和h b(kr)=fIb(kr,s),=(-1,h-1),h=1,k (2-b) 有向超边群S的一般表达式如下： Sg={bb=b…b}=Sg…Sg (5-a) 式中，b(k,r)是h-有向超边置换；b(k,r,S)= [ee]是s号k长h-有向超边循环；f是k长 S=bb=五fhbk,r)h卫bt,,)h, 21…≤ h有向超边循环的个数；k-1,h-1= h=1,…P (5-b) (k-1)/h-1)(k-h)!. 特别有S=S,且S是图论a)中的约化有序对 令jj+…+jp,=+Σi,a(t)=a(r),b(,s)卢 群。 b(kr,S,b0=b(k,r）,b()=b(k,).则a= 定理2有向超边群S和S的循环指标 Πa(),从每个点置换a(t)可导出一个有向超边 Z(S)和Z(S)的一般表达式如下： 置换b((根据上述引理1)和一个无向超边置 ZS)=ZS)…ZS) (6) 换b()(根据文献[4]中引理1)如下： ZS)-(rs)) bet)=Πb*(t)=Π，Π女b(t,） (3-a) 一Sh] (7-1) b-Πb小Ⅱ东LⅡ系b(G,s） (3-b) 有下列引理： 2aSyW0真几在 2iset 引理2从仁1，，任取e个数：t,…t,1≤t< S路新人 …<t,≤j,2≤esj,从任一个be(t),ie{1,…,e},中任 )=0,…),N)=p/Πkj,jj1+tj, M=[m…k…ml,fa=(m…k…m,)/M,h=l,p(7-2) 1999-01-13收稿黄汝激男，67岁，教授 式中"一表示"换成"，求和是对满足Σ=p的

第 21 卷 第 5 期 1 9 9 年 10 月 北 京 科 技 大 学 学 报 J o u r n a l o f U n i v e r s i ty o f s e i e n e e a n d Te e h n o l o gy B e ij i n g V 心1 . 2 1 N 0 . 5 o e t . 1 9 99 薰亘舅 有 向超 图 的 计数 理论 黄 汝激 北京科技大学信息 工程 学院 , 北 京 10 0 0 8 3 把有 向图的计数理论 `,闭 推广 到有 向超 图 . 引入 了有 向超边群 , 有 向超 图群和 有 向超 图同 构 的概念 , 导 出了有 向超图 的计数级 数 , 解决 了 有 向超 图的计数 问题 . 1 有向超边群;sc 〕及其循环指标(Z ;sc ) 的一 般表达式 取 一个 b沪 一 ( it , s , )和 从每 一 个 b以) , l任 { l , … , e }一 { i} , 中任取一个毗 ) (t, , s,) 满足条件 : h l +. 二 十 h=e h , 。 ` h 印 可 导 出一 个新 的 有 向超边置 换:cb ( t , , … , 幼如 下 : b { 亡〕 ( r l , … , ` ) = b 一 ` : ( r ; , … , et ) … b , 一 ( t l , … , et ) ( 4 一 a ) b 一 (t^ ’l, . ,tJ 一 n 六 n 八负九呱 八 , 人 份 1 粉用 淑无 h小 二二 l 了产 1 护l 气+ 一气= 为 IC 们一时 一 i( } =v { 1 , …尹 } 上夕! 个置换构成 的点群凡可表 示 成 凡一 al{ =a if 六a,( ,)r ak( )r 一 v( , , … , *v) , v l , … , vk o v, 转渤 沙 一价 ` ’ ` l从 = Lm , ’ ( r : , s : ; … ;人 , s 。 ; u ) m , n )一 艺 m `儿 , 」( n = m h k)/ 旧俪 , K阴 n ) k,. 二 m J鱿 二 k,. 二 风」 ( 4 一 b ) 盏’bk =P , ( l ) 式 中点置换 a 表示成 k长点循环几 (r )的乘积 , 五 是长 为 k 的 口` (日的个数 , 仍二仃 1 , … 痴)称 为 a 的循 环分解 向量 . 引理 1 每个点循环*a( r) 导 出一 个有 向超边 置换 bl c] k(, )r 如下 : b 〔 ` 〕 (k, r卜 b : `〕 k(, )r … b ;` 一 (,k r ) , 卜 l , … 刃 , 二 l , … ’Jk ( 2 一 a ) 。 : * 〕 (瓦)r 一 六。沪: (从 r , s ) ,关气、 一 l , * 一 l 一 , * 一 l , … , 、 ( 2 一 b ) 式 中 , *bl (] k, )r 是 h 一 有 向 超 边 置 换 ; 时 〕 k(, ,r s) = 〔才 〕… 时习是 : 号 k 长 h 一 有 向超边 循环 ; 人是 k 长 h 一 有 向 超 边 循 环 的 个 数 ; k( 一 1 , h 一 1卜 k( 一 l ) ! / ( h 一 l ) ! ( k一 h ) ! . 勿万 , + … +j) , =t +r 艺 誓坏 , a ( r ) = a * ( r ) , b声 1 ( r , s ) = b沪(弋r , s ) , b : h 一 (t) = b 一 h l (瓦 r ) , b 〔 c〕 ( t ) = b 一 亡 ( k , r ) . 则 =a n 简a( t) , 从每个 点置换 a( t) 可导 出一个有 向超边 置 换 bc[ : ( t)( 根据上述 引理 l) 和 一个 无 向超 边置 换 b( t)( 根 据文献 【4」中引理 l) 如下 : b 〔 · i (t) 二 fl 戈 二 , b :为: ( t) = fl 暴 l fl 澳 . b护 : ( t , s ) ( 3 一 a ) b ( t) = fl 奉 : b 伪 , ( )t = fl 集 1 fl fl 么 l b岔, ( r , s ) ( 3 一 b ) 赶川 K k内) 有下列 引理 : 引理 2 从 =t 1 , … J , 任取 e 个数 :lt , … , 人 , 1夕 1 < … ct< 习 , 2 ` e 习 , 从任 一 个 b叹t,) , 汇 { 1 , … , e} , 中任 式 中 , 峨(t, ,s l ’; ; et, ;as u) 表示 u号 斌 长 h 一 有 向超边 循 环 ;[ m , … k., 二 m习是 m l , … , ik , … , m 。 的最 小 公 倍数 ; 几 是这种循环 的个数;求积 是对变量 u, is, ,sl m h, , I凡 iE { 1 , … , e} , lE { l , … , e} 一 { i} , 的所有 可能值进行 的 . 根据 引理 1 和 2 及有 向超边群 与循 环指标 的定义和性质 ` ;1] , 考虑到 砂=] u 纂 ,砂〕 ,可推 得 : 定理 1 从点群凡可导 出有 向超边群 sct 一 和 h - 有 向超边群母 ,的一般表达 式如下 : icS := {b 叫:cb = :lb 一夕 3 }=sJ , ,…砂 : (5 一 a) ;hs 〕= { b 〔为〕 } b 儿〕= P J . n n 卜内 辉 1 。 〔` “ ( 、 , r )直 n 产 2 1夕 l< 斗习 h = 1 , … ,P 特 别有男 :二凡 , 且毋 一 是 图 论 群 . b 〔人: ( r l , … ,人) } , ( 5 一 b ) 【,刃 中的约化有序对 定 理 2 有 向超 边 群 isc : 和 砂 : 的循 环 指 标 (Z ;sc ) 和 (Z 砂 一 ) 的一般表 达式如下 : (Z isc ) = 以男 一 ) … (Z ihs ) (6 ) (z 军 〕 ) 一击 : 。 〔* , [。沪 一 ( 、 , r , s )一: * , * , 。盗( , 1 , : 1 ; … ;。 , s 。 ; u ) l今 ! b’ 〔 罕 一 s 、 , 〕 (z 梁) 一 去 : 岭) ft 砌 尸 ` U ) 介. 六 ( 7 一 l ) j n 心二 2 n n n 1` 瓦< 从匀 气 , ,h , 户 l 气` , 气= h 七俪 J(七 气) l〔 { 1 , . e } 一 { : } 1 99 9 一 0 1 · 1 3 收稿 黄汝激 男 , 67 岁 , 教授 故犷 人; 0’) = 幼 , … 痴) , 岭)=P ! / n 弘 ’kj ! , ’=j 1 +. 二 +’jn , 似 :[ m , … k,. 二 m月 ,几 二 ( m , … k,. 二 m e)/ 从 , h = 1 , … ,P ( 7 一 2) 式 中 ’一 ’ 表示 ” 换成 ” , 求和 是 对满足 乏衡*kj =P 的 DOI: 10. 13374 /j . issn1001 -053x. 1999. 05. 054

512 北京科技大学学报 1999年第5期 所有向量()进行的，表示置换b中含有j:个 定理3d(6y)和d,y)可从S和S的循环指 k长h-有向超边循环，余类推，每项中所有循环的 标Z(S)和Z(S)导出如下： 个数与长度之积的和等于hp,h). Hp.h) d(y=ZS,5nh一l+yg卢Σ42 (9-a) 9.0 d0y)=Z(SpSmh一1+yg,h=l,…p) (9-b) 2无标号有向超图的计数级数 =Π1dgyFΣd.ov,dnp=Πda 无标号的有向超图计数级数dxy),p点有向 推论p点无标号的h-有向超图总数n,和 超图计数级数d,y)和p点h-有向超图计数级数 有向超图总数n如下： d(y)的定义如下： n=d6(0y=1上Z(Sg5mh一2)，h=1,…p (10-a) d(xy)=d,6yx=Σpe4.ey (8-a) nm=∑n2 (10-b) do0y=Σedoy,p=1,2,3,… (8-b) 参考文献 d(ya=∑dyg,h=l,p (8-c) 1 Harary F.Graph Theory.Massachusetts:Addison-Wesley, 式中，yy,…y,-(q,…,9m,ygyg,d.0 1969 d4,表示含p点g条h-有向超边，h=l,…p,的无标 2 Harary F.Palmer E M.Graphical Enumeration.New York 号有向超图的数目，d。表示含p点q条h-有向超 and London:Academic Press,1973 边的无标号h-有向超图的数目，求和是对所有 3黄汝激.有向超图理论的发展和应用.电子科技导 p=1,2,…和2中所有9w=0,1,…,h2,h),h=1,"p,进行 报，1995(3)：10 4黄汝激，无向超图的计数理论.北京科技大学学报， 的.应用定理2和文献[1,2]中的Polya计数定 1999,21(5):507 理可导出： Counting Series of Directed Hypergraphs Huang Ruji Information Engineering School,UST Beijing,Beijing 100083,China 米米米米米米米米米米米米米米米米米米米米米米米米米米米米米米米米米米米米米米米米米米米 [Journal of University of Science and Technology Beijing (English Edition),1999,6(3),168] Combined Effect of Arsenic and Cadmium on the Transformation of Ferrihydrite into Crystalline Pro- ducts Tichang Sun,C R Paige,WJ Snodgrass Abstract:Ferrihydrite,prepared in the presence of different amount of As and Cd in the solution,was used to study the combined effect of As and Cd coexisted in the same system on the transformation of ferrihydrite into crystalline products at pH 8 and pH 12.The data showed that there was apparent interaction between As and Cd in the transformation process.At pH 8,the transformation product was hematite with 1%As and different percent Cd(mole fraction,so as the follows),but the size of particles formed with different amount of Cd was different.At pH 12,the transformation products varied from sole hematite with 1%As and less than 2%Cd to a mixture of hematite and goethite with more than and equal to 2%Cd,and the percentage of goethite in the transformation products increased with the increasing level of Cd in the system.XRD(X-ray diffraction)and chemical analysis data showed that almost all As and part of Cd initially present in the system were retained in the crystalline products.The presence of As increased the amount of Cd retained in the structure of iron ox- ide.SEM(Scanning Electron Microscope)examination showed that the presence of As and Cd also altered the morphology of crystalline products. Key words:ferrihydrite;arsenic;cadmium;transformation;crystallization

一 5 1 2 - 北 京 科 技 大 学 学 报 1 9 9 9 年 第 5 期 所有 向量0’) 进行 的 , 心表示置 换护〕中含有不五 个 k长h 一 有 向超边循环 , 余类推 ,每项 中所 有循环 的 个数与长度 之积 的和 等于 h切 , h) . 定理 3 毋 :饥)和 味伽)可 从军 和 ;sc 」 的循环 指 标 (Z 砂) 和 (Z sct ) 导 出如下 : 咧卿艺 心 ]饥卜(Z 母 〕 .,s , 一 l勺心) = 舔 , ,洲 山 2 无 标号 有 向超图 的计数级数 无标号的有 向超图计数级数试 义 少) , p 点有 向 超 图计数 级数 dP 伽)和 P 点 h 一 有 向超 图计数 级数 心 一 切的定义如下 : dx( 必二 艺声舔妙扮= 艺 , , 两 , 户勺。 (8 一 a) 味伽=) 艺武护 , p = 1, 2, .3, · (8 一 b) 心 〕饥卜艺胃比袱 , 卜 1 , … ,P (8 一 c) 式 中 , =y 伽 , , … 沂) , =Q ( q , , … ,价) , 少口气川 口 . · 片 , 冻广 氏q, . , , 表 示含尸点q条 h 一 有 向超边 , h=l , … ,P , 的无标 号有 向超 图的数 目 , 冻 , 表示含尸点q 。条 h 一 有 向超 边 的无标 号 h 一 有 向超 图的数 目 , 求和是对 所有 p =l , 2 , … 和 Q中所有争= 0 , 1 , … , h切 , h) , h=l , … 刃 , 进行 的 . 应用 定理 2 和文献 「1 , 2] 中的 P ol ya 计 数定 理可 导 出 : 伟切 二 (Z icS ,sm , 一 1切 , h = 1 , … ,P ) ( 9 一 a ) ( 9 一 b ) = n 弘心 伽办二 艺 凤护 , 氏 。 = fl =l{ 氏 。 推 论 P 点无标号 的 h 一 有 向超 图总数心 : 和 有 向超 图总数 cn4 如 下 : 心七心 :协= 1 ) = 以毋:,s 。 , 一 2 ) , h = 1 , … ,P ( 10 一 a) cnj 〕= 艺仁 :心 : ( 10 一 b ) 参 考 文 献 H ar 田令 .F G r aP h hT e o yr . Mas s a e h u s e t s: A d d i s o n 一 W七s l e y, 19 69 H ar a yr .F P a lm e r E M . G r a Ph i e a l E n um e r at i o n . N e w oY r k an d L o n d o n : A e a血 m i e P er s s , 1 9 7 3 黄汝激 . 有向超图理论 的发展和应 用 . 电子科技导 报 , 19 95 (3) : 10 黄汝激 . 无 向超图 的计 数理 论 . 北京 科技 大学 学报 , 199 9 , 2 1( 5) : 5 0 7 C o un t i n g S e ir e s o f D i r e e t e d H yP e 班笋a Ph s 万扮口双g R’uj i I n fo mr at i o n E n g in e e r i n g S e h o l , U S T B e ij ing , B e ij in g 10 0 0 8 3 , C h i n a o[J u r n a l of nU iv esr i印 of sc i e n c e a n d eT c h n o l o 舒 B e 扩ing (E n g lis h 石id t ot n ) , 19 9 9 , 6 ( 3 ) , 16 8 ] C o m b i n e d E fe e t o f A r s e n i e a n d C a d m i u m o n t h e rT a n s fo r m a it o n o f F e r ir b y d irt e in t o C yr s t a 址n e P or - d U C t S icT h a gn uS n , C R QP geI , 万 J 肠 o dg r 口 5 5 A b s t r a e t : F e币hy dr it e , Pr e Par e d i n ht e P r e s e n e e o f d i fe r e in am o u n t o f A s an d C d i n ht e s o lut i o n , w a s u s e d t o sut dy ht e e om b i n e d e fe e t o f A s a n d C d e o e x i s t e d i n ht e s a m e s y s t e m o n t h e tr a n s fo mr at ion o f fe r i妙 idr t e in t o e yr s at lli n e Pr o d u e t s a t P H 8 an d P H 12 . Th e d a t a s h o w e d ht at ht e r e w a s a PP ar e nt in t e ar e t i o n b e wt e e n A s an d C d i n ht e tr an s fo n n at i o n P r o e e s s . A t P H S , ht e tr an s fo mr at i o n Pr o du e t w a s h e m iat et w iht l% A s an d d i fe r e nt P e r e e nt C d (m o l e fr a e t i o n , 5 0 a s ht e fo ll o w s ) , b ut ht e s i z e o f Part i e l e s fo mr e d w iht d i fe r e nt am o u n t o f C d w a s d i fe r e nt . A t PH 12 , ht e tr an s fo mr at i o n Pr o d u e t s v iar e d fr o m s o l e h e m at it e w iht l% A s an d l e s s t h an Z% C d t o a m i x t u r e o f h e m at it e an d g o e t h it e w iht m o r e ht an an d e q u a 1 t o 2 % C d , an d ht e P e r e e nt a g e o f g o e ht i et in ht e tr an s fo mr at i o n rP o d u c t s i n e r e a s e d w iht ht e i n e er a s i n g l e v e l o f C d i n ht e sy s et m . X RD (X 一 r ay d i价a e t i o n) an d e h e m i e a l an a l y s i s d at s h o w e d ht a t a lm o s t a ll A s an d P art o f C d i n it i a ll y P r e s e nt i n ht e sy s t e m w e r e r e at in e d i n ht e e yr s at lli n e Pr o du e t s . hT e Pr e s e n e e o f A s i n e r e a s e d ht e am o un t o f C d r e at i n e d i n ht e s trU e trU e o f ir o n o x - id e . SEM ( S e an in g E l e e otr n M i e r o s e o Pe ) e x am i n at i o n s h o w e d ht at ht e rP e s e n e e o f A s an d C d a l s o a lt e r e d ht e m o rp h o l o gy o f e yr s at lli n e P r o d u e t s . K 即 w o r d s : fe 币h y idr t e ; ar s e n i e ; e a dm i urn ; 加n s fo mr a t i o n ; e yr s at lli z a t i o n