资源描述：
《无圈线性同胚K 不可约超图的计数》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第26卷第6期惠州学院学报(自然科学版)Vol1261No162006年12月JOURNALOFHUIZHOUUNIVERSITYDec12006无圈线性同胚k不可约超图的计数黄俊源(华南师范大学 教学系,广东 广州 510631) 摘 要:无圈超图的数学模型在计算机科学的关系数据库设计和蜂窝式移动通信系统中具有重要作用。本文运用了Polya计数定理得到了无标号无圈线性同胚k不可约超图的计数公式。关键词:超图;无圈线性同胚k不可约超图;线性同胚k不可约超树;二部树;Polya计数定理中图分类号:O157.5 文献
2、标识码:A 文章编号:1671-5934(2006)06-0022-051 定义和性质超图是有限集合的子集系统,是最一般的离散结构。它是图的概念的推广,用“图的语言”描述集合系[1,2]统。近年的研究表明,无圈超图的数学模型在计算机科学的关系数据库设计中有重要应用。在一个蜂窝式网络中,路线分派的模型主要是图模型,然而,在模拟总的流量时,蜂窝式系统中的超图模型是比图模型更加有优势。因而,在固定和动态的路线分派计划中,用超图模型来设计比用图模型来设计[3]更加有效。定义111 二元组H=(X,ζ)为一个超图,如果X=(
3、x1,x2,⋯,xp)是有限集,ζ=(Ei
4、i=1,2,⋯,qq)是x的子集的一个族,其中Ei≠«,1FiFq,且∪i=1Ei=X,
5、X
6、=p称为H=(X,ζ)的阶。X中的元素成为顶点,ζ中的元素称为边。若Ei∈ζ,且
7、Ei
8、=1,则Ei称为环(loop)。又max
9、Ei
10、称为H的秩。在超图H=(X,ζ)中,一个顶点称为孤立的,如果它仅仅属于一条边。一条边E成为H的一个耳朵,如果存在E′∈ζE,使得EE′中的每个顶点是孤立的。设E是一个耳朵,称从H中除去E为耳朵移除,重[4]复耳朵移除直到不能再移除为止,所得的超
11、图称为是原超图的Graham约简。一个超图称为是无圈的,如果它的Graham约简是空的。在超图H中,若对任意两条不同的边E1,E∈ζ,在ζ中均存在一边序列f1,f2,⋯,fk,使得E1=f1,E2=fk,且fi∩fi+1≠«(1FiFk-1),则称H是连通的。定义112 如果超图H=(X,ζ)是连通且不含圈的,则称H为超树。如果对于每一条边Ei,Ej∈ζ,都有
12、Ei∩Ej
13、F1,则称超图H=(X,ζ)是线性的。定义113 在线性超树H=(X,ζ)中,如果PEi∈ζ,
14、Ei
15、E2,且Ei中恰有一点是与其它边的公共点,则
16、称Ei为悬挂边。定义114 在超图H=(X,ζ)中,若顶点vi∈Ei,则称顶点vi与边Ei是关联的。与顶点vi关联的边的数目,称为顶点vi的度,用符号d(vi)表示。定义115 如果线性超树H=(X,ζ)不含有k度点,则称H=(X,ζ)为线性同胚k不可约超树。线性收稿日期:2006-09-26作者简介:黄俊源(1980-),男,广东揭阳人,硕士研究生。 第6期黄俊源:无圈线性同胚k不可约超图的计数·23·同胚2-不可约超树称为同胚不可约超树。定义116 超图H=(X,ζ)的对应二部图为G(H)=(Y1,Y2,E)(这
17、里Y1,Y2是G两部分顶点集,E是边集),其中Y1=X,Y2=ζ(即把超图H=(X,ζ)中的边Ei看成是G(H)中Y2的点)。在G中,两点xi∈Y1,Ej∈Y2之间连一条边当且仅当在H中xi∈Ej。定义117 线性超树H=(X,ζ)对应二部图G(H)=(Y1,Y2,E)称为对应二部树;给其对应二部树的某个点着以根点,称为对应二部有根树;给其对应二部树的某个一度点着以根点,称为对应二部植树。定义118 如果超图H是一棵超树,并且它的顶点和边都是无标号的,则称这样的超图为无标号超树。Harary在其著作[5]中给出了同胚
18、不可约树的计数公式。单志龙和柳柏濂在[6]中得到了严格非匀称线性超树的计数公式。在[7]中单志龙和柳柏濂给出了匀称线性无圈超图的计数公式,并且研究了无标号匀称线性无圈超图的计数公式。后来在[8]中单志龙和柳柏濂进一步得到无标号线性无圈超图的计数公式。邓志云,杨云苏在[9]中得到同胚不可约k树的计数公式。魏均斌在[10]中得到了同胚不可约超树的计数公式。本文在此基础上运用Polya计数定理进一步得到了无标号线性同胚k不可约超树的计数公式和无标号无圈线性同胚k不可约超图的计数公式。关于线性超图及其对应的二部图,在文献[1
19、1]中已证明下面的结论:引理111H是线性超树当且仅当它对应二部图G(H)是树。引理112 若H是线性超树,无环,且
20、ζ
21、E2,则其对应二部图G(H)的边集E中至少有两条悬挂边。对于线性超树,我们可由度及二部树的定义得到下面的结论引理113 若H=(X,ζ)是线性超树,G(H)=(Y1,Y2,E)是其对应二部树,xi∈X,x′i是xi在Y1中的
