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