自同态生物力量的元循环图

自同态生物力量的元循环图

最终半正图是原始半组图的图。同一图的等效截面。这是一个完整的自然生态图像的子图。它们都是收缩图的收缩核。这与自然生态图像的原始图像具有相同的结构。在和中，通过图积算法获得了更广泛的最终结果。李于民还提供了一个家庭的自然生态横截面，即黄色cn（n.3）cn（n.3）。事实上，左图（n.3）cs，左图（n.3）是末端的正式循环图。在这项工作中，我们研究了小型末端的后半部分。本文只讨论有限简单图.记X=(V(X),E(X))为具有顶点集V(X),边集E(X)的图.若顶点x1与x2在X中相邻,则记为{x1,x2}∈E(X).称映射f∶V(X)→V(Y)为图X到图Y的同态,如果f保持顶点的相邻关系,即对任意x1,x2∈V(X),{x1,x2}∈E(X)蕴含{f(x1),f(x2)}∈E(Y).若f是双射,并且f-1也是从Y到X的同态,则称f是X到Y的同构.当X=Y时,上面定义的映射分别称为自同态与自同构.X的所有自同态的集合记为EndX,它在通常的映射合成下构成一个幺半群,称为图X的自同态幺半群.类似地定义图X的自同构群AutX.显然AutX⊂EndX.若AutX=EndX,则称X为E-A不可收缩图.设f∈EndX,分别记ran(f),R(f)为f的像集及由此像集ran(f)导出的X的子图.称R(f)为图X在f下的自同态像子图.f|V′表示映射f在V的子集V′上的限制.若对所有v∈ran(f),f(v)=v,则称自同态f为收缩映射,称相应的自同态像子图R(f)为X的收缩核.设S是一个幺半群,a∈S,称a为S的正则元如果存在b∈S使得aba=a.若S中所有元素都是正则元,则称S是正则幺半群.若图X的自同态幺半群EndX是正则幺半群,则称图X是End-正则图,其它概念和术语可参见文献.引理1设X是图,f∈EndX,则下列条件等价:(i)f是正则元;(ii)R(f)是X的收缩核,并且存在X的收缩核A,使得f|V(A)是从A到R(f)的同构;(iii)R(f)是X的收缩核,并且存在X的导出子图A,使得f|V(A)是从A到R(f)的同构.引理2设X是二分图,则X是End-正则图当且仅当X是下列图之一:(i)完全二分图Kn,m(n,m≥1);(ii)双星图T(r,s)(r,s≥1);(iii)6长圈C6;(iv)4长路P4或8长圈C8;(v)不连通图nK1,(n-1)K1∪K2或nK2(n≥2).若图有n个连通分支,并且每个连通分支都同构于X,则记此图为nX.若对任意f,g∈EndX,有ran(f)⊆ran(g)或者ran(g)⊆ran(f),则称X为阶梯图.显然,E-A不可收缩图是阶梯图,偶圈不是阶梯图.引理3nX是End-正则图当且仅当X是End-正则的阶梯图.记循环图G为Cn〈j1,j2,…,jr〉,其中1≤j1<j2<⋯≤jr=[n/2]([n]1≤j1<j2<⋯≤jr=[n/2]([n]表示不大于n的最大正整数),顶点集为V(G)={0,1,…,n-1},边集为E(G)={{i,j}||j-i|≡jk(modn),k=1,2,…,r}.循环图G=Cn〈j1,j2,…,jr〉有m=gcd(n,j1,j2,…,jr)个连通分支,每个连通分支的度数都与G的度数相同并且都同构于Cn/m〈j1/m,j2/m,…,jr/m〉.若G=Cn〈j1,j2,…,jr〉(jr≠n/2)是偶数度循环图,则G是由一些回路构成的,这些回路分成r组,每组是由Cn〈ji〉(i=1,2,…,r)构成的mi=gcd(n,ji)条长为nminmi的边不相交的回路组成.若G=Cn〈j1,j2,…,jr〉(jr=n/2)是奇数度循环图,则G由两部分构成:一部分由r-1组回路构成,每组回路是由Cn〈ji〉(i=1,2,…,r-1)构成的mi=gcd(n,ji)条长为nminmi的边不相交的回路组成;另一部分由n/2条边{0,n/2},{1,1+n/2},{2,2+n/2},⋯,{n/2-1,n-1}{0,n/2},{1,1+n/2},{2,2+n/2},⋯,{n/2−1,n−1}构成.根据循环图的结构,1度循环图即为Cn(j)(j=n/2).而Cn(j)≅jK2,由引理2,即得下面定理.定理4Cn(j)(j=n/2)是End-正则图.关于2度循环图,有下面结果.定理5设X=Cn(j)(j≠n/2),m=gcd(n,j),则X是End-正则图当且仅当n/m为奇数或者n=4,6,8而且m=1.证把m分成两种情形进行讨论:情形1当m=1时,X只有一个连通分支并且每个顶点的度数为2,所以X是圈Cn.(i)若n为奇数,因为对任意f∈EndX,f只能把极小奇圈Cn映到极小奇圈Cn,所以f是满射,必为自同构.此时,EndX=AutX,f是正则元,因此X=Cn是End-正则图.(ii)若n为偶数时,偶圈Cn是二分图.由引理2得X=Cn是End-正则图当且仅当n等于4,6或8.由(i),(ii),当m=1时,Cn(j)(j≠n/2)是End-正则图当且仅当n为奇数或为4,6,8.情形2当m>1时,由循环图的结构可知X由m个连通分支组成,每个连通分支为Cn/m.(i)′若n/m为奇数,与情形1中(i)的证明类似,可知EndCn/m=AutCn/m.因此Cn/m是End-正则的阶梯图.又由引理3得X=mCn/m是End-正则图.(ii)′若n/m为偶数,与情形1中(ii)的证明类似,可知Cn/m是End-正则图当且仅当n/m等于4,6或8.但当n/m等于4,6或8时,Cn/m是偶圈,不是阶梯圈.由引理3得X=mCn/m不是End-正则图.由(i)′,(ii)′,可知当m>1时,Cn(j)(j≠n/2)是End-正则图当且仅当n/m为奇数.综合情形1,情形2,可知X=Cn(j)(j≠n/2)是End-正则图当且仅当n/m为奇数或者n=4,6,8而且m=1.因为gcd(n,j,n/2)=gcd(j,gcd(n,n/2))=gcd(j,n/2),所以由循环图的结构可知3度循环图Cn〈j,n/2〉由m=gcd(j,n/2)个有n/m个顶点的互相同构的连通分支构成,而且每个连通分支都是3度连通循环图.又因为gcd(j,n/2)=m,所以gcd(n,j)=m或2m.先讨论3度连通循环图.引理6设Cn〈i,n/2〉与Cn〈j,n/2〉都是3度连通循环图.若gcd(n,i)=gcd(n,j)=1,则Cn〈i,n/2〉与Cn〈j,n/2〉都与Cn〈1,n/2〉同构;若gcd(n,i)=gcd(n,j)=2,则Cn〈i,n/2〉与Cn〈j,n/2〉都与Cn〈2,n/2〉同构.由引理6可知所有3度连通循环图Cn〈i,n/2〉只分为两类:Cn〈1,n/2〉与Cn〈2,n/2〉.命题7设Cn〈1,n/2〉是连通图,则它是End-正则图当且仅当n≡0(mod4)或者n=6.证因为n为偶数,所以n/2或者为偶数,或者为奇数.可把Cn〈1,n/2〉分为两类:C4k〈1,2k〉与C4k+2〈1,2k+1〉.(i)如果n/2为偶数,那么设n/2=2k(k≥1).对任意f∈EndC4k〈1,2k〉,f是单射.事实上,因为C4k〈1,2k〉中任意两个顶点都在一个极小2k+1长奇圈上.如果f不是单射,那么f把此奇圈映到一个比它更小的奇圈,矛盾.所以,EndC4k〈1,2k〉=AutC4k〈1,2k〉,进一步得C4k〈1,2k〉是End-正则图.(ii)如果n/2为奇数,那么设n/2=2k+1(k≥0).将C4k+2〈1,2k+1〉中顶点标号按奇偶分划,易见它为二分图.由引理2,可知C4k+2〈1,2k+1〉是End-正则图当且仅当它是C6〈1,3〉,即图K3,3.综合(i),(ii),可知当n≡0(mod4)或者n=6时,Cn〈1,n/2〉是End-正则图.充分性得证.又由(ii)可知当n≠0(mod4)时,n/2为奇数,如果n≠6,那么Cn〈1,n/2〉不是End-正则图.必要性得证.记G□H为图G与H的卡氏积,它的顶点集V(G□H)=V(G)×V(H),边集为E(G□H)={{(u,x),(v,y)}∶u=v且{x,y)∈E(H)或者{u,v}∈E(G)且x=y}.引理8若循环图Cn〈j1,j2,jr,n/2〉是连通的,且gcd(n,j1,j2,…,jr)=2,则Cn〈j1,j2,⋯,jr,n/2〉≅Cn/2〈j12,j22,⋯,jr2〉□Κ2命题9若Cn〈2,n/2〉是连通图,则它是End-正则图,且不是阶梯图.证先证明n/2为奇数.否则,如果n/2为偶数,那么gcd(2,n/2)=2≠1.即Cn〈2,n/2〉有2个连通分支,矛盾.所以n/2为奇数.由引理8可知Cn〈2,n/2〉≅Cn/2□K2,因此Cn/2是Cn〈2,n/2〉的极小奇圈.设Cn/2的顶点为0,1,…,n/2-1,K2的顶点为0,1.按卡氏积的定义对Cn〈2,n/2〉进行标号.可以构造映射α如下:α((i,1))=(i,1),α((i,0))=(i+1,1)(i∈{0,1,…,n/2}且运算取模n/2).设G=R(α),G′=(Cn/2□K2)-G.则G为由边{(0,1),(1,1)},{(1,1),(2,1)},…,{(n/2-1,1),(0,1)}组成的圈Cn/2,它是Cn〈2,n/2〉的收缩核.而G′为由边{(0,0),(1,0)},{(1,0),(2,0)},…,{(n/2-1,0),(0,0)}组成的圈Cn/2.同理可构造映射β使R(β)=G′.而G与G′之间没有包含关系,故Cn〈2,n/2〉不是阶梯图.因为对任意f∈EndCn〈2,n/2〉,f只能把极小奇圈Cn/2映到极小奇圈Cn/2,所以R(f)=Cn〈2,n/2〉≅Cn/2□K2或者R(f)=Cn/2.(i)如果R(f)=Cn〈2,n/2〉,那么f是满射,所以是自同构.因此f是正则元.(ii)如果R(f)=Cn/2,则R(f)是Cn〈2,n/2〉的收缩核,并且存在Cn〈2,n/2〉的收缩核A=(Cn/2□K2)-R(f),使得f|A是A到R(f)上的同构.根据引理2得f是正则元.综上所述,Cn〈2,n/2〉是End-正则图.命题10设Cn〈j,n/2〉是不连通图,m=gcd(j,n/2)>1,则Cn〈j,n/2〉是End-正则图当且仅当gcd(n,j)=m并且n/2m为偶数.证如果m=gcd(j,n/2),那gcd(n,j)=m或2m.如果gcd(n,j)=m,那么gcd(n/m,j/m)=1.由引理6得每个连通分支同构于Cn/m〈1,n/2m〉.又由命题7得Cn/m〈1,n/2m〉是End-正则图当且仅当n/m≡0(mod4)或n/m=6.当n/m≡0(mod4),即n/2m为偶数时,由命题7(i)的证明过程,可知EndCn/m〈1,n/2m〉=AutCn/m(1,n/2m).又由引理3得mCn/m〈1,n/2m〉是End-正则图.当n/m=6时,C〈1,3〉不是阶梯图,根据引理3可知mCn/m〈1,n/2m〉不是End-正则图.如果gcd(n,j)=2m,那么gcd(n/m,j/m)=2.由引理6得每个连通分支同构于Cn/m〈2,n/2m〉.由命题6得Cn/m〈2,n/2m〉不是阶梯图